24
Optimisation
Exemple 2. Dans un produit matriciel, on peut réduire le nombre de multiplications en augmentant le nombre d’additions. Le produit de deux matrices à deux lignes et deux colonnes nécessite sept multiplications et non
huit :
µ
de
fg
¶µ
hi
jk
¶
=
µ
¶
On calcule successivement
s 1 = dh
s 2 = ej
s 3 =(d f)(k i )
s 4 =(f + g)(i h)
s 5 =(d + e f g)k
s 6 = g(h i + j k)
s 7 =(f d + g)(h i + k)
Ces sept valeurs su!sent pour déterminer le produit des deux matrices
= s 1 + s 2
= s 1 + s 4 + s 5 + s 7
= s 1 + s 3 + s 6 + s 7
= s 1 + s 3 + s 4 + s 7
Lorsque plusieurs utilisateurs ou plusieurs fragments de calculs veulent utiliser un même résultat, il est possible d’organiser le calcul de manière parallèle de sorte que chaque calcul réutilise un ensemble de données préalablement calculées : c’est le préconditionnement. Par exemple, pour évaluer
la valeur en { d’un polynôme du quatrième degré, on calculera au préalable
les quantités > > et définies par :
d{
4 + e{
3 + f{
2 + g{ + h =[({ + ){ + ][({ + ){ +({ + )] +
Les coe!cients étant donnés par les relations
=(e d)@2d
=(gf@d
2 )+
2 ( +1)
=(f@d) ( +1)
= h d
Par l’évaluation de ces quantités et leur mise à disposition dans d’autres
calculs, le calcul du polynôme ne nécessite plus que trois multiplications.
On peut généraliser ce processus. Strassen a montré que le produit de deux
matrices 2q × 2q se ramène au produit de sept matrices q × q.
La règle de Horner permet l’évaluation d’un polynôme en un point donné en
un nombre optimal d’opérations. Dans un article publié en 1819, William
Horner (1786-1837) a indiqué une méthode pour évaluer la valeur d’un
Optimisation
Exemple 2. Dans un produit matriciel, on peut réduire le nombre de multiplications en augmentant le nombre d’additions. Le produit de deux matrices à deux lignes et deux colonnes nécessite sept multiplications et non
huit :
µ
de
fg
¶µ
hi
jk
¶
=
µ
¶
On calcule successivement
s 1 = dh
s 2 = ej
s 3 =(d f)(k i )
s 4 =(f + g)(i h)
s 5 =(d + e f g)k
s 6 = g(h i + j k)
s 7 =(f d + g)(h i + k)
Ces sept valeurs su!sent pour déterminer le produit des deux matrices
= s 1 + s 2
= s 1 + s 4 + s 5 + s 7
= s 1 + s 3 + s 6 + s 7
= s 1 + s 3 + s 4 + s 7
Lorsque plusieurs utilisateurs ou plusieurs fragments de calculs veulent utiliser un même résultat, il est possible d’organiser le calcul de manière parallèle de sorte que chaque calcul réutilise un ensemble de données préalablement calculées : c’est le préconditionnement. Par exemple, pour évaluer
la valeur en { d’un polynôme du quatrième degré, on calculera au préalable
les quantités > > et définies par :
d{
4 + e{
3 + f{
2 + g{ + h =[({ + ){ + ][({ + ){ +({ + )] +
Les coe!cients étant donnés par les relations
=(e d)@2d
=(gf@d
2 )+
2 ( +1)
=(f@d) ( +1)
= h d
Par l’évaluation de ces quantités et leur mise à disposition dans d’autres
calculs, le calcul du polynôme ne nécessite plus que trois multiplications.
On peut généraliser ce processus. Strassen a montré que le produit de deux
matrices 2q × 2q se ramène au produit de sept matrices q × q.
La règle de Horner permet l’évaluation d’un polynôme en un point donné en
un nombre optimal d’opérations. Dans un article publié en 1819, William
Horner (1786-1837) a indiqué une méthode pour évaluer la valeur d’un