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

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

Алгоритм

Вход

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

Выход

Да, если ${\displaystyle A\times B=C}$; В противном случае нет.

Процедура

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 A\times B=C}$, то алгоритм всегда возвращает «Да». Если ${\displaystyle A\times B\neq C}$, то вероятность того, что алгоритм вернет «Да», меньше или равна половине. Это называется односторонняя ошибка.

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

Пример

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

${\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{aligned}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{aligned}}}$

Это дает нулевой вектор, предполагая возможность того, что 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{aligned}{\vec {P}}&=A\times (B{\vec {r}})-C{\vec {r}}\\&=(A\times B){\vec {r}}-C{\vec {r}}\\&=(A\times B-C){\vec {r}}\\&={\vec {0}}\end{aligned}}}$

Это независимо от стоимости ${\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\times 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{aligned}\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{aligned}}}$

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

${\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]

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

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

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

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

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

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