Русская Википедия:Алгоритм Фрейвалдса
Алгоритм Фрейвалдса (назван по имени Русиньша Мартыньша Фрейвалдса) — это вероятностный рандомизированный алгоритм, используемый для верификации матричного произведения. По трём матрицам <math>A</math>, <math>B</math> и <math>C</math> размера <math>n \times n</math> необходимо проверить, что <math>A \times B = C</math>. Наивный алгоритм решения данной задачи заключается в том, чтобы посчитать <math>A \times B</math> в явном виде и поэлементно сравнить получившуюся матрицу с <math>C</math>. Однако наилучший известный алгоритм умножения матриц работает за время <math>O(n^{2.3729})</math>[1]. Алгоритм Фрейвалдса использует рандомизацию чтобы снизить данную оценку до <math>O(n^2)</math>[2] с высокой вероятностью. За время <math>O(kn^2)</math> алгоритм может проверить матричное произведение с вероятностью ошибки, не превосходящей <math>2^{-k}</math>.
Алгоритм
Ввод
Три матрицы <math>A</math>, <math>B</math> и <math>C</math> размера <math>n \times n</math>.
Вывод
«Да» если <math>A \times B = C</math>; «Нет» в противном случае.
Процедура
- Сгенерировать случайный вектор <math>\vec{r}</math> из нулей и единиц размера <math>n \times 1</math>.
- Вычислить <math>\vec{P} = A \times (B \vec{r}) - C\vec{r}</math>.
- Вывести «Да» если <math>\vec{P} = (0,0,\ldots,0)^T</math>; «Нет» в противном случае.
Вероятность ошибки
Если <math>A \times B = C</math>, то алгоритм всегда возвращает «Да». Если <math>A \times B \neq C</math>, то вероятность того, что алгоритм вернёт «Да» не больше <math>1/2</math>.
Если выполнить алгоритм <math>k</math> раз и возвращать «Да» только если на каждой итерации был получен ответ «Да», будет получен алгоритм со временем работы <math>O(kn^2)</math> и вероятностью ошибки <math>\leq 2^{-k}</math>.
Пример
Пусть нужно проверить, что:
- <math>
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. </math>
Выбирается случайный вектор из нулей и единиц, например, <math>\vec{r} = \begin{bmatrix}1 \\ 1\end{bmatrix}</math>, после чего он используется для вычислений:
- <math>
\begin{align} 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{align} </math>
То, что получен нулевой вектор указывает на то, что <math>AB=C</math>. Однако, если на второй итерации использовать вектор <math>\vec{r} = \begin{bmatrix}1 \\ 0\end{bmatrix}</math> , то будет получен следующий результат:
- <math>
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}. </math>
Полученный вектор не нулевой, что доказывает, что <math>AB \neq C</math>.
В рассмотренном случае есть всего четыре двухэлементных векторов из нулей и единиц, и на половине из них получается нулевой вектор (<math>\vec{r} = \begin{bmatrix}0 \\ 0\end{bmatrix}</math> и <math>\vec{r} = \begin{bmatrix}1 \\ 1\end{bmatrix}</math>), таким образом вероятность того, что оба раза будет выбран один из этих векторов (что повлечёт ложный вывод о том, что <math>AB = C</math>) равна <math>2^{-2}</math> или <math>1/4</math>. В общем случае доля векторов <math>r</math>, влекущих нулевой вектор может быть меньше <math>1/2</math>, и использование нескольких итераций (например, 20) сделает вероятность ошибки пренебрежимо малой.
Анализ алгоритма
Пусть вероятность ошибки равна <math>p</math>. Если <math>A \times B = C</math>, то <math>p=0</math>, если же <math>A \times B \neq C</math>, то <math>p \leq 1/2</math>.
Случай A × B = C
- <math>
\begin{align} \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{align} </math>
Полученный результат не зависит от <math>\vec{r}</math>, так как здесь используется лишь то, что <math>A \times B - C = 0</math>. Таким образом, вероятность ошибки в данном случае:
- <math>\Pr[\vec{P} \neq 0] = 0</math>
Случай A × B ≠ C
Пусть матрица <math>D</math> такова, что
- <math>\vec{P} = D \times \vec{r} = (p_1, p_2, \dots, p_n)^T</math>
Где
- <math>D = A \times B - C = (d_{ij})</math>.
Так как <math>A \times B \neq C</math>, некоторые элементы матрицы <math>D</math> не равны нулю. Пусть <math>d_{ij} \neq 0</math>. По определению матричного произведения:
- <math>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</math>.
Для некоторой константы <math>y</math>. Используя теорему Байеса, можно разложить вероятность по <math>y</math>:
- <math>\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]</math>.
Указанные вероятности можно оценить следующим образом:
- <math>\Pr[p_i = 0 | y = 0] = \Pr[r_j = 0] = \frac{1}{2}</math>
- <math>\Pr[p_i = 0 | y \neq 0] = \Pr[r_j = 1 \land d_{ij}=-y] \leq \Pr[r_j = 1] = \frac{1}{2}</math>
Подставляя эти выражения в исходное равенство, можно прийти к:
- <math>
\begin{align} \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{align} </math>
Таким образом,
- <math>\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}.</math>
См. также
Ссылки
- Freivalds, R. (1977), «Probabilistic Machines Can Use Less Running Time», IFIP Congress 1977, pp. 839—842.
