Freivalds' Algorithm - Ramifications

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, 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. In fact, the best known deterministic matrix multiplication verification algorithm known at the current time is a variant of the Coppersmith-Winograd algorithm with an asymptotic running time of O(n2.3727).

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.