Freivalds' algorithm [SEP] named after
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 formula_1, formula_2, and formula_3, a general problem is to verify whether formula_4. A naïve algorithm would compute the product formula_5 explicitly and compare term by term whether this product equals formula_3. However, the best known matrix multiplication algorithm runs in formula_7 time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to formula_8
).
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.
See also.
- Schwartz–Zippel lemma
References.
- Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, pp. 839–842.