Freivalds' Algorithm

Freivalds' algorithm (named after Rusins Freivalds) is a randomized algorithm used to verify matrix multiplication. Given three n × n matrices A, B, and C, a general problem is to verify whether A × B = C. A naïve algorithm would compute the product A × B explicitly and compare term by term whether this product equals C. However, even using the best known matrix multiplication algorithm, the best bound that can be attained for this approach is O(n2.3727) time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to O(n2).