A
B
C
A x B=C
A x B
C
O(n2.3729)
O(n2)
O(kn2)
2-k
A
B
C
Yes, if
A x B=C
\vec{r}
\vec{P}=A x (B\vec{r})-C\vec{r}
\vec{P}=(0,0,\ldots,0)T
If
A x B=C
A x B ≠ C
By iterating the algorithm k times and returning "Yes" only if all iterations yield "Yes", a runtime of
O(kn2)
\leq1/2k
Suppose one wished to determine whether:
AB= \begin{bmatrix} 2&3\\ 3&4 \end{bmatrix} \begin{bmatrix} 1&0\\ 1&2 \end{bmatrix} \stackrel{?}{=} \begin{bmatrix} 6&5\\ 8&7 \end{bmatrix} =C.
\vec{r}=\begin{bmatrix}1\ 1\end{bmatrix}
\begin{align} A x (B\vec{r})-C\vec{r}&= \begin{bmatrix} 2&3\\ 3&4 \end{bmatrix} \left(\begin{bmatrix} 1&0\\ 1&2 \end{bmatrix} \begin{bmatrix}1\ 1\end{bmatrix} \right) - \begin{bmatrix} 6&5\\ 8&7 \end{bmatrix} \begin{bmatrix}1\ 1\end{bmatrix}\\ &= \begin{bmatrix} 2&3\\ 3&4 \end{bmatrix} \begin{bmatrix}1\ 3\end{bmatrix} - \begin{bmatrix}11\ 15\end{bmatrix}\\ &= \begin{bmatrix}11\ 15\end{bmatrix} - \begin{bmatrix}11\ 15\end{bmatrix}\\ &= \begin{bmatrix}0\ 0\end{bmatrix}. \end{align}
\vec{r}=\begin{bmatrix}1\ 0\end{bmatrix}
A x (B\vec{r})-C\vec{r}= \begin{bmatrix} 2&3\\ 3&4 \end{bmatrix} \left(\begin{bmatrix} 1&0\\ 1&2 \end{bmatrix} \begin{bmatrix}1\ 0\end{bmatrix} \right) - \begin{bmatrix} 6&5\\ 8&7 \end{bmatrix} \begin{bmatrix}1\ 0\end{bmatrix} = \begin{bmatrix}-1\ -1\end{bmatrix}.
There are four two-element 0/1 vectors, and half of them give the zero vector in this case (
\vec{r}=\begin{bmatrix}0\ 0\end{bmatrix}
\vec{r}=\begin{bmatrix}1\ 1\end{bmatrix}
Let p equal the probability of error. We claim that if A × B = C, then p = 0, and if A × B ≠ C, then p ≤ 1/2.
\begin{align} \vec{P}&=A x (B\vec{r})-C\vec{r}\\ &=(A x B)\vec{r}-C\vec{r}\\ &=(A x B-C)\vec{r}\\ &=\vec{0} \end{align}
This is regardless of the value of
\vec{r}
A x B-C=0
\Pr[\vec{P} ≠ 0]=0
Let
D
\vec{P}=D x \vec{r}=(p1,p2,...,
T | |
p | |
n) |
Where
D=A x B-C=(dij)
Since
A x B ≠ C
D
dij ≠ 0
pi=
n | |
\sum | |
k=1 |
dikrk=di1r1+ … +dijrj+ … +dinrn=dijrj+y
For some constant
y
y
We use that:
\Pr[pi=0|y=0]=\Pr[rj=0]=
1 | |
2 |
\Pr[pi=0|y ≠ 0]=\Pr[rj=1\landdij=-y]\leq\Pr[rj=1]=
1 | |
2 |
Plugging these in the equation, we get:
\begin{align} \Pr[pi=0]&\leq
1 | |
2 |
⋅ \Pr[y=0]+
1 | |
2 |
⋅ \Pr[y ≠ 0]\\ &=
1 | |
2 |
⋅ \Pr[y=0]+
1 | |
2 |
⋅ (1-\Pr[y=0])\\ &=
1 | |
2 |
\end{align}
Therefore,
\Pr[\vec{P}=0]=\Pr[p1=0\land...\landpi=0\land...\landpn=0]\leq\Pr[pi=0]\leq
1 | |
2 |
.
Simple algorithmic analysis shows that the running time of this algorithm is
O(n2)
O(n3)
O(n2.373)
k
1/2k
Freivalds' algorithm frequently arises in introductions to probabilistic algorithms because of its simplicity and how it illustrates the superiority of probabilistic algorithms in practice for some problems.