Freivalds' algorithm

Freivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices A {displaystyle A} , B {displaystyle B} , and C {displaystyle C} , a general problem is to verify whether A × B = C {displaystyle A imes B=C} . A naïve algorithm would compute the product A × B {displaystyle A imes B} explicitly and compare term by term whether this product equals C {displaystyle C} . However, the best known matrix multiplication algorithm runs in O ( n 2.3729 ) {displaystyle O(n^{2.3729})} time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to O ( n 2 ) {displaystyle O(n^{2})} with high probability. In O ( k n 2 ) {displaystyle O(kn^{2})} time the algorithm can verify a matrix product with probability of failure less than 2 − k {displaystyle 2^{-k}} . Pr [ p i = 0 ] = Pr [ p i = 0 | y = 0 ] ⋅ Pr [ y = 0 ] + Pr [ p i = 0 | y ≠ 0 ] ⋅ Pr [ y ≠ 0 ] {displaystyle Pr=Prcdot Pr,+,Prcdot Pr}     (1) Freivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices A {displaystyle A} , B {displaystyle B} , and C {displaystyle C} , a general problem is to verify whether A × B = C {displaystyle A imes B=C} . A naïve algorithm would compute the product A × B {displaystyle A imes B} explicitly and compare term by term whether this product equals C {displaystyle C} . However, the best known matrix multiplication algorithm runs in O ( n 2.3729 ) {displaystyle O(n^{2.3729})} time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to O ( n 2 ) {displaystyle O(n^{2})} with high probability. In O ( k n 2 ) {displaystyle O(kn^{2})} time the algorithm can verify a matrix product with probability of failure less than 2 − k {displaystyle 2^{-k}} . Three n × n matrices A {displaystyle A} , B {displaystyle B} , and C {displaystyle C} . Yes, if A × B = C {displaystyle A imes B=C} ; No, otherwise. If A × B = C {displaystyle A imes B=C} , then the algorithm always returns 'Yes'. If A × B ≠ C {displaystyle A imes B eq C} , then the probability that the algorithm returns 'Yes' is less than or equal to one half. This is called one-sided error. By iterating the algorithm k times and returning 'Yes' only if all iterations yield 'Yes', a runtime of O ( k n 2 ) {displaystyle O(kn^{2})} and error probability of ≤ 1 / 2 k {displaystyle leq 1/2^{k}} is achieved.