Алгоритм Фрейвалдса (назван по имени Русиньша Мартыньша Фрейвалдса ) — это вероятностный рандомизированный алгоритм , используемый для верификации матричного произведения . По трём матрицам ${\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})}$ . Алгоритм Фрейвалдса использует рандомизацию чтобы снизить данную оценку до ${\displaystyle O(n^{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}$ .

Случай A × B = C

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

Случай A × B ≠ C

Пусть матрица ${\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.