Freivald's algorithm

From Wikipedia, the free encyclopedia

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²).

1 The Algorithm
2 Error Analysis
- 2.1 A x B = C
- 2.2 A x B ≠ C
3 Ramifications

[edit] The Algorithm

[edit] Input

Three n x n matrices A, B, C.

[edit] Output

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

[edit] Procedure

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

[edit] 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.

[edit] A x B = C

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

[edit] A x B ≠ C

Let $D = A \times B - C = (d_{ij})$ , so $\vec{P} = D \times \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} \neq 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 \neq 0] \cdot Pr[y \neq 0]$ .

Also, note that:

$Pr[p_i = 0 | y = 0] = Pr[r_j = 0] = \frac{1}{2}$

$Pr[p_i = 0 | y \neq 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 \neq 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.

[edit] 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).