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

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

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

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

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

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

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

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

${\displaystyle 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.}$

Выбирается случайный вектор из нулей и единиц, например, ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$, после чего он используется для вычислений:

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

То, что получен нулевой вектор указывает на то, что ${\displaystyle AB=C}$. Однако, если на второй итерации использовать вектор ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\0\end{bmatrix}}}$ , то будет получен следующий результат:

${\displaystyle 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}}.}$

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

В рассмотренном случае есть всего четыре двухэлементных векторов из нулей и единиц, и на половине из них получается нулевой вектор (${\displaystyle {\vec {r}}={\begin{bmatrix}0\\0\end{bmatrix}}}$ и ${\displaystyle {\vec {r}}={\begin{bmatrix}1\\1\end{bmatrix}}}$), таким образом вероятность того, что оба раза будет выбран один из этих векторов (что повлечёт ложный вывод о том, что ${\displaystyle AB=C}$) равна ${\displaystyle 2^{-2}}$ или ${\displaystyle 1/4}$. В общем случае доля векторов ${\displaystyle r}$, влекущих нулевой вектор может быть меньше ${\displaystyle 1/2}$, и использование нескольких итераций (например, 20) сделает вероятность ошибки пренебрежимо малой.

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

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

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

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

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

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

Где

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

Так как ${\displaystyle A\times B\neq C}$, некоторые элементы матрицы ${\displaystyle D}$ не равны нулю. Пусть ${\displaystyle d_{ij}\neq 0}$. По определению матричного произведения:

${\displaystyle 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}$.

Для некоторой константы ${\displaystyle y}$. Используя теорему Байеса, можно разложить вероятность по ${\displaystyle y}$:

${\displaystyle \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]}$.

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

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

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

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

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

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

${\displaystyle \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}}.}$

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

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