Алгоритм Фрейвалдса

Алгоритм Фрейвалдса (назван по имени Русиньша Мартыньша Фрейвалдса) — это вероятностный рандомизированный алгоритм, используемый для верификации матричного произведения. По трём матрицам $A$ , $B$ и $C$ размера $n\times n$ необходимо проверить, что $A\times B=C$ . Наивный алгоритм решения данной задачи заключается в том, чтобы посчитать $A\times B$ в явном виде и поэлементно сравнить получившуюся матрицу с $C$ . Однако наилучший известный алгоритм умножения матриц работает за время $O(n^{2.3729})$ ^[1]. Алгоритм Фрейвалдса использует рандомизацию чтобы снизить данную оценку до $O(n^{2})$ ^[2] с высокой вероятностью. За время $O(kn^{2})$ алгоритм может проверить матричное произведение с вероятностью ошибки, не превосходящей $2^{-k}$ .

Алгоритм

Ввод

Три матрицы $A$ , $B$ и $C$ размера $n\times n$ .

Вывод

«Да» если $A\times B=C$ ; «Нет» в противном случае.

Процедура

Сгенерировать случайный вектор ${\vec {r}}$ из нулей и единиц размера $n\times 1$ .
Вычислить ${\vec {P}}=A\times (B{\vec {r}})-C{\vec {r}}$ .
Вывести «Да» если ${\vec {P}}=(0,0,\ldots ,0)^{T}$ ; «Нет» в противном случае.

Вероятность ошибки

Если $A\times B=C$ , то алгоритм всегда возвращает «Да». Если $A\times B\neq C$ , то вероятность того, что алгоритм вернёт «Да» не больше $1/2$ .

Если выполнить алгоритм $k$ раз и возвращать «Да» только если на каждой итерации был получен ответ «Да», будет получен алгоритм со временем работы $O(kn^{2})$ и вероятностью ошибки $\leq 2^{-k}$ .

Пример

Пусть нужно проверить, что:

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{aligned}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\\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}}

То, что получен нулевой вектор указывает на то, что $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}}.

Полученный вектор не нулевой, что доказывает, что $AB\neq C$ .

В рассмотренном случае есть всего четыре двухэлементных векторов из нулей и единиц, и на половине из них получается нулевой вектор ( ${\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$ , и использование нескольких итераций (например, 20) сделает вероятность ошибки пренебрежимо малой.

Анализ алгоритма

Пусть вероятность ошибки равна $p$ . Если $A\times B=C$ , то $p=0$ , если же $A\times B\neq C$ , то $p\leq 1/2$ .

Случай A × B = C

{\begin{aligned}{\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}}\end{aligned}}

Полученный результат не зависит от ${\vec {r}}$ , так как здесь используется лишь то, что $A\times B-C=0$ . Таким образом, вероятность ошибки в данном случае:

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

Случай A × B ≠ C

Пусть матрица $D$ такова, что

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

Где

D=A\times B-C=(d_{ij})

.

Так как $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

.

Для некоторой константы $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]

.

Указанные вероятности можно оценить следующим образом:

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

Подставляя эти выражения в исходное равенство, можно прийти к:

{\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}}

Таким образом,

\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}}.

См. также

Лемма Шварца — Зиппеля

Ссылки

↑ Virginia Vassilevska Williams. Breaking the Coppersmith-Winograd barrier (неопр.). Дата обращения: 11 ноября 2019. Архивировано 30 апреля 2013 года.
↑ Raghavan, Prabhakar. Randomized algorithms (англ.) // ACM Computing Surveys^[англ.] : journal. — 1997. — Vol. 28. — P. 33. — doi:10.1145/234313.234327.

Freivalds, R. (1977), «Probabilistic Machines Can Use Less Running Time», IFIP Congress 1977, pp. 839—842.

[williams-1] Virginia Vassilevska Williams. Breaking the Coppersmith-Winograd barrier (неопр.). Дата обращения: 11 ноября 2019. Архивировано 30 апреля 2013 года.

[2] Raghavan, Prabhakar. Randomized algorithms (англ.) // ACM Computing Surveys^[англ.] : journal. — 1997. — Vol. 28. — P. 33. — doi:10.1145/234313.234327.

[1]

[2]