Алгоритм Фрейвалдса (назван по имени Русиньша Мартыньша Фрейвалдса) — это вероятностный рандомизированный алгоритм, используемый для верификации матричного произведения. По трём матрицам , и размера необходимо проверить, что . Наивный алгоритм решения данной задачи заключается в том, чтобы посчитать в явном виде и поэлементно сравнить получившуюся матрицу с . Однако наилучший известный алгоритм умножения матриц работает за время . Алгоритм Фрейвалдса использует рандомизацию чтобы снизить данную оценку до с высокой вероятностью. За время алгоритм может проверить матричное произведение с вероятностью ошибки, не превосходящей .
Алгоритм
Ввод Три матрицы , и размера .
Вывод «Да» если ; «Нет» в противном случае.
Процедура Сгенерировать случайный вектор из нулей и единиц размера . Вычислить . Вывести «Да» если ; «Нет» в противном случае.
Вероятность ошибки Если , то алгоритм всегда возвращает «Да». Если , то вероятность того, что алгоритм вернёт «Да» не больше .
Если выполнить алгоритм раз и возвращать «Да» только если на каждой итерации был получен ответ «Да», будет получен алгоритм со временем работы и вероятностью ошибки .
Пример Пусть нужно проверить, что:
Выбирается случайный вектор из нулей и единиц, например, , после чего он используется для вычислений:
То, что получен нулевой вектор указывает на то, что . Однако, если на второй итерации использовать вектор , то будет получен следующий результат:
Полученный вектор не нулевой, что доказывает, что .
В рассмотренном случае есть всего четыре двухэлементных векторов из нулей и единиц, и на половине из них получается нулевой вектор ( и ), таким образом вероятность того, что оба раза будет выбран один из этих векторов (что повлечёт ложный вывод о том, что ) равна или . В общем случае доля векторов , влекущих нулевой вектор может быть меньше , и использование нескольких итераций (например, 20) сделает вероятность ошибки пренебрежимо малой.
Анализ алгоритма Пусть вероятность ошибки равна . Если , то , если же , то .
Случай A × B = C
Полученный результат не зависит от , так как здесь используется лишь то, что . Таким образом, вероятность ошибки в данном случае:
Случай A × B ≠ C Пусть матрица такова, что
Где
.
Так как , некоторые элементы матрицы не равны нулю. Пусть . По определению матричного произведения:
.
Для некоторой константы . Используя теорему Байеса, можно разложить вероятность по :
.
Указанные вероятности можно оценить следующим образом:
Подставляя эти выражения в исходное равенство, можно прийти к:
Таким образом,
См. также Лемма Шварца — Зиппеля
Ссылки
Freivalds, R. (1977), «Probabilistic Machines Can Use Less Running Time», IFIP Congress 1977, pp. 839—842.
Категория:Матрицы Категория:Алгоритмы