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

Алгоритм Фрейвальдса (названный в честь Русиньш Мартиньш Фрейвальдс ) является вероятностным рандомизированный алгоритм используется для проверки матричное умножение. Учитывая три п × п матрицы ${ displaystyle A}$, ${ displaystyle B}$, и ${ displaystyle C}$, общая проблема состоит в том, чтобы проверить, ${ Displaystyle А раз В = С}$. Наивный алгоритм вычислил бы продукт ${ displaystyle A times B}$ явно и сравните по срокам, равен ли этот продукт ${ displaystyle C}$. Однако самый известный алгоритм умножения матриц работает в ${ displaystyle O (п ^ {2.3729})}$ время.^[1] Алгоритм Фрейвальдса использует рандомизация чтобы сократить это время, привязанное к ${ Displaystyle О (п ^ {2})}$^[2]с большой вероятностью. В ${ displaystyle O (kn ^ {2})}$ время, когда алгоритм может проверить матричное произведение с вероятностью отказа меньше, чем ${ displaystyle 2 ^ {- k}}$.

Алгоритм

Вход

Три п × п матрицы ${ displaystyle A}$, ${ displaystyle B}$, и ${ displaystyle C}$.

Выход

Да, если ${ Displaystyle А раз В = С}$; В противном случае нет.

Процедура

1. Создать п × 1 случайный 0/1 вектор ${ displaystyle { vec {r}}}$.
2. Вычислить ${ displaystyle { vec {P}} = A times (B { vec {r}}) - C { vec {r}}}$.
3. Выведите «Да», если ${ Displaystyle { vec {P}} = (0,0, ldots, 0) ^ {T}}$; «Нет», иначе.

Ошибка

Если ${ Displaystyle А раз В = С}$, то алгоритм всегда возвращает «Да». Если ${ displaystyle A times B neq C}$, то вероятность того, что алгоритм вернет «Да», меньше или равна половине. Это называется односторонняя ошибка.

Повторяя алгоритм k раз и возвращает «Да», только если все итерации дают «Да», время выполнения ${ displaystyle O (kn ^ {2})}$ и вероятность ошибки ${ Displaystyle Leq 1/2 ^ {к}}$ Достигнут.

Пример

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

${ displaystyle AB = { begin {bmatrix} 2 & 3 3 & 4 end {bmatrix}} { begin {bmatrix} 1 & 0 1 & 2 end {bmatrix}} { stackrel {?} {=}} { begin {bmatrix} 6 & 5 8 & 7 end {bmatrix}} = C.}$

Выбирается случайный двухэлементный вектор с элементами, равными 0 или 1, например ${ displaystyle { vec {r}} = { begin {bmatrix} 1 1 end {bmatrix}}}$ - и используется для вычисления:

${ displaystyle { begin {align} A times (B { vec {r}}) - C { vec {r}} & = { begin {bmatrix} 2 & 3 3 & 4 end {bmatrix}} left ({ begin {bmatrix} 1 & 0 1 & 2 end {bmatrix}} { begin {bmatrix} 1 1 end {bmatrix}} right) - { begin {bmatrix} 6 & 5 8 & 7 end {bmatrix}} { begin {bmatrix} 1 1 end {bmatrix}} & = { begin {bmatrix} 2 & 3 3 & 4 end {bmatrix}} { begin {bmatrix} 1 3 end {bmatrix}} - { begin {bmatrix} 11 15 end {bmatrix}} & = { begin {bmatrix} 11 15 end {bmatrix}} - { begin {bmatrix} 11 15 end {bmatrix}} & = { begin {bmatrix} 0 0 end {bmatrix}}. End {align}}}$

Это дает нулевой вектор, предполагая возможность того, что AB = C. Однако, если во втором испытании вектор ${ displaystyle { vec {r}} = { begin {bmatrix} 1 0 end {bmatrix}}}$ выбран, результат становится:

${ displaystyle A times (B { vec {r}}) - C { vec {r}} = { begin {bmatrix} 2 & 3 3 & 4 end {bmatrix}} left ({ begin {bmatrix } 1 & 0 1 & 2 end {bmatrix}} { begin {bmatrix} 1 0 end {bmatrix}} right) - { begin {bmatrix} 6 & 5 8 & 7 end {bmatrix}} { begin {bmatrix} 1 0 end {bmatrix}} = { begin {bmatrix} -1 - 1 end {bmatrix}}.}$

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

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

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

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

Дело А × B = C

${ Displaystyle { begin {выровнено} { vec {P}} & = A times (B { vec {r}}) - C { vec {r}} & = (A times B) { vec {r}} - C { vec {r}} & = (A times BC) { vec {r}} & = { vec {0}} end {выровнено}} }$

Это независимо от стоимости ${ displaystyle { vec {r}}}$, поскольку он использует только это ${ displaystyle A times B-C = 0}$. Следовательно, вероятность ошибки в этом случае равна:

${ Displaystyle Pr [{ vec {P}} neq 0] = 0}$

Дело А × B ≠ C

Позволять ${ displaystyle D}$ такой, что

${ displaystyle { vec {P}} = D times { vec {r}} = (p_ {1}, p_ {2}, dots, p_ {n}) ^ {T}}$

Где

${ Displaystyle D = A раз B-C = (d_ {ij})}$.

С ${ displaystyle A times B neq C}$, у нас есть этот элемент ${ displaystyle D}$ отличен от нуля. Предположим, что элемент ${ displaystyle d_ {ij} neq 0}$. По определению матричное умножение, у нас есть:

${ displaystyle p_ {i} = sum _ {k = 1} ^ {n} d_ {ik} r_ {k} = d_ {i1} r_ {1} + cdots + d_ {ij} r_ {j} + cdots + d_ {in} r_ {n} = d_ {ij} r_ {j} + y}$.

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

${ displaystyle Pr [p_ {i} = 0] = Pr [p_ {i} = 0 | y = 0] cdot Pr [y = 0] , + , Pr [p_ {i} = 0 | y neq 0] cdot Pr [y neq 0]}$

(1)

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

${ displaystyle Pr [p_ {i} = 0 | y = 0] = Pr [r_ {j} = 0] = { frac {1} {2}}}$

${ displaystyle Pr [p_ {i} = 0 | y neq 0] = Pr [r_ {j} = 1 land d_ {ij} = - y] leq Pr [r_ {j} = 1] = { frac {1} {2}}}$

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

${ displaystyle { begin {align} Pr [p_ {i} = 0] & leq { frac {1} {2}} cdot Pr [y = 0] + { frac {1} {2 }} cdot Pr [y neq 0] & = { frac {1} {2}} cdot Pr [y = 0] + { frac {1} {2}} cdot (1 - Pr [y = 0]) & = { frac {1} {2}} end {align}}}$

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

${ Displaystyle Pr [{ vec {P}} = 0] = Pr [p_ {1} = 0 land dots land p_ {i} = 0 land dots land p_ {n} = 0 ] leq Pr [p_ {i} = 0] leq { frac {1} {2}}.}$

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

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

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

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

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

• Лемма Шварца – Циппеля.

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

• Р. Фрейвальдс (1977), «Вероятностные машины могут использовать меньшее время работы», Конгресс ИФИП 1977 г., стр. 839–842.