Алгоритм Фрейвалдса (назван по имени Русиньша Мартыньша Фрейвалдса) — это вероятностный рандомизированный алгоритм, используемый для верификации матричного произведения. По трём матрицам
,
и
размера
необходимо проверить, что
. Наивный алгоритм решения данной задачи заключается в том, чтобы посчитать
в явном виде и поэлементно сравнить получившуюся матрицу с
. Однако наилучший известный алгоритм умножения матриц работает за время
[1]. Алгоритм Фрейвалдса использует рандомизацию чтобы снизить данную оценку до
[2] с высокой вероятностью. За время
алгоритм может проверить матричное произведение с вероятностью ошибки, не превосходящей
.
Алгоритм
Ввод
Три матрицы
,
и
размера
.
Вывод
«Да» если
; «Нет» в противном случае.
Процедура
- Сгенерировать случайный вектор
из нулей и единиц размера
. - Вычислить
. - Вывести «Да» если
; «Нет» в противном случае.
Вероятность ошибки
Если
, то алгоритм всегда возвращает «Да». Если
, то вероятность того, что алгоритм вернёт «Да» не больше
.
Если выполнить алгоритм
раз и возвращать «Да» только если на каждой итерации был получен ответ «Да», будет получен алгоритм со временем работы
и вероятностью ошибки
.
Пример
Пусть нужно проверить, что:

Выбирается случайный вектор из нулей и единиц, например,
, после чего он используется для вычислений:

То, что получен нулевой вектор указывает на то, что
. Однако, если на второй итерации использовать вектор
, то будет получен следующий результат:

Полученный вектор не нулевой, что доказывает, что
.
В рассмотренном случае есть всего четыре двухэлементных векторов из нулей и единиц, и на половине из них получается нулевой вектор (
и
), таким образом вероятность того, что оба раза будет выбран один из этих векторов (что повлечёт ложный вывод о том, что
) равна
или
. В общем случае доля векторов
, влекущих нулевой вектор может быть меньше
, и использование нескольких итераций (например, 20) сделает вероятность ошибки пренебрежимо малой.
Анализ алгоритма
Пусть вероятность ошибки равна
. Если
, то
, если же
, то
.
Случай A × B = C

Полученный результат не зависит от
, так как здесь используется лишь то, что
. Таким образом, вероятность ошибки в данном случае:
![{\displaystyle \Pr[{\vec {P}}\neq 0]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c73087a7efc162b4e75c6865e98c1d05aec25a0a)
Случай A × B ≠ C
Пусть матрица
такова, что

Где
.
Так как
, некоторые элементы матрицы
не равны нулю. Пусть
. По определению матричного произведения:
.
Для некоторой константы
. Используя теорему Байеса, можно разложить вероятность по
:
.
Указанные вероятности можно оценить следующим образом:
![{\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.