Введение

Алгоритм Фрейвальда (названный в честь Русиньша Мартиньша Фрейвальда) - вероятностный рандомизированный алгоритм, используемый для проверки множения матриц. При наличии трех матриц n × n , , и , общая проблема заключается в том, чтобы проверить, будет ли наивный алгоритм рассчитывать произведение явно и сравнивать термин за термином, равен ли это произведение. Однако, наиболее известный алгоритм умножения матриц работает во времени. Алгоритм Фрейвальда использует рандомизацию для того, чтобы сократить это время, связанное с высокой вероятностью. Со временем алгоритм может проверить матричный произведение с вероятностью неудачи меньше .

Входные данные

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

Выпуск

Да, если; Нет, если нет.

Процедура

Создать n × 1 случайный вектор 0/1 Выход вычисления "Да" если; "Нет", в противном случае.

Ошибка

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

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

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

Случай A × B = C

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

Разделы

Простой алгоритмический анализ показывает, что время выполнения этого алгоритма (в большом O-символе). Это превосходит время выполнения классического детерминированного алгоритма (или если использовать быстрое умножение матриц). Анализ ошибок также показывает, что если алгоритм выполняется несколько раз, то ошибка меньше, чем может быть достигнута, экспоненциально небольшое количество. Алгоритм также быстрый на практике из-за широкой доступности быстрых реализаций для матричных векторных продуктов. Поэтому использование рандомизированных алгоритмов может ускорить очень медленный детерминированный алгоритм. Алгоритм Фрейвальда часто встречается в введении в вероятностные алгоритмы из-за его простоты и того, как он иллюстрирует превосходство вероятностных алгоритмов на практике для некоторых проблем.