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

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

Три матрицы n  ×  n , , и . ${\displaystyle А}$${\displaystyle Б}$${\displaystyle С}$

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

1. Сгенерировать случайный вектор 0/1 размером n  × 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{выровнено}}}$

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

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

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

Пусть такой, что${\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}}.}$

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

Простой алгоритмический анализ показывает, что время выполнения этого алгоритма составляет (в нотации O большое ). Это превосходит время выполнения классического детерминированного алгоритма (или при использовании быстрого умножения матриц ). Анализ ошибок также показывает, что если алгоритм выполняется раз, может быть достигнута граница ошибки менее , экспоненциально малая величина. Алгоритм также быстр на практике из-за широкой доступности быстрых реализаций для произведений матрицы и вектора. Следовательно, использование рандомизированных алгоритмов может ускорить очень медленный детерминированный алгоритм .${\displaystyle O(n^{2})}$${\displaystyle O(n^{3})}$${\displaystyle O(n^{2.373})}$${\displaystyle k}$${\displaystyle 1/2^{k}}$

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

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