Алгоритм Фрейвальдса - Википедия - Freivalds algorithm

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

Алгоритм

Вход

Три п × п матрицы , , и .

Выход

Да, если ; В противном случае нет.

Процедура

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

Ошибка

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

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

Пример

Предположим, кто-то желает определить:

Выбирается случайный двухэлементный вектор с элементами, равными 0 или 1, например - и используется для вычисления:

Это дает нулевой вектор, предполагая возможность того, что AB = C. Однако, если во втором испытании вектор выбран, результат становится:

Результат отличен от нуля, что доказывает, что AB ≠ C.

Имеется четыре двухэлементных вектора 0/1, половина из которых в данном случае дает нулевой вектор ( и ), поэтому шанс случайного выбора их в двух испытаниях (и ложного заключения о том, что AB = C) равен 1/2.2 или 1/4. В общем случае доля р дающий нулевой вектор может быть меньше 1/2, и будет использовано большее количество попыток (например, 20), что сделает вероятность ошибки очень малой.

Анализ ошибок

Позволять п равно вероятность ошибки. Мы утверждаем, что если А × B = C, тогда п = 0, а если А × BC, тогда п ≤ 1/2.

Дело А × B = C

Это независимо от стоимости , поскольку он использует только это . Следовательно, вероятность ошибки в этом случае равна:

Дело А × BC

Позволять такой, что

Где

.

С , у нас есть этот элемент отличен от нуля. Предположим, что элемент . По определению матричное умножение, у нас есть:

.

Для некоторой постоянной .С помощью Теорема Байеса, мы можем разделить :

 

 

 

 

(1)

Мы используем это:

Подключив их к уравнению (1), мы получили:

Следовательно,

Это завершает доказательство.

Разветвления

Простой алгоритмический анализ показывает, что время работы этого алгоритм является О (п2), превосходя классический детерминированный алгоритм граница О (п3). Анализ ошибок также показывает, что если мы запустим алгоритм k раз мы можем достичь граница ошибки менее чем , экспоненциально малая величина. Алгоритм также быстр на практике из-за широкой доступности быстрых реализаций для произведений матрица-вектор. Следовательно, использование рандомизированные алгоритмы может ускорить очень медленно детерминированный алгоритм. Фактически, наиболее известный детерминированный алгоритм умножения матриц, известный в настоящее время, является вариантом метода Алгоритм Копперсмита – Винограда с асимптотическим временем работы О (п2.3729).[1]

Алгоритм Фрейвальдса часто встречается при введении в вероятностные алгоритмы из-за его простоты и того, как он иллюстрирует превосходство вероятностных алгоритмов на практике для некоторых задач.

Смотрите также

Рекомендации

  1. ^ а б Вирджиния Василевска Уильямс. «Преодолевая барьер медников-виноград» (PDF).
  2. ^ Рагхаван, Прабхакар (1997). «Рандомизированные алгоритмы». Опросы ACM Computing. 28: 33. Дои:10.1145/234313.234327. Получено 2008-12-16.
  • Р. Фрейвальдс (1977), «Вероятностные машины могут использовать меньшее время работы», Конгресс ИФИП 1977 г., стр. 839–842.