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"³) time. To resolve this, Freivald's algorithm utilizes randomization in order to reduce this time bound to O("n"²).

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\{r\}$.
2. Compute $vec\{P\}\; =\; A\; imes\; (B\; vec\{r\})\; -\; Cvec\{r\}$.
3. Output "Yes" if $vec\{P\}\; =\; (0,0,ldots,0)^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\{P\}\; =\; A\; imes\; (B\; vec\{r\})\; -\; C\; vec\{r\}\; =\; (A\; imes\; B)vec\{r\}\; -\; Cvec\{r\}\; =\; (A\; imes\; B\; -\; C)vec\{r\}\; =\; vec\{0\}$, regardless of what our vector $vec\{r\}$ was.

"A" x "B" ≠ "C"

Let $D\; =\; A\; imes\; B\; -\; C\; =\; (d\_\{ij\})$, so $vec\{P\}\; =\; D\; imes\; vec\{r\}\; =\; (p\_1,\; p\_2,\; ...,\; p\_n)^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\_\{ij\}\; eq\; 0$. By the definition of matrix multiplication, we have $p\_i\; =\; sum\_\{k\; =\; 1\}^n\; d\_\{ik\}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\; [p\_i\; =\; 0]\; =\; Pr\; [p\_i\; =\; 0\; |\; y\; =\; 0]\; cdot\; Pr\; [y\; =\; 0]\; +\; Pr\; [p\_i\; =\; 0\; |\; y\; eq\; 0]\; cdot\; Pr\; [y\; eq\; 0]$.

Also, note that::$Pr\; [p\_i\; =\; 0\; |\; y\; =\; 0]\; =\; Pr\; [r\_j\; =\; 0]\; =\; frac\{1\}\{2\}$:$Pr\; [p\_i\; =\; 0\; |\; y\; eq\; 0]\; leq\; Pr\; [r\_j\; =\; 1]\; =\; frac\{1\}\{2\}$

Plugging these in the above equation, we have:

:$Pr\; [p\_i\; =\; 0]\; leq\; frac\{1\}\{2\}cdot\; Pr\; [y\; =\; 0]\; +\; frac\{1\}\{2\}cdot\; Pr\; [y\; eq\; 0]$:$Pr\; [p\_i\; =\; 0]\; leq\; frac\{1\}\{2\}cdot\; Pr\; [y\; =\; 0]\; +\; frac\{1\}\{2\}cdot\; (1\; -\; Pr\; [y\; =\; 0]\; )$:$Pr\; [p\_i\; =\; 0]\; leq\; frac\{1\}\{2\}$

Therefore, :$Pr\; [vec\{P\}\; =\; 0]\; leq\; Pr\; [p\_i\; =\; 0]\; leq\; frac\{1\}\{2\}$.This completes the proof.

Ramifications

Simple algorithmic analysis shows that the running time of this algorithm is O("n"²), beating the classical deterministic algorithm's bound of O("n"³). The error analysis also shows that if we run our algorithm "k" times, we can achieve an error bound of less than $frac\{1\}\{2^k\}$, 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).