Freivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication.
, a general problem is to verify whether
A naïve algorithm would compute the product
explicitly and compare term by term whether this product equals
However, the best known matrix multiplication algorithm runs in
[1] Freivalds' algorithm utilizes randomization in order to reduce this time bound to
time the algorithm can verify a matrix product with probability of failure less than
, 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
Suppose one wished to determine whether: A random two-element vector with entries equal to 0 or 1 is selected – say
– and used to compute: This yields the zero vector, suggesting the possibility that AB = C. However, if in a second trial the vector
is selected, the result becomes: 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 (
), so the chance of randomly selecting these in two trials (and falsely concluding that AB=C) is 1/22 or 1/4.
In the general case, the proportion of r yielding the zero vector may be less than 1/2, and a larger number of trials (such as 20) would be used, rendering the probability of error very small.
Let p equal the probability of error.
Hence the probability for error in this case is: Let
Suppose that the element
By the definition of matrix multiplication, we have: For some constant
Using Bayes' theorem, we can partition over
: We use that: Plugging these in the equation (1), we get: Therefore, This completes the proof.
Simple algorithmic analysis shows that the running time of this algorithm is
This beats the classical deterministic algorithm's runtime of
if using fast matrix multiplication).
The error analysis also shows that if the algorithm is run
times, an error bound of less than
can be achieved, an exponentially small quantity.
The algorithm is also fast in practice due to wide availability of fast implementations for matrix-vector products.
Therefore, utilization of randomized algorithms can speed up a very slow deterministic algorithm.
Freivalds' algorithm frequently arises in introductions to probabilistic algorithms because of its simplicity and how it illustrates the superiority of probabilistic algorithms in practice for some problems.