Scribd
Upload
180 views2 pages

Freivalds' Algorithm

This document summarizes Freivalds' algorithm for verifying matrix multiplication. It begins by explaining the naive O(n^3) matrix multiplication algorithm. It then describes Freivalds' algorithm, which has O(n^2) time complexity. Freivalds' algorithm works by choosing a random vector r, computing A(Br) and Cr, and checking if they are equal. If not equal, it outputs false, otherwise it outputs true with probability at least 1/2 of being correct.

Uploaded by

Bhakti Kalyankasture
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
180 views2 pages

Freivalds' Algorithm

This document summarizes Freivalds' algorithm for verifying matrix multiplication. It begins by explaining the naive O(n^3) matrix multiplication algorithm. It then describes Freivalds' algorithm, which has O(n^2) time complexity. Freivalds' algorithm works by choosing a random vector r, computing A(Br) and Cr, and checking if they are equal. If not equal, it outputs false, otherwise it outputs true with probability at least 1/2 of being correct.

Uploaded by

Bhakti Kalyankasture
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

EE 230 Probability and random variables

Freivalds’ algorithm Report


Bhakti Laxman Kalyankasture 210108019

It is used for verifying matrix multiplication.


Naïve method:

Multiplying n*n matrices(consider n=2)

[ a b ][w x ] = [aw+by ax+bz]

[ c d ][ y z ] [cw+dy cx+dz]
Complexity of algorithm: Θ(n^3 )
Calculating time complexity:
Matrix multiplication of A, B of order n:
for i=1 to n ----O(n)
for j=1 to n ----O(n)
c[i][j]=0
for k=1 to n ----O(n)
c[i][j] = c[i][j]+a[i][k]*b[k][j]

Therefore time complexity of matrix multiplication: O(n^3)


(There are 8 multiplications here; in general, n multiplications for each of n^2 entries)

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.
Time complexity:
for i=1 to n ----O(n)
for j=1 ----O(1)
c[i][j]=0
for k=1 to n ----O(n)
c[i][j] = c[i][j]+a[i][k]*b[k][j]
therefore time complexity of Freivalds’ Algorithm is O(n^2) if we interate
k times time complexity = O(kn^2)
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.

Though it has some problems


Error analysis in Freivalds’ Algorithm:

You might also like