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

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