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 ${\displaystyle A}$, ${\displaystyle B}$, et ${\displaystyle C}$, de tailles respectives ${\displaystyle m\times k,\ k\times n}$ et ${\displaystyle m\times n}$, à coefficients dans un anneau quelconque, le problème est de vérifier si ${\displaystyle A\times B=C}$. Pour le résoudre, l'algorithme naïf calcule le produit ${\displaystyle A\times B}$ explicitement et compare le résultat terme à terme avec ${\displaystyle 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 ${\displaystyle O(n^{2.3729})}$^[1]. L'algorithme de Freivalds utilise la randomisation afin de réduire cette borne à ${\displaystyle O(n^{2})}$^[2]  avec une forte probabilité. Il peut vérifier un produit matriciel en temps ${\displaystyle O(rn^{2})}$ avec une probabilité d'échec inférieure à ${\displaystyle 2^{-r}}$.

Algorithme

Procédure

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

On effectue alors les trois étapes :

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

Erreur

Si ${\displaystyle A\times B=C}$, alors l'algorithme retourne toujours Oui. Si ${\displaystyle 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 ${\displaystyle r}$ fois et en renvoyant Oui si et seulement si toutes les itérations renvoient Oui, la complexité temporelle du test est ${\displaystyle O(rn^{2})}$ et sa probabilité d'erreur est inférieure ou égale à ${\displaystyle 1/2^{r}}$.

Exemple

Supposons qu'on souhaite vérifier si :

${\displaystyle 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, ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$ — et utilisé pour calculer :

${\displaystyle {\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 ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}}$ est sélectionné pour une deuxième itération, le résultat devient :

${\displaystyle 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 (${\displaystyle {\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}}$ et ${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle {\vec {r}}}$ car il utilise seulement l'égalité ${\displaystyle A\times B-C=0}$. Par conséquent, la probabilité d'erreur est dans ce cas :

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

Cas A × B ≠ C

Soit

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

où

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

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

${\displaystyle 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 ${\displaystyle y}$. Par la formule des probabilités totales, on a :

${\displaystyle \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

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

${\displaystyle \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 :

${\displaystyle {\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,

${\displaystyle \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 ${\displaystyle r}$ exécutions de l'algorithme, la probabilité d'erreur est inférieure à ${\displaystyle {\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 ${\displaystyle \mathbb {Z} /q\mathbb {Z} }$

Il pourrait être tentant de générer le vecteur aléatoire avec des composantes prises uniformément dans ${\displaystyle \{0,\ \ldots ,\ q-1\}}$ dans le cas où l'anneau de base est ${\displaystyle \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:

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

${\displaystyle \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 ${\displaystyle d_{i}=(d_{i1},\ \ldots ,\ d_{in})}$ et du vecteur aléatoire ${\displaystyle r_{i}}$ se compense à zéro.

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

${\displaystyle {\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 à ${\displaystyle {\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

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

• Portail de l'informatique théorique