Algorithme de Freivalds

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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.