Algorithme de Freivalds

Un article de Wikipédia, l'encyclopédie libre.

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 , 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 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[modifier | modifier le code]

Procédure[modifier | modifier le code]

Le principe de l'algorithme consiste à vérifier si, pour trois matrices n × n notées , et  si l'égalité est vérifiée ou non.

On effectue alors les trois étapes :

  1. Générer un vecteur aléatoire  de composantes 0 ou 1.
  2. Calculer .
  3. Renvoyer Oui si  ; Non sinon.

Erreur[modifier | modifier le code]

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 k 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[modifier | modifier le code]

Supposons qu'on souhaite vérifier si :

Un vecteur aléatoire 2 × 1 de composantes égales à 0 ou 1 est sélectionné — par exemple,  — et utilisé pour calculer :

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 :

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 ces deux vecteurs (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[modifier | modifier le code]

Soit p la probabilité d'erreur. Si A × B = C alors p = 0, et si A × BC alors p ≤ 1/2.

Cas A × B = C[modifier | modifier le code]

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 :

Cas A × BC[modifier | modifier le code]

Soit

.

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 le théorème de Bayes, on a :

En utilisant les résultats

dans l'équation précédente, le résultat est :

Par conséquent,

Ceci termine la preuve.

Complexité[modifier | modifier le code]

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 k 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.

Voir aussi[modifier | modifier le code]

Notes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Virginia Vassilevska Williams, « Breaking the Coppersmith-Winograd barrier »
  2. Prabhakar Raghavan, « Randomized algorithms », ACM Computing Surveys, vol. 28,‎ (DOI 10.1145/234313.234327, lire en ligne, consulté le 16 décembre 2008)
  • Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, pages 839-842.