Freivalds’ algorithm for verifying Matrix Multiplication

Internship at OpenGenus

Get FREE domain for 1st year and build your brand new site

Reading time: 30 minutes | Coding time: 12 minutes

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.

Freivalds' algorithm

  1. Input: n×n matrices A, B and C.

  2. We would like to verify if A×B=C.
    Choose a n×1 column vector r→∈{0,1}n, uniformly and at random. In other words, each component of the vector is either 0 or 1 and chosen randomly and uniformly.

  3. Compute A⋅(B⋅r) and C⋅r. This takes Θ(n^2) time.

  4. Now comes the output

    • If A⋅(B⋅r)≠C⋅r, output FALSE. In other words, we say that the given matrix multiplication is incorrect. This has a probability of correctness = 1.
    • If A⋅(B⋅r)=C⋅r, output TRUE. In other words, we say that the given matrix multiplication is correct. This has a probability of correctness ≥1/2.

Example

Let A,B,C are the matrices such that A × B = C.A random two-element vector with entries equal to 0 or 1 is selected Vector r=[1,1] .
eg1
This yields the zero vector, suggesting the possibility that AB = C. However, if in a second trial the vector r=[1,0] is selected, the result becomes:
eg2
The result is nonzero, proving that in fact AB ≠ C.
There are four two-element 0/1 vectors, and half of them give the zero vector in this case Vector r=[0,0] and r=[1,1].so the chance of randomly selecting these in two trials (and falsely concluding that AB=C) is 1/22 or 1/4. In the general case, the proportion of r yielding the zero vector may be less than 1/2, and a larger number of trials would be used, rendering the probability of error very small.

Error analysis

Let p equal the probability of error. We claim that if A × B = C, then p = 0, and if A × B ≠ C, then p ≤ 1/2.

Case A × B = C:
Regardless of the value of vector r, since it uses only that A × B - C =0. Hence the probability for error in this case would be zero.
ercase1-1
Case A × B ≠ C:
ercase21-1
Since A × B ≠ C, we have that some element of D is nonzero. Suppose that the element d≠0.For some constant y. Using Bayes' Theorem, we can partition over y.
ercase22-1

Pseudocode

  • Generate an n × 1 random 0/1 vector r.
  • Compute P = A × (Br) – Cr.
  • Return true if P = ( 0, 0, …, 0 )T, return false otherwise.

Br = matrix B multiplied by Vector r.
Cr = matrix C multiplied by Vector r.

Complexity

  • Worst case time complexity: Θ(kn^2)

  • Space complexity: Θ(n^2)
    k = number of times the algorithm iterates.

Implementations

  • C++

C++


#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main(int argc, char **argv)
{
    cout << "Enter the dimension of the matrices: " << endl;
    int n;
    cin >> n;
    cout << "Enter the 1st matrix: " << endl;
    double a[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }
    cout << "Enter the 2nd matrix: " << endl;
    double b[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> b[i][j];
        }
    }
    cout << "Enter the result matrix: " << endl;
    double c[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> c[i][j];
        }
    }
    //random generation of the r vector 
    // containing only 0/1 as its elements
    double r[n][1];
    for (int i = 0; i < n; i++)
    {
        r[i][0] = rand() % 2;
    }
    //test A * (b*r) - (C*) = 0
    double br[n][1];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 1; j++)
        {
            for (int k = 0; k < n; k++)
            {
                br[i][j] = br[i][j] + b[i][k] * r[k][j];
            }
        }
    }
    double cr[n][1];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 1; j++)
        {
            for (int k = 0; k < n; k++)
            {
                cr[i][j] = cr[i][j] + c[i][k] * r[k][j];
            }
        }
    }
    double abr[n][1];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 1; j++)
        {
            for (int k = 0; k < n; k++)
            {
                abr[i][j] = abr[i][j] + a[i][k] * br[k][j];
            }
        }
    }
    //    br = multiplyVector(b, r, n);
    //    cr = multiplyVector(c, r, n);
    //    abr = multiplyVector(a, br, n);
    //abr-cr
    for (int i = 0; i < n; i++)
    {
        abr[i][0] -= cr[i][0];
    }
    bool flag = true;
    for (int i = 0; i < n; i++)
    {
        if (abr[i][0] == 0)
            continue;
        else
            flag = false;
    }
    if (flag == true)
        cout << "True";
    else
        cout << "False";
}

Applications

  • Fingerprinting is a well known technique, which is often used in designing Monte Carlo algorithms for verifying identities involving matrices, integers and polynomials.

  • 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.

Kyatham Srikanth

Kyatham Srikanth

Software Developer at Optum | Summer Research Intern at Central Institute Of Mining & Fuel Research (2017) and OpenGenus (2018) | B. Tech (2019) at Indian Institute of Technology (IIT BHU), Varanasi

Read More

Improved & Reviewed by:


OpenGenus Foundation OpenGenus Foundation