Freivaldův algoritmus

Freivaldsův algoritmus (pojmenovaný po Rusins Martins Freivalds ) je pravděpodobnostní randomizovaný algoritmus používaný k ověření maticového produktu . Pro tři matice a velikost je nutné to zkontrolovat . Naivním algoritmem pro řešení tohoto problému je explicitně vypočítat a porovnat prvek po prvku výslednou matici s . Nejznámější algoritmus pro násobení matic však běží v čase [1] . Freivaldův algoritmus používá randomizaci ke snížení daného odhadu na [2] s vysokou pravděpodobností . Během $A$ $B$ $C$ $n\krát n$ $A\times B=C$ $A\krát B$ $C$ $O(n^{2,3729})$ $O(n^{2})$ $O(kn^{2})$ algoritmus může kontrolovat maticový součin s pravděpodobností chyby nepřesahující . $2^{-k}$

Algoritmus

Vstup

Tři matice a velikosti . _ $A$ $B$ $C$ $n\krát n$

Závěr

"Ano", pokud ; "Ne" jinak. $A\times B=C$

Postup

Vygenerujte náhodný vektor velikosti nul a jedniček . ${\vec {r))$ $n krát 1$
Vypočítejte . ${\vec {P}}=A\times (B{\vec {r}})-C{\vec {r}}$
Výstup "Ano" pokud ; "Ne" jinak. ${\vec {P}}=(0,0,\ldots ,0)^{T}$

Pravděpodobnost chyby

Pokud , pak algoritmus vždy vrátí "Ano". Pokud , pak pravděpodobnost, že algoritmus vrátí "Ano", není větší než . $A\times B=C$ $A\times B\neq C$ $1/2$

Pokud provedeme algoritmus jednou a vrátíme "Ano" pouze v případě, že při každé iteraci byla přijata odpověď "Ano", dostaneme algoritmus s dobou běhu a pravděpodobností chyby . $k$ $O(kn^{2})$ ${\displaystyle \leq 2^{-k))$

Příklad

Zkontrolujeme, že:

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.

Vybere se například náhodný vektor nul a jedniček, poté se použije pro výpočty: ${\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}$

{\begin{aligned}A\times (B{\vec {r)))-C{\vec {r}}&={\begin{bmatrix}2&3\\3&4\end{bmatrix}}\ vlevo({\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{aligned}}

Skutečnost, že je získán nulový vektor, znamená, že . Pokud je však vektor použit ve druhé iteraci , získá se následující výsledek: $AB=C$ ${\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}$

A\times (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}}.

Výsledný vektor není nula, což dokazuje, že . $AB\neq C$

V uvažovaném případě existují pouze čtyři dvouprvkové vektory nul a jedniček a na polovině z nich je získán nulový vektor ( a ), takže pravděpodobnost, že bude v obou případech zvolen jeden z těchto vektorů (což povede k falešný závěr, že ) se rovná nebo . Obecně platí, že zlomek vektorů , který implikuje nulový vektor, může být menší než a použití více iterací (například 20) způsobí, že pravděpodobnost chyby bude zanedbatelná. ${\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}$ ${\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}$ $AB=C$ $2^{-2}$ $1/4$ $r$ $1/2$

Analýza algoritmů

Nechť pravděpodobnost chyby je . Když , tak , když , tak . $p$ $A\times B=C$ $p=0$ $A\times B\neq C$ $p\leq 1/2$

Případ A × B = C

{\begin{aligned}{\vec {P}}&=A\times (B{\vec {r}})-C{\vec {r}}\\&=(A\times B) {\vec {r}}-C{\vec {r}}\\&=(A\krát BC){\vec {r}}\\&={\vec {0}}\end{aligned}}

Získaný výsledek nezávisí na , protože pouze na skutečnosti , že . Pravděpodobnost chyby v tomto případě je tedy: ${\vec {r))$ $A\times BC=0$

\Pr[{\vec {P}}\neq 0]=0

Případ A × B ≠ C

Nechť je matice taková, že $D$

{\vec {P}}=D\times {\vec {r}}=(p_{1},p_{2},\tečky ,p_{n})^{T}

Kde

D=A\times BC=(d_{ij})

Protože některé prvky matice nejsou rovny nule. Nechte _ Podle definice maticového produktu : $A\times B\neq C$ $D$ $d_{ij}\neq 0$

p_{i}=\sum _{k=1}^{n}d_{ik}r_{k}=d_{i1}r_{1}+\cdots +d_{ij}r_{j}+ \cdots +d_{in}r_{n}=d_{ij}r_{j}+y

Pro nějakou stálou . Pomocí Bayesova teorému lze rozšířit pravděpodobnost z hlediska : $y$ $y$

\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]

Tyto pravděpodobnosti lze odhadnout následovně:

\Pr[p_{i}=0|y=0]=\Pr[r_{j}=0]={\frac {1}{2))

\Pr[p_{i}=0|y\neq 0]=\Pr[r_{j}=1\land d_{ij}=-y]\leq \Pr[r_{j}=1] ={\frac {1}{2}}

Dosazením těchto výrazů do původní rovnosti lze dospět k:

{\begin{aligned}\Pr[p_{i}=0]&\leq {\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2 }}\cdot \Pr[y\neq 0]\\&={\frac {1}{2}}\cdot \Pr[y=0]+{\frac {1}{2}}\cdot (1 -\Pr[y=0])\\&={\frac {1}{2}}\end{aligned}}

Takto,

\Pr[{\vec {P}}=0]=\Pr[p_{1}=0\land \dots \land p_{i}=0\land \dots \land p_{n}=0 ]\leq \Pr[p_{i}=0]\leq {\frac {1}{2}}.

Viz také

Schwarz-Zippel Lemma

Odkazy

↑ Virginia Vassilevska Williamsová. Prolomení Coppersmith-Winogradské bariéry . Získáno 11. listopadu 2019. Archivováno z originálu 30. dubna 2013. (neurčitý)
↑ Raghavan, Prabhakar. Randomizované algoritmy // ACM Computing Surveys : deník. - 1997. - Sv. 28 . — S. 33 . - doi : 10.1145/234313.234327 .

Freivalds, R. (1977), "Pravděpodobnostní stroje mohou používat méně provozní doby", Kongres IFIP 1977, str. 839-842.