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(r{n}^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 :

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

Erreur

Si $A\times B=C$, alors l'algorithme retourne toujours Oui. Si $A\times B\ne 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(r{n}^2)$ et sa probabilité d'erreur est inférieure ou égale à $1/2^r$.

Exemple

Supposons qu'on souhaite vérifier si :

$AB=\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]\left[\begin{array}{cc}1& 0\\ 1& 2\end{array}\right]\stackrel{?}{=}\left[\begin{array}{cc}6& 5\\ 8& 7\end{array}\right]=C.$

Un vecteur aléatoire 2 × 1 de composantes égales à 0 ou 1 est sélectionné — par exemple, $\overrightarrow{r}=\left[\begin{array}{c}1\\ 1\end{array}\right]$ — et utilisé pour calculer :

$\begin{array}{cc}A\times (B\overrightarrow{r})-C\overrightarrow{r}& =\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]\left(\left[\begin{array}{cc}1& 0\\ 1& 2\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\right)-\left[\begin{array}{cc}6& 5\\ 8& 7\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\\ & =\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]\left[\begin{array}{c}1\\ 3\end{array}\right]-\left[\begin{array}{c}11\\ 15\end{array}\right]\\ & =\left[\begin{array}{c}11\\ 15\end{array}\right]-\left[\begin{array}{c}11\\ 15\end{array}\right]\\ & =\left[\begin{array}{c}0\\ 0\end{array}\right].\end{array}$

Le résultat est le vecteur nul ce qui suggère la possibilité que AB = C. Toutefois, si le vecteur $\overrightarrow{r}=\left[\begin{array}{c}1\\ 0\end{array}\right]$ est sélectionné pour une deuxième itération, le résultat devient :

$A\times (B\overrightarrow{r})-C\overrightarrow{r}=\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]\left(\left[\begin{array}{cc}1& 0\\ 1& 2\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\right)-\left[\begin{array}{cc}6& 5\\ 8& 7\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}-1\\ -1\end{array}\right].$

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 ($\overrightarrow{r}=\left[\begin{array}{c}0\\ 0\end{array}\right]$ et $\overrightarrow{r}=\left[\begin{array}{c}1\\ 1\end{array}\right]$) 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{array}{cc}\overrightarrow{P}& =A\times (B\overrightarrow{r})-C\overrightarrow{r}\\ & =(A\times B)\overrightarrow{r}-C\overrightarrow{r}\\ & =(A\times B-C)\overrightarrow{r}\\ & =\overrightarrow{0}\end{array}$

Ce résultat est indépendant de la valeur de $\overrightarrow{r}$ car il utilise seulement l'égalité $A\times B-C=0$. Par conséquent, la probabilité d'erreur est dans ce cas :

$\mathrm{Pr}[\overrightarrow{P}\ne 0]=0$

Cas A × B ≠ C

Soit

$\overrightarrow{P}=D\times \overrightarrow{r}=(p_1,p_2,\dots ,p_n{)}^T$

où

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

Puisque $A\times B\ne C$, certaines composantes de $D$ sont forcément non-nulles. Supposons l'élément $d_{ij}\ne 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 :

$\mathrm{Pr}[p_i=0]=\mathrm{Pr}[p_i=0|y=0]\cdot \mathrm{Pr}[y=0]+\mathrm{Pr}[p_i=0|y\ne 0]\cdot \mathrm{Pr}[y\ne 0]$.

En utilisant les résultats

$\mathrm{Pr}[p_i=0|y=0]=\mathrm{Pr}[r_j=0]=\frac{1}{2}$

$\mathrm{Pr}[p_i=0|y\ne 0]=\mathrm{Pr}[r_j=1\wedge d_{ij}=-y]\le \mathrm{Pr}[r_j=1]=\frac{1}{2}$

dans l'équation précédente, on obtient :

$\begin{array}{cc}\mathrm{Pr}[p_i=0]& \le \frac{1}{2}\cdot \mathrm{Pr}[y=0]+\frac{1}{2}\cdot \mathrm{Pr}[y\ne 0]\\ & =\frac{1}{2}\cdot \mathrm{Pr}[y=0]+\frac{1}{2}\cdot (1-\mathrm{Pr}[y=0])\\ & =\frac{1}{2}\end{array}$

Par conséquent,

$\mathrm{Pr}[\overrightarrow{P}=0]=\mathrm{Pr}[p_1=0\wedge \dots \wedge p_i=0\wedge \dots \wedge p_n=0]\le \mathrm{Pr}[p_i=0]\le \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,\dots ,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:

$\mathrm{Pr}[p_i=0|y=0]=\mathrm{Pr}[r_j=0]=\frac{1}{q}$

$\mathrm{Pr}[p_i=0|y\ne 0]=\bigcup _{l=1}^q\mathrm{Pr}[r_j=i\wedge d_{ij}=-ly]\le \bigcup _{l=1}^q\mathrm{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},\dots ,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{array}{cc}\mathrm{Pr}[p_i=0]& =\frac{1}{q}\cdot \mathrm{Pr}[y=0]+\frac{q-1}{q}\cdot \mathrm{Pr}[y\ne 0]\\ & =\frac{1}{q^2}+{\left(\frac{q-1}{q}\right)}^2\\ & >\frac{1}{2}\end{array}$

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

Références

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