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 , , and , 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 time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to
with high probability. In time the algorithm can verify a matrix product with probability of failure less than .

Three n × n matrices , , and .

Yes, if ; No, otherwise.

Generate an n × 1 random 0/1 vector Compute Output "Yes" if ; "No," otherwise.

If , then the algorithm always returns "Yes". If , 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 and error probability of is achieved.

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.

This is regardless of the value of , since it uses only that Hence the probability for error in this case is:

Simple algorithmic analysis shows that the running time of this algorithm is (in big O notation). This beats the classical deterministic algorithm's runtime of (or 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.