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{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"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{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).


Wikimedia Foundation. 2010.