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$ , de tailles respectives $m\times k,\ k\times n$ et $m\times n$ , à coefficients dans un anneau quelconque, 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 (dans le cas où les matrices sont de taille identique à n) 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(rn^{2})$ avec une probabilité d'échec inférieure à $2^{-r}$ .

Algorithme

Procédure

Le principe de l'algorithme consiste à vérifier, pour trois matrices de taille $m\times k,\ k\times n,$ et $m\times 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 de taille $n$ .
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 $r$ fois et en renvoyant Oui si et seulement si toutes les itérations renvoient Oui, la complexité temporelle du test est $O(rn^{2})$ et sa probabilité d'erreur est inférieure ou égale à $1/2^{r}$ .

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 un de ces deux vecteurs deux fois de suite (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 la formule des probabilités totales, 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, on obtient :

{\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 $r$ exécutions de l'algorithme, la probabilité d'erreur est inférieure à ${\frac {1}{2^{r}}}$ . 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.

Anneaux $\mathbb {Z} /q\mathbb {Z}$

Il pourrait être tentant de générer le vecteur aléatoire avec des composantes prises uniformément dans $\{0,\ \ldots ,\ q-1\}$ dans le cas où l'anneau de base est $\mathbb {Z} /q\mathbb {Z} ,\ q>2$ .

En effet, on pourrait penser que si le vecteur est pris dans un espace plus grand, l'égalité a encore moins de chance de se produire pour un vecteur générique.

Cependant, on a:

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

$\Pr[p_{i}=0|y\neq 0]=\bigcup _{l=1}^{q}\Pr[r_{j}=i\land d_{ij}=-ly]\leq \bigcup _{l=1}^{q}\Pr[r_{j}=l]={\frac {q-1}{q}}$

En conclusion, le test devient plus efficace seulement dans le cas où l'erreur n'intervient que sur un coefficient, mais est moins efficace dans le cas général où le produit scalaire du vecteur d'erreur $d_{i}=(d_{i1},\ \ldots ,\ d_{in})$ et du vecteur aléatoire $r_{i}$ se compense à zéro.

On détermine la probabilité du test par la formule des probabilités totales:

${\begin{aligned}\Pr[p_{i}=0]&={\frac {1}{q}}\cdot \Pr[y=0]+{\frac {q-1}{q}}\cdot \Pr[y\neq 0]\\&={\frac {1}{q^{2}}}+\left({\frac {q-1}{q}}\right)^{2}\\&>{\frac {1}{2}}\end{aligned}}$

La probabilité d'erreur de ce second test étant supérieur à ${\frac {1}{2}}$ , il est préférable de ne générer le vecteur qu'avec des composantes entre 0 et 1.

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.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.