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 , , 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 . L'algorithme de Freivalds utilise la randomisation afin de réduire cette borne à avec une forte probabilité. Il peut vérifier un produit matriciel en temps avec une probabilité d'échec inférieure à .