Алгоритм Фрейвалдса (назван по имени Русиньша Мартыньша Фрейвалдса) — это вероятностный рандомизированный алгоритм, используемый для верификации матричного произведения. По трём матрицам
,
и
размера
необходимо проверить, что
. Наивный алгоритм решения данной задачи заключается в том, чтобы посчитать
в явном виде и поэлементно сравнить получившуюся матрицу с
. Однако наилучший известный алгоритм умножения матриц работает за время
[1]. Алгоритм Фрейвалдса использует рандомизацию чтобы снизить данную оценку до
[2] с высокой вероятностью. За время
алгоритм может проверить матричное произведение с вероятностью ошибки, не превосходящей
.
Алгоритм
Ввод
Три матрицы
,
и
размера
.
Вывод
«Да» если
; «Нет» в противном случае.
Процедура
- Сгенерировать случайный вектор
из нулей и единиц размера
.
- Вычислить
.
- Вывести «Да» если
; «Нет» в противном случае.
Вероятность ошибки
Если
, то алгоритм всегда возвращает «Да». Если
, то вероятность того, что алгоритм вернёт «Да» не больше
.
Если выполнить алгоритм
раз и возвращать «Да» только если на каждой итерации был получен ответ «Да», будет получен алгоритм со временем работы
и вероятностью ошибки
.
Пример
Пусть нужно проверить, что:
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40b8b964afcdf0a656d6335c6eee3d9605409700)
Выбирается случайный вектор из нулей и единиц, например,
, после чего он используется для вычислений:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d3c195761cf6bd80066615a92dc1ce584b12f17)
То, что получен нулевой вектор указывает на то, что
. Однако, если на второй итерации использовать вектор
, то будет получен следующий результат:
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f350143b68beb89ba227ad3c703cb97fac29c3c)
Полученный вектор не нулевой, что доказывает, что
.
В рассмотренном случае есть всего четыре двухэлементных векторов из нулей и единиц, и на половине из них получается нулевой вектор (
и
), таким образом вероятность того, что оба раза будет выбран один из этих векторов (что повлечёт ложный вывод о том, что
) равна
или
. В общем случае доля векторов
, влекущих нулевой вектор может быть меньше
, и использование нескольких итераций (например, 20) сделает вероятность ошибки пренебрежимо малой.
Анализ алгоритма
Пусть вероятность ошибки равна
. Если
, то
, если же
, то
.
Случай 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fabd27ff04a5b967fc378a944e3a230a6d6339c)
Полученный результат не зависит от
, так как здесь используется лишь то, что
. Таким образом, вероятность ошибки в данном случае:
![{\displaystyle \Pr[{\vec {P}}\neq 0]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c73087a7efc162b4e75c6865e98c1d05aec25a0a)
Случай A × B ≠ C
Пусть матрица
такова, что
![{\displaystyle {\vec {P}}=D\times {\vec {r}}=(p_{1},p_{2},\dots ,p_{n})^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7bbb1d0196e78bfa7347345e0b05877f8616198)
Где
.
Так как
, некоторые элементы матрицы
не равны нулю. Пусть
. По определению матричного произведения:
.
Для некоторой константы
. Используя теорему Байеса, можно разложить вероятность по
:
.
Указанные вероятности можно оценить следующим образом:
![{\displaystyle \Pr[p_{i}=0|y=0]=\Pr[r_{j}=0]={\frac {1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c5a17eb0d50e08bb9a83418bf18f5ada6d2b210)
![{\displaystyle \Pr[p_{i}=0|y\neq 0]=\Pr[r_{j}=1\land d_{ij}=-y]\leq \Pr[r_{j}=1]={\frac {1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0ba405df9fd611dbb73bf7c9bf4eac801ae8a30)
Подставляя эти выражения в исходное равенство, можно прийти к:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac04124bbed15468913248264a3f495d919efe2e)
Таким образом,
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e355ff8aa8a654e52019735c8e960fc2555f859)
См. также
Ссылки
- Freivalds, R. (1977), «Probabilistic Machines Can Use Less Running Time», IFIP Congress 1977, pp. 839—842.
Эта страница в последний раз была отредактирована 28 мая 2022 в 17:24.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.