Freivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices
Contents
Input
Three n × n matrices
Output
Yes, if
Procedure
- Generate an n × 1 random 0/1 vector
r → - Compute
P → = A × ( B r → ) − C r → - Output "Yes" if
P → = ( 0 , 0 , … , 0 ) T
Error
If
By iterating the algorithm k times and returning "Yes" only if all iterations yield "Yes", a runtime of
Example
Suppose one wished to determine whether:
A random two-element vector with entries equal to 0 or 1 is selected — say
This yields the zero vector, suggesting the possibility that AB = C. However, if in a second trial the vector
The result is nonzero, proving that in fact AB ≠ C.
There are four two-element 0/1 vectors, and half of them give the zero vector in this case (
Error analysis
Let p equal the probability of error. We claim that if A × B = C, then p = 0, and if A × B ≠ C, then p ≤ 1/2.
Case A × B = C
This is regardless of the value of
Case A × B ≠ C
Let
Where
Since
For some constant
We use that:
Plugging these in the equation (1), we get:
Therefore,
This completes the proof.
Ramifications
Simple algorithmic analysis shows that the running time of this algorithm is O(n2), beating the classical deterministic algorithm's bound of O(n3). The error analysis also shows that if we run our algorithm k times, we can achieve an error bound of less than
Freivalds' algorithm frequently arises in introductions to probabilistic algorithms due to its simplicity and how it illustrates the superiority of probabilistic algorithms in practice for some problems.