Avant de commencer à aborder le sujet principal, il est important de comprendre un point essentiel pour la compréhension du développement des méthodes qui vont être présentées ci-après. Dans un cours d'initiation à l'algèbre linéaire, on n'insiste pas trop sur les problèmes pratiques. Par exemple, si on doit s'intéresser au produit suivant : \[ \begin{bmatrix} \alpha & \beta & \gamma \end{bmatrix} \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} \begin{bmatrix} A & B & C\\ D & E & F\\ G & H & I \end{bmatrix} \]
on n'insiste pas trop sur l'ordre des opérations. Calcule-t-on
\[ \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} \begin{bmatrix} A & B & C\\ D & E & F\\ G & H & I \end{bmatrix}= \begin{bmatrix} A^\prime & B^\prime & C^\prime\\ D^\prime & E^\prime & F^\prime\\ G^\prime & H^\prime & I^\prime \end{bmatrix} \]puis
\[ \begin{bmatrix} \alpha & \beta & \gamma \end{bmatrix} \begin{bmatrix} A^\prime & B^\prime & C^\prime\\ D^\prime & E^\prime & F^\prime\\ G^\prime & H^\prime & I^\prime \end{bmatrix} = \begin{bmatrix} \alpha^{\prime\prime} & \beta^{\prime\prime} & \gamma^{\prime\prime} \end{bmatrix} \]ou
\[ \begin{bmatrix} \alpha & \beta & \gamma \end{bmatrix} \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} = \begin{bmatrix} \alpha^{\prime} & \beta^{\prime} & \gamma^{\prime} \end{bmatrix} \]puis
\[ \begin{bmatrix} \alpha^\prime & \beta^\prime & \gamma^\prime \end{bmatrix} \begin{bmatrix} A & B & C\\ D & E & F\\ G & H & I \end{bmatrix} = \begin{bmatrix} \alpha^{\prime\prime} & \beta^{\prime\prime} & \gamma^{\prime\prime} \end{bmatrix}? \]Après tout, peu importe. Dans les deux cas on aboutit au même vecteur. Du point de vue de l'algèbre linéaire théorique, c'est une vérité d'église puisque les produits matriciels sont associatifs. Mais, du point de vue du calcul en lui-même, est-ce bien la même chose ?
Considérons la première méthode. Quand on effectue le produit matriciel d'un matrice $3\times 3$, on réalise 9 fois : 3 multiplications et deux additions, soit 27 multiplications et 18 additions. Puis, quand on réalise le produit du vecteur ligne par la matrice résultante, on ajoute 3 fois : 3 multiplications et 2 additions, soit 9 multiplications et 6 additions. Au bout du compte, on a réalisé 30 multiplications et 20 additions soit 50 opérations.
En ce qui concerne la seconde méthode, on commence par le produit d'un vecteur avec une matrice et on vient juste de voir que cela correspond à 9 multiplications et 6 additions dont la résultante est un vecteur $1 \times 3$ que l'on doit une seconde fois multiplier par une matrice $3 \times 3$, ce qui fait que l'on réalise le même type d'opérations deux fois. Au bout du compte, on a réalisé 18 multiplications et 12 additions soit 30 opérations. On a fait une économie de 20 opérations avec la seconde méthode soit 33.33\% des opérations. C'est énorme !
Maintenant, adoptons toujours le point de vue de l'économiste sur la résolution d'un système d'équations linéaire du type
\[ \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix} \begin{bmatrix} x\\ y\\ z \end{bmatrix} = \begin{bmatrix} \alpha\\ \beta\\ \gamma \end{bmatrix} \hspace{.25cm}\Longleftrightarrow\hspace{.25cm} \begin{bmatrix} x\\ y\\ z \end{bmatrix} = \begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix}^{-1} \begin{bmatrix} \alpha\\ \beta\\ \gamma \end{bmatrix} \]On doit donc inverser une matrice $3\times 3$. On commence par calculer son déterminant:
\[ \begin{vmatrix} a & b & c\\ d & e & f\\ g & h & i \end{vmatrix} =(-1)^{(1+1)} \,a \begin{vmatrix} e & f\\ h & i \end{vmatrix} +(-1)^{(1+2)} \,b \begin{vmatrix} d & f\\ g & i \end{vmatrix} +(-1)^{(1+3)} \,c \begin{vmatrix} e & f\\ h & i \end{vmatrix} \]Sachant que
\[ \begin{vmatrix} e & f\\ h & i \end{vmatrix} = ei - hf \]pour calculer le déterminant d'une matrice $3\times 3$, on doit réaliser 3 fois le même groupe d'opérations :
Au bout de ce premier compte, le calcul d'un déterminant d'une matrice $3\times3$ nécessite : 4 multiplications pour le premier bloc, cinq multiplications pour le second, six pour le troisième, 3 soustractions ---~1 par bloc~--- et deux additions soit 20 opérations. Maintenant, il faut calculer les matrices des cofacteurs de la matrice initiale soit
\[ \begin{bmatrix} \begin{vmatrix} e & f \\ h & i \end{vmatrix}&\begin{vmatrix} d & f \\ g & i \end{vmatrix}& \begin{vmatrix} d & e \\ g & h \end{vmatrix}\\\\ \begin{vmatrix} b & c \\ h & i \end{vmatrix}& \begin{vmatrix} a & c \\ g & i \end{vmatrix}& \begin{vmatrix} a & b \\ g & h \end{vmatrix}\\\\ \begin{vmatrix} b & e \\ c & f \end{vmatrix}& \begin{vmatrix} a & d \\ c & f \end{vmatrix}& \begin{vmatrix} a & b \\ d & e \end{vmatrix} \end{bmatrix} \]Chaque terme de la matrice des cofacteurs rajoute 2 multiplications et une addition et comme il y en a 9, ce calcul revient à effectuer 18 multiplications et 9 additions. Maintenant, il faut la transposer ce qui revient à 9 opérations et pour finir diviser chaque terme par le déterminant, soit encore 9 divisions. Au bout du compte, on a effectué : 18 multiplications, 3 soustractions, 9 additions, 9 divisions et 1 transpositions qui correspond à 9 permutations.
Mais cette présentation cache la montagne: les multiplications et donc les divisions, prennent beaucoup plus de temps calcul qu'une addition (une soustraction) et une transposition. En réfléchissant bien, une multiplication de deux nombreux à deux digits (le digit est un symbole, par exemple, un chiffre indo-arabique, utilisé pour l'écriture d'un nombre, en numération de position), par exemple $15 \times 16$, correspond à 7 opérations ($6 \times 15$ correspond à 2 opérations et $1\times 16$ aussi, l'addition de leur résultat correspond à 3 opérations).
Que se passe-t-il si on rajoute un digit à chaque nombre ? Ce nouveau digit doit être multiplié par tous les digits qui composent l'autre nombre. Pour arriver à multiplier plusieurs nombres composés de plus de chiffres, nous devons considérer que l'ajout d'un autre chiffre signifie que nous avons maintenant à multiplier ce chiffre par tous les autres chiffres dans l'autre nombre. Si la multiplication de deux nombres à deux digits donne $2^2=4$ opérations de multiplication, la multiplication de deux nombres de $n$ digits nécessitera $n^2$ opérations. Une fois les multiplications achevées, on aura deux nombres à $2 n$ digits que l'on devra additionner, ce qui fait $4 n$ opérations. Finalement, la multiplication de deux nombres à $n$ digits nécessite $n^2 + 4 n$ opérations (on remarque que pour $n = 2$, la formule donne 8 multiplications alors que dans l'exemple, on en a eu que $7$. C'est parce toutes les multiplications de deux nombres à deux digits ne donnent pas un nombre à 4 digits. Par exemple, $32 \times 31 = 992$ alors que $32\times 32 = 1024$.). Comparé aux $n$ opérations que prend l'addition, la multiplication est extrêmement coûteuse. Bien entendu, les nombres stockés dans un ordinateur le sont en notation binaire et le coût de la multiplication n'est pas vraiment décrit par l'équation présentée ci-dessus. Mais le message est assez clair : il est nécessaire, quand on le peut, de diminuer ses occurrences. C'est pourquoi depuis deux siècles, mais surtout depuis l'arrivée des ordinateurs, les mathématiciens ont essayé de repenser les opérations de manière à ce qu'elles soient le moins coûteuse en temps (surtout quand le programme qui doit être calculé en évalue un très grand nombre).
Les efforts des informaticiens ont été concentrés sur cette économie de temps. Par exemple, si on effectue la multiplication suivante $125467\times 256174=32141383258$ d'après la formule précédente, il sera nécessaire de réaliser $6^2 = 36$ multiplications. \citet{KaratsubaOfman63}\sindex[aut]{Karatsuba A. A.}\sindex[aut]{Ofman Y.} ont trouvé un moyen plus économe. On note tout d'abord que ces deux nombres peuvent s'écrire sous la forme $(a \times 10^3) + b$ (i.e. : $(125\times 1000)+ 467$ pour le premier et $(256 \times 1000) + 174$ pour le second). Leur produit prend donc la forme :
\[ (a_1 \times 10^3+ b_1)\times (a_2 \times 10^3+ b_2) = (a_1 a_2) 10^{2\times 3} + (a_1 b_1+ b_1 a_2) 10^3 +( b_1 b_2) \]A priori, cette multiplication nécessite 4 multiplications $a_1 a_2$, $a_1b_1$, $b_1 a_2$ et $b_1 b_2$, sachant que le découpage en puissance de 10 est arbitraire et que, de ce fait, les puissance de 10 peuvent être stockées à l'avance ce qui ne demande aucun temps-machine. En réalité, il est possible de n'avoir recours qu'à 3 multiplications ($a_1 a_2$, $b_1 b_2$ et $(a_1-b_1)(a_2 -b_2)$), si on note que :
\[ a_1 a_2+ b_1 b_2 -(a_1 - b_1)(a_2-b_2) \]De la sorte, pour réaliser la multiplication précédente, on posera : $a_1 = 125$, $a_2 = 256$, $b_1 = 467$ et $b_2 = 174$ et on calculera :
\[ \begin{array}{l} a_1 a_2 =32000\\ b_1b_2 =81258\\ (a_1-b_1)(a_2 -b_2) = (125-256)(467-174) =-28\ 044 \end{array} \]ce qui permet d'écrire :
\[ 125467\times 256174 = 32000 \times 10^6 +(3200+81258+28044)\times 10^3+81258=32141383258 \]Tout cela n'est évidemment pas fait pour être réalisé à la main. Mais de toute évidence, quand on cherche à gagner du temps machine cela a une importance. Bien entendu, ce qui peut apparaître comme une chicanerie informatique s'est développé à une époque où les ordinateurs étaient peu puissants et où le principal terminal d'entrée était constitué de cartes perforées. Il était très important de gagner du temps et d'éviter des manipulation Mais, il ne faut pas croire que c'est un passé totalement disparu. Depuis, les demandes de calculs ont été accrues exponentiellement et les calculs sont souvent d'une dimension sans commune mesure avec ce qu'ils étaient dans les années 1960.
D'ailleurs, très peu de temps après la publication de l'algorithme de Karatsuba et Ofman, \citet{Toom63}\sindex[aut]{Toom A. L.} puis \citet{Cook66}\sindex[aut]{Cook S. A.} ont encore amélioré la méthode.
Soit le vecteur
\[ \boldsymbol{a} = \begin{bmatrix} 1 & 2 & 3 & 4 \end{bmatrix} \]et les matrices
\[ \boldsymbol{B}= \begin{bmatrix} 2 & 4 & 6 & 8\\ 1 & 3 & 7 & 2\\ 5 & 2 & 6 & 1\\ 1 & 1 & 3 & 5 \end{bmatrix}\hspace{.25cm}\text{et}\hspace{.25cm} \boldsymbol{C}= \begin{bmatrix} 4 & 3 & 5\\ 2 & 1 & 1\\ 7 & 1 & 2\\ 1 & 3 & 4 \end{bmatrix} \]