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
,
, et
, de tailles respectives
et
, à coefficients dans un anneau quelconque, le problème est de vérifier si
. Pour le résoudre, l'algorithme naïf calcule le produit
explicitement et compare le résultat terme à terme avec
. Cependant, le meilleur algorithme connu de produit matriciel (dans le cas où les matrices sont de taille identique à n) s'exécute en temps
[1]. L'algorithme de Freivalds utilise la randomisation afin de réduire cette borne à
[2] avec une forte probabilité. Il peut vérifier un produit matriciel en temps
avec une probabilité d'échec inférieure à
.
Algorithme
Procédure
Le principe de l'algorithme consiste à vérifier, pour trois matrices de taille
et
, notées
,
et
si l'égalité
est vérifiée ou non.
On effectue alors les trois étapes :
- Générer un vecteur aléatoire
de composantes 0 ou 1 de taille
.
- Calculer
.
- Renvoyer Oui si
; Non sinon.
Erreur
Si
, alors l'algorithme retourne toujours Oui. Si
, alors la probabilité que l'algorithme retourne Oui est inférieure ou égale à 1/2.
En répétant l'algorithme
fois et en renvoyant Oui si et seulement si toutes les itérations renvoient Oui, la complexité temporelle du test est
et sa probabilité d'erreur est inférieure ou égale à
.
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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40b8b964afcdf0a656d6335c6eee3d9605409700)
Un vecteur aléatoire 2 × 1 de composantes égales à 0 ou 1 est sélectionné — par exemple,
— 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d3c195761cf6bd80066615a92dc1ce584b12f17)
Le résultat est le vecteur nul ce qui suggère la possibilité que AB = C. Toutefois, si le vecteur
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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f350143b68beb89ba227ad3c703cb97fac29c3c)
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 (
et
) 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/22 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fabd27ff04a5b967fc378a944e3a230a6d6339c)
Ce résultat est indépendant de la valeur de
car il utilise seulement l'égalité
. Par conséquent, la probabilité d'erreur est dans ce cas :
![{\displaystyle \Pr[{\vec {P}}\neq 0]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c73087a7efc162b4e75c6865e98c1d05aec25a0a)
Cas A × B ≠ C
Soit
![{\displaystyle {\vec {P}}=D\times {\vec {r}}=(p_{1},p_{2},\dots ,p_{n})^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7bbb1d0196e78bfa7347345e0b05877f8616198)
où
.
Puisque
, certaines composantes de
sont forcément non-nulles. Supposons l'élément
. Par la définition du produit matriciel, il vient :
.
pour un certain
. Par la formule des probabilités totales, on a :
.
En utilisant les résultats
![{\displaystyle \Pr[p_{i}=0|y=0]=\Pr[r_{j}=0]={\frac {1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c5a17eb0d50e08bb9a83418bf18f5ada6d2b210)
![{\displaystyle \Pr[p_{i}=0|y\neq 0]=\Pr[r_{j}=1\land d_{ij}=-y]\leq \Pr[r_{j}=1]={\frac {1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0ba405df9fd611dbb73bf7c9bf4eac801ae8a30)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac04124bbed15468913248264a3f495d919efe2e)
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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e355ff8aa8a654e52019735c8e960fc2555f859)
Ceci termine la preuve.
Complexité
Une analyse simple de cet algorithme montre une complexité en temps de O(n2) qui bat l'algorithme déterministe classique en O(n3). L'analyse de l'erreur montre qu'après
exécutions de l'algorithme, la probabilité d'erreur est inférieure à
. 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(n2.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} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/86963fd8a1f21cde4890de3cfb6f9a3e881d9b45)
Il pourrait être tentant de générer le vecteur aléatoire avec des composantes prises uniformément dans
dans le cas où l'anneau de base est
.
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:
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
et du vecteur aléatoire
se compense à zéro.
On détermine la probabilité du test par la formule des probabilités totales:
La probabilité d'erreur de ce second test étant supérieur à
, il est préférable de ne générer le vecteur qu'avec des composantes entre 0 et 1.
Voir aussi
Notes
Références
- Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, pages 839-842.
|
|
Propriétés |
|
Exemples |
|
Algorithmes de multiplication |
|
Algorithmes de vérification |
Multiplication d'entiers |
|
Multiplication de matrices |
|
|