随机算法 (Fall 2011)/Verifying Matrix Multiplication: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
Created page with 'Consider the following problem: * Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>, * check whether <math>C=AB</math>. We could compu…'
 
imported>WikiSysop
No edit summary
Line 1: Line 1:
= Freivalds Algorithm for Verifying Matrix Multiplication=
Consider the following problem:
Consider the following problem:
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* Given as the input three <math>n\times n</math> matrices <math>A,B</math> and <math>C</math>,
* check whether <math>C=AB</math>.
* check whether <math>C=AB</math>.


We could compute <math>AB</math> and compare the result to <math>C</math>. The time complexity of fastest matrix multiplication algorithm (in theory) is <math>O(n^{2.376})</math>, and so is the time complexity of this method.
We could compute <math>AB</math> and compare the result to <math>C</math>. The (asymptotically) fastest matrix multiplication algorithm today runs in time <math>O(n^{2.376})</math>. Our algorithm will take the same time.


Here’s a very simple randomized algorithm, due to Freivalds, that runs in only <math>O(n^2)</math> time:
Here’s a very simple randomized algorithm, due to Freivalds, running in only <math>O(n^2)</math> time:


{{Theorem|Algorithm (Freivalds)|
{{Theorem|Algorithm (Freivalds)|
Line 11: Line 12:
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
*if <math>A(Br) = Cr</math> then return "yes" else return "no";
}}
}}
The running time of the algorithm is <math>O(n^2)</math> because it does only 3 matrix-vector multiplications.  
The product <math>A(Br)</math> is computed by first multiplying <math>Br</math> and then <math>A(Br)</math>.
The running time is <math>O(n^2)</math> because the algorithm does 3 matrix-vector multiplications in total.  


If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm always returns "yes". But if <math>AB \neq C</math> then the algorithm will make a mistake if it happens to choose an <math>r</math> for which <math>ABr = Cr</math>. This, however, is unlikely:
If <math>AB=C</math> then <math>A(Br) = Cr</math> for any <math>r \in\{0, 1\}^n</math>, thus the algorithm will return a "yes" for any positive instance (<math>AB=C</math>).  
But if <math>AB \neq C</math> then the algorithm will make a mistake if it chooses such an <math>r</math> that <math>ABr = Cr</math>. However, the following lemma states that the probability of this event is bounded.


{{Theorem|Lemma|
{{Theorem|Lemma|
Line 19: Line 22:
::<math>\Pr[ABr = Cr]\le \frac{1}{2}</math>.
::<math>\Pr[ABr = Cr]\le \frac{1}{2}</math>.
}}
}}
{{Proof| Let <math>D=AB-C</math>. We will show that if <math>D\neq \boldsymbol{0}</math>, then <math>\Pr[Dr = \boldsymbol{0}]\le \frac{1}{2}</math> for a uniform random <math>r \in\{0, 1\}^n</math>.
{{Proof| Let <math>D=AB-C</math>. The event <math>ABr=Cr</math> is equivalent to that <math>Dr=0</math>. It is then sufficient to show that for a <math>D\neq \boldsymbol{0}</math>, it holds that <math>\Pr[Dr = \boldsymbol{0}]\le \frac{1}{2}</math> for a uniform random <math>r \in\{0, 1\}^n</math>.


Since <math>D\neq \boldsymbol{0}</math>, it must have at least one non-zero entry, say <math>D(i,j)\neq 0</math>. The <math>i</math>-th entry of <math>Dr</math> is
Since <math>D\neq \boldsymbol{0}</math>, it must have at least one non-zero entry. Suppose that <math>D(i,j)\neq 0</math>.
:<math>(Dr)_i=\sum_{k=1}^nD(i,k)r_k</math>.
 
If to the contrary, <math>Dr=\boldsymbol{0}</math>, then <math>(Dr)_i=\sum_{k=1}^nD(i,k)r_k=0</math>, which is equivalent to that
We assume the event that <math>Dr=\boldsymbol{0}</math>. In particular, the <math>i</math>-th entry of <math>Dr</math> is  
:<math>r_j=-\frac{1}{D(i,j)}\sum_{k\neq j}^nD(i,k)r_k</math>,
:<math>(Dr)_{i}=\sum_{k=1}^nD(i,k)r_k=0.</math>  
i.e. once <math>r_k</math> for <math>k\neq j</math> have been chosen, there is only '''one''' value of <math>r_j</math> that would give us a zero <math>Dr</math>. However, there are '''two''' possible values <math>\{0,1\}</math> for <math>r_j</math> which are equal-probable, so with at least <math>\frac{1}{2}</math> probability, the choice of <math>r</math> fails to give us a zero <math>Dr</math>.
The <math>r_j</math> can be calculated by
:<math>r_j=-\frac{1}{D(i,j)}\sum_{k\neq j}^nD(i,k)r_k.</math>
Once all <math>r_k</math> where <math>k\neq j</math> are fixed, there is a unique solution of <math>r_j</math>. That is to say, conditioning on any <math>r_k, k\neq j</math>, there is at most '''one''' value of <math>r_j\in\{0,1\}</math> satisfying <math>Dr=0</math>. On the other hand, observe that <math>r_j</math> is chosen from '''two''' values <math>\{0,1\}</math> uniformly and independently at random. Therefore, with at least <math>\frac{1}{2}</math> probability, the choice of <math>r</math> fails to give us a zero <math>Dr</math>. That is, <math>\Pr[ABr=Cr]=\Pr[Dr=0]\le\frac{1}{2}</math>.
}}
}}

Revision as of 00:30, 22 July 2011

Freivalds Algorithm for Verifying Matrix Multiplication

Consider the following problem:

  • Given as the input three [math]\displaystyle{ n\times n }[/math] matrices [math]\displaystyle{ A,B }[/math] and [math]\displaystyle{ C }[/math],
  • check whether [math]\displaystyle{ C=AB }[/math].

We could compute [math]\displaystyle{ AB }[/math] and compare the result to [math]\displaystyle{ C }[/math]. The (asymptotically) fastest matrix multiplication algorithm today runs in time [math]\displaystyle{ O(n^{2.376}) }[/math]. Our algorithm will take the same time.

Here’s a very simple randomized algorithm, due to Freivalds, running in only [math]\displaystyle{ O(n^2) }[/math] time:

Algorithm (Freivalds)
  • pick a vector [math]\displaystyle{ r \in\{0, 1\}^n }[/math] uniformly at random;
  • if [math]\displaystyle{ A(Br) = Cr }[/math] then return "yes" else return "no";

The product [math]\displaystyle{ A(Br) }[/math] is computed by first multiplying [math]\displaystyle{ Br }[/math] and then [math]\displaystyle{ A(Br) }[/math]. The running time is [math]\displaystyle{ O(n^2) }[/math] because the algorithm does 3 matrix-vector multiplications in total.

If [math]\displaystyle{ AB=C }[/math] then [math]\displaystyle{ A(Br) = Cr }[/math] for any [math]\displaystyle{ r \in\{0, 1\}^n }[/math], thus the algorithm will return a "yes" for any positive instance ([math]\displaystyle{ AB=C }[/math]). But if [math]\displaystyle{ AB \neq C }[/math] then the algorithm will make a mistake if it chooses such an [math]\displaystyle{ r }[/math] that [math]\displaystyle{ ABr = Cr }[/math]. However, the following lemma states that the probability of this event is bounded.

Lemma
If [math]\displaystyle{ AB\neq C }[/math] then for a uniformly random [math]\displaystyle{ r \in\{0, 1\}^n }[/math],
[math]\displaystyle{ \Pr[ABr = Cr]\le \frac{1}{2} }[/math].
Proof.
Let [math]\displaystyle{ D=AB-C }[/math]. The event [math]\displaystyle{ ABr=Cr }[/math] is equivalent to that [math]\displaystyle{ Dr=0 }[/math]. It is then sufficient to show that for a [math]\displaystyle{ D\neq \boldsymbol{0} }[/math], it holds that [math]\displaystyle{ \Pr[Dr = \boldsymbol{0}]\le \frac{1}{2} }[/math] for a uniform random [math]\displaystyle{ r \in\{0, 1\}^n }[/math].

Since [math]\displaystyle{ D\neq \boldsymbol{0} }[/math], it must have at least one non-zero entry. Suppose that [math]\displaystyle{ D(i,j)\neq 0 }[/math].

We assume the event that [math]\displaystyle{ Dr=\boldsymbol{0} }[/math]. In particular, the [math]\displaystyle{ i }[/math]-th entry of [math]\displaystyle{ Dr }[/math] is

[math]\displaystyle{ (Dr)_{i}=\sum_{k=1}^nD(i,k)r_k=0. }[/math]

The [math]\displaystyle{ r_j }[/math] can be calculated by

[math]\displaystyle{ r_j=-\frac{1}{D(i,j)}\sum_{k\neq j}^nD(i,k)r_k. }[/math]

Once all [math]\displaystyle{ r_k }[/math] where [math]\displaystyle{ k\neq j }[/math] are fixed, there is a unique solution of [math]\displaystyle{ r_j }[/math]. That is to say, conditioning on any [math]\displaystyle{ r_k, k\neq j }[/math], there is at most one value of [math]\displaystyle{ r_j\in\{0,1\} }[/math] satisfying [math]\displaystyle{ Dr=0 }[/math]. On the other hand, observe that [math]\displaystyle{ r_j }[/math] is chosen from two values [math]\displaystyle{ \{0,1\} }[/math] uniformly and independently at random. Therefore, with at least [math]\displaystyle{ \frac{1}{2} }[/math] probability, the choice of [math]\displaystyle{ r }[/math] fails to give us a zero [math]\displaystyle{ Dr }[/math]. That is, [math]\displaystyle{ \Pr[ABr=Cr]=\Pr[Dr=0]\le\frac{1}{2} }[/math].

[math]\displaystyle{ \square }[/math]