Utilisateur:Eneelk/Brouillon/Algorithme de Freivalds

Brouillon pour 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})$. L'algorithme de Freivalds utilise la randomisation afin de réduire cette borne à $O(n^{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

Entrée

Trois matrices n × n notées $A$, $B$ et $C$.

Sortie

Oui si $A\times B=C$ ; Non sinon.

Procédure

1. Générer un vecteur aléatoire ${\vec {r}}$ de composantes 0 ou 1.
2. Calculer ${\vec {P}}=A\times (B{\vec {r}})-C{\vec {r}}$.
3. 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 à ${\displaystyle }$ 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

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