Freivalds' algorithm is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n x n matrices, Freivalds' algorithm determines in O(kn^2) whether the matrices are equal for a chosen k value with a probability of failure less than 2^-k.
This algorithm demonstrate that to verify if a matrix multiplication is correct, we can do better than re-running matrix multiplication which takes O(N^3) in general.
Read this article to understand the intuition behind this wonderful algorithm
Freivalds’ algorithm, nicely, illustrates the superiority of probabilistic algorithms in practice for some problems.
Have a doubt or thought? Join the discussion below
This is a companion discussion topic for the original entry at http://iq.opengenus.org/freivalds-algorithm/