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