- Freivald's algorithm
Freivald's algorithm is a
randomized algorithm used to verifymatrix multiplication . Given three "n" x "n" matrices "A", "B", and "C", a general problem is to verify whether "A" x "B" = "C". A naïvealgorithm 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 utilizesrandomization 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
- Generate an "n" x 1
random 0/1 vector vec{r}. - Compute vec{P} = A imes (B vec{r}) - Cvec{r}.
- 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 ouralgorithm "k" times, we can achieve an error bound of less than frac{1}{2^k}, an exponentially small quantity. Therefore, utilization ofrandomized algorithms can speed up a very slowdeterministic algorithm . In fact, the best known deterministic matrix multiplication verification algorithm known at the current time is theCoppersmith-Winograd algorithm with an asymptotic running time of O("n"2.376).- Generate an "n" x 1
Wikimedia Foundation. 2010.