# Freivald's algorithm

﻿
Freivald's algorithm

Freivald's algorithm is a randomized algorithm used to verify matrix multiplication. Given three "n" x "n" matrices "A", "B", and "C", a general problem is to verify whether "A" x "B" = "C". A naïve algorithm would compute the product "A" x "B" explicitly and compare term by term whether this product equals "C". However, this approach takes O("n"3) time. To resolve this, Freivald's algorithm utilizes randomization in order to reduce this time bound to O("n"2).

The Algorithm

Input

Three "n" x "n" matrices "A", "B", "C".

Output

Yes, if "A" x "B" = "C"; No, otherwise.

Procedure

1. Generate an "n" x 1 random 0/1 vector $vec\left\{r\right\}$.
2. Compute $vec\left\{P\right\} = A imes \left(B vec\left\{r\right\}\right) - Cvec\left\{r\right\}$.
3. Output "Yes" if $vec\left\{P\right\} = \left(0,0,ldots,0\right)^T$; "No," otherwise.

Error Analysis

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

="A" x "B" = "C"=

If "A" x "B" = "C", then "A" x "B" − "C" = 0, and so $vec\left\{P\right\} = A imes \left(B vec\left\{r\right\}\right) - C vec\left\{r\right\} = \left(A imes B\right)vec\left\{r\right\} - Cvec\left\{r\right\} = \left(A imes B - C\right)vec\left\{r\right\} = vec\left\{0\right\}$, regardless of what our vector $vec\left\{r\right\}$ was.

"A" x "B" ≠ "C"

Let $D = A imes B - C = \left(d_\left\{ij\right\}\right)$, so $vec\left\{P\right\} = D imes vec\left\{r\right\} = \left(p_1, p_2, ..., p_n\right)^T$.Since "A" x "B" ≠ "C", we have "A" x "B" − "C" ≠ 0, so some element of "D" is nonzero.

Suppose that the element $d_\left\{ij\right\} eq 0$. By the definition of matrix multiplication, we have $p_i = sum_\left\{k = 1\right\}^n d_\left\{ik\right\}r_k =$

d_{i1}r_1 + ldots + d_{ij}r_j + ldots + d_{in}r_n = d_{ij}r_j + y.

Using Bayes' Theorem, we have $Pr \left[p_i = 0\right] = Pr \left[p_i = 0 | y = 0\right] cdot Pr \left[y = 0\right] + Pr \left[p_i = 0 | y eq 0\right] cdot Pr \left[y eq 0\right]$.

Also, note that::$Pr \left[p_i = 0 | y = 0\right] = Pr \left[r_j = 0\right] = frac\left\{1\right\}\left\{2\right\}$:$Pr \left[p_i = 0 | y eq 0\right] leq Pr \left[r_j = 1\right] = frac\left\{1\right\}\left\{2\right\}$

Plugging these in the above equation, we have:

:$Pr \left[p_i = 0\right] leq frac\left\{1\right\}\left\{2\right\}cdot Pr \left[y = 0\right] + frac\left\{1\right\}\left\{2\right\}cdot Pr \left[y eq 0\right]$:$Pr \left[p_i = 0\right] leq frac\left\{1\right\}\left\{2\right\}cdot Pr \left[y = 0\right] + frac\left\{1\right\}\left\{2\right\}cdot \left(1 - Pr \left[y = 0\right] \right)$:$Pr \left[p_i = 0\right] leq frac\left\{1\right\}\left\{2\right\}$

Therefore, :$Pr \left[vec\left\{P\right\} = 0\right] leq Pr \left[p_i = 0\right] leq frac\left\{1\right\}\left\{2\right\}$.This completes the proof.

Ramifications

Simple algorithmic analysis shows that the running time of this algorithm is O("n"2), beating the classical deterministic algorithm's bound of O("n"3). The error analysis also shows that if we run our algorithm "k" times, we can achieve an error bound of less than $frac\left\{1\right\}\left\{2^k\right\}$, an exponentially small quantity. Therefore, utilization of randomized algorithms can speed up a very slow deterministic algorithm. In fact, the best known deterministic matrix multiplication verification algorithm known at the current time is the Coppersmith-Winograd algorithm with an asymptotic running time of O("n"2.376).

Wikimedia Foundation. 2010.