Algorithme de Freivalds

L'algorithme de Freivalds (du nom de Rūsiņš Mārtiņš Freivalds) est un test probabiliste pour vérifier le résultat d'un produit matriciel. Étant donné trois matrices $A$ , $B$ , et $C$ , le problème est de vérifier si $A\times B=C$ . Pour le résoudre, l'algorithme naïf calcule le produit $A\times B$ explicitement et compare le résultat terme à terme avec $C$ . Cependant, le meilleur algorithme connu de produit matriciel s'exécute en temps $O(n^{2.3729})$ [1]. L'algorithme de Freivalds utilise la randomisation afin de réduire cette borne à $O(n^{2})$ [2] avec une forte probabilité. Il peut vérifier un produit matriciel en temps $O(kn^{2})$ avec une probabilité d'échec inférieure à $2^{-k}$ .

Algorithme

Procédure

Le principe de l'algorithme consiste à vérifier si, pour trois matrices n × n notées $A$ , $B$ et $C$ si l'égalité $A\times B=C$ est vérifiée ou non.

On effectue alors les trois étapes :

Générer un vecteur aléatoire ${\vec {r}}$ de composantes 0 ou 1.
Calculer ${\vec {P}}=A\times (B{\vec {r}})-C{\vec {r}}$ .
Renvoyer Oui si ${\vec {P}}=(0,0,\ldots ,0)^{T}$ ; Non sinon.

Erreur

Si $A\times B=C$ , alors l'algorithme retourne toujours Oui. Si $A\times B\neq C$ , alors la probabilité que l'algorithme retourne Oui est inférieure ou égale à 1/2.

En répétant l'algorithme k fois et en renvoyant Oui si et seulement si toutes les itérations renvoient Oui, la complexité temporelle du test est $O(kn^{2})$ et sa probabilité d'erreur est inférieure ou égale à $1/2^{k}$ .

Exemple

Supposons qu'on souhaite vérifier si :

AB={\begin{bmatrix}2&3\\3&4\end{bmatrix}}{\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\stackrel {?}{=}}{\begin{bmatrix}6&5\\8&7\end{bmatrix}}=C.

Un vecteur aléatoire 2 × 1 de composantes égales à 0 ou 1 est sélectionné — par exemple, ${\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}$ — et utilisé pour calculer :

{\begin{aligned}A\times (B{\vec {r}})-C{\vec {r}}&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\1\end{bmatrix}}\\&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}{\begin{bmatrix}1\\3\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}11\\15\end{bmatrix}}-{\begin{bmatrix}11\\15\end{bmatrix}}\\&={\begin{bmatrix}0\\0\end{bmatrix}}.\end{aligned}}

Le résultat est le vecteur nul ce qui suggère la possibilité que AB = C. Toutefois, si le vecteur ${\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}$ est sélectionné pour une deuxième itération, le résultat devient :

A\times (B{\vec {r}})-C{\vec {r}}={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\left({\begin{bmatrix}1&0\\1&2\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}\right)-{\begin{bmatrix}6&5\\8&7\end{bmatrix}}{\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}-1\\-1\end{bmatrix}}.

Le résultat n'est plus nul ce qui prouve que AB ≠ C.

Il existe quatre vecteurs 0/1 à deux composantes. La moitié d'entre eux mène au vecteur nul ( ${\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}$ et ${\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}$ ) de sorte que la probabilité de choisir aléatoirement ces deux vecteurs (et donc de conclure à tort que AB=C) est de 1/2² ou 1/4. Dans le cas général, la proportion de vecteurs r menant au vecteur nul peut être inférieure à 1/2. Un grand nombre d'essais est effectué de manière à rendre la probabilité d'erreur très faible.

Probabilité d'erreur

Soit p la probabilité d'erreur. Si A × B = C alors p = 0, et si A × B ≠ C alors p ≤ 1/2.

Cas A × B = C

{\begin{aligned}{\vec {P}}&=A\times (B{\vec {r}})-C{\vec {r}}\\&=(A\times B){\vec {r}}-C{\vec {r}}\\&=(A\times B-C){\vec {r}}\\&={\vec {0}}\end{aligned}}

Ce résultat est indépendant de la valeur de ${\vec {r}}$ car il utilise seulement l'égalité $A\times B-C=0$ . Par conséquent, la probabilité d'erreur est dans ce cas :

\Pr[{\vec {P}}\neq 0]=0

Cas A × B ≠ C

Soit

{\vec {P}}=D\times {\vec {r}}=(p_{1},p_{2},\dots ,p_{n})^{T}

où

D=A\times B-C=(d_{ij})

.

Puisque $A\times B\neq C$ , certaines composantes de $D$ sont forcément non-nulles. Supposons l'élément $d_{ij}\neq 0$ . Par la définition du produit matriciel, il vient :

p_{i}=\sum _{k=1}^{n}d_{ik}r_{k}=d_{i1}r_{1}+\cdots +d_{ij}r_{j}+\cdots +d_{in}r_{n}=d_{ij}r_{j}+y

.

pour un certain $y$ . Par le théorème de Bayes, on a :

\Pr[p_{i}=0]=\Pr[p_{i}=0|y=0]\cdot \Pr[y=0]\,+\,\Pr[p_{i}=0|y\neq 0]\cdot \Pr[y\neq 0]

En utilisant les résultats

\Pr[p_{i}=0|y=0]=\Pr[r_{j}=0]={\frac {1}{2}}

\Pr[p_{i}=0|y\neq 0]=\Pr[r_{j}=1\land d_{ij}=-y]\leq \Pr[r_{j}=1]={\frac {1}{2}}

dans l'équation précédente, le résultat est :

{\begin{aligned}\Pr[p_{i}=0]&\leq {\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot \Pr[y\neq 0]\\&={\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot (1-\Pr[y=0])\\&={\frac {1}{2}}\end{aligned}}

Par conséquent,

\Pr[{\vec {P}}=0]=\Pr[p_{1}=0\land \dots \land p_{i}=0\land \dots \land p_{n}=0]\leq \Pr[p_{i}=0]\leq {\frac {1}{2}}.

Ceci termine la preuve.

Complexité

Une analyse simple de cet algorithme montre une complexité en temps de O(n²) qui bat l'algorithme déterministe classique en O(n³). L'analyse de l'erreur montre qu'après k exécutions de l'algorithme, la probabilité d'erreur est inférieure à ${\frac {1}{2^{k}}}$ . Dans la pratique, l'algorithme est rapide en raison d'implémentations efficaces du calcul d'un produit matrice-vecteur. Par conséquent, l'utilisation des algorithmes randomisés peut accélérer un algorithme déterministe lent. Le meilleur algorithme déterministe pour la vérification du produit matriciel est à l'heure actuelle une variante de l'algorithme de Coppersmith-Winograd avec un temps d'exécution asymptotique en O(n^2.3729).

L'algorithme de Freivalds apparaît souvent dans les introductions aux algorithmes probabilistes grâce à sa simplicité. En pratique, il illustre également la supériorité des algorithmes probabilistes dans certains problèmes.

Voir aussi

Lemme de Schwartz-Zippel

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Freivalds' algorithm » (voir la liste des auteurs).

Références

Virginia Vassilevska Williams, « Breaking the Coppersmith-Winograd barrier »
Prabhakar Raghavan, « Randomized algorithms », ACM Computing Surveys, vol. 28,‎ 1997 (DOI 10.1145/234313.234327, lire en ligne, consulté le 16 décembre 2008)

Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, pages 839-842.

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[williams-1] Virginia Vassilevska Williams, « Breaking the Coppersmith-Winograd barrier »

[2] Prabhakar Raghavan, « Randomized algorithms », ACM Computing Surveys, vol. 28,‎ 1997 (DOI 10.1145/234313.234327, lire en ligne, consulté le 16 décembre 2008)