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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Три матрицы , и размера .

«Да» если ; «Нет» в противном случае.

  1. Сгенерировать случайный вектор из нулей и единиц размера .
  2. Вычислить .
  3. Вывести «Да» если ; «Нет» в противном случае.

Вероятность ошибки

[править | править код]

Если , то алгоритм всегда возвращает «Да». Если , то вероятность того, что алгоритм вернёт «Да» не больше .

Если выполнить алгоритм раз и возвращать «Да» только если на каждой итерации был получен ответ «Да», будет получен алгоритм со временем работы и вероятностью ошибки .

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

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

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

Полученный вектор не нулевой, что доказывает, что .

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

Анализ алгоритма

[править | править код]

Пусть вероятность ошибки равна . Если , то , если же , то .

Случай A × B = C

[править | править код]

Полученный результат не зависит от , так как здесь используется лишь то, что . Таким образом, вероятность ошибки в данном случае:

Случай A × BC

[править | править код]

Пусть матрица такова, что

Где

.

Так как , некоторые элементы матрицы не равны нулю. Пусть . По определению матричного произведения:

.

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

.

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

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

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

  1. Virginia Vassilevska Williams. Breaking the Coppersmith-Winograd barrier. Дата обращения: 11 ноября 2019. Архивировано 30 апреля 2013 года.
  2. Raghavan, Prabhakar. Randomized algorithms (англ.) // ACM Computing Surveys[англ.] : journal. — 1997. — Vol. 28. — P. 33. — doi:10.1145/234313.234327.
  • Freivalds, R. (1977), «Probabilistic Machines Can Use Less Running Time», IFIP Congress 1977, pp. 839—842.