Freivalds’ algorithm for verifying Matrix Multiplication

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
1 Like