Algorithme de Freivalds
# 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})$. 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(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^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^2)$ qui bat l'algorithme déterministe classique en $O(n^3).$ 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.

