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

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

Алгоритм

Ввод

Три матрицы $A$, $B$ и $C$ размера $n\times n$.

Вывод

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

Процедура

1. Сгенерировать случайный вектор $\overrightarrow{r}$ из нулей и единиц размера $n\times 1$.
2. Вычислить $\overrightarrow{P}=A\times (B\overrightarrow{r})-C\overrightarrow{r}$.
3. Вывести «Да» если $\overrightarrow{P}=(0,0,\dots ,0{)}^T$; «Нет» в противном случае.

Вероятность ошибки

Если $A\times B=C$, то алгоритм всегда возвращает «Да». Если $A\times B\ne C$, то вероятность того, что алгоритм вернёт «Да» не больше $1/2$.

Если выполнить алгоритм $k$ раз и возвращать «Да» только если на каждой итерации был получен ответ «Да», будет получен алгоритм со временем работы $O(k{n}^2)$ и вероятностью ошибки $\le 2^{-k}$.

Пример

Пусть нужно проверить, что:

$AB=\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]\left[\begin{array}{cc}1& 0\\ 1& 2\end{array}\right]\stackrel{?}{=}\left[\begin{array}{cc}6& 5\\ 8& 7\end{array}\right]=C.$

Выбирается случайный вектор из нулей и единиц, например, $\overrightarrow{r}=\left[\begin{array}{c}1\\ 1\end{array}\right]$, после чего он используется для вычислений:

$\begin{array}{cc}A\times (B\overrightarrow{r})-C\overrightarrow{r}& =\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]\left(\left[\begin{array}{cc}1& 0\\ 1& 2\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\right)-\left[\begin{array}{cc}6& 5\\ 8& 7\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]\\ & =\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]\left[\begin{array}{c}1\\ 3\end{array}\right]-\left[\begin{array}{c}11\\ 15\end{array}\right]\\ & =\left[\begin{array}{c}11\\ 15\end{array}\right]-\left[\begin{array}{c}11\\ 15\end{array}\right]\\ & =\left[\begin{array}{c}0\\ 0\end{array}\right].\end{array}$

То, что получен нулевой вектор указывает на то, что $AB=C$. Однако, если на второй итерации использовать вектор $\overrightarrow{r}=\left[\begin{array}{c}1\\ 0\end{array}\right]$ , то будет получен следующий результат:

$A\times (B\overrightarrow{r})-C\overrightarrow{r}=\left[\begin{array}{cc}2& 3\\ 3& 4\end{array}\right]\left(\left[\begin{array}{cc}1& 0\\ 1& 2\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\right)-\left[\begin{array}{cc}6& 5\\ 8& 7\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{c}-1\\ -1\end{array}\right].$

Полученный вектор не нулевой, что доказывает, что $AB\ne C$.

В рассмотренном случае есть всего четыре двухэлементных векторов из нулей и единиц, и на половине из них получается нулевой вектор ($\overrightarrow{r}=\left[\begin{array}{c}0\\ 0\end{array}\right]$ и $\overrightarrow{r}=\left[\begin{array}{c}1\\ 1\end{array}\right]$), таким образом вероятность того, что оба раза будет выбран один из этих векторов (что повлечёт ложный вывод о том, что $AB=C$) равна $2^{-2}$ или $1/4$. В общем случае доля векторов $r$, влекущих нулевой вектор может быть меньше $1/2$, и использование нескольких итераций (например, 20) сделает вероятность ошибки пренебрежимо малой.

Анализ алгоритма

Пусть вероятность ошибки равна $p$. Если $A\times B=C$, то $p=0$, если же $A\times B\ne C$, то $p\le 1/2$.

Случай A × B = C

$\begin{array}{cc}\overrightarrow{P}& =A\times (B\overrightarrow{r})-C\overrightarrow{r}\\ & =(A\times B)\overrightarrow{r}-C\overrightarrow{r}\\ & =(A\times B-C)\overrightarrow{r}\\ & =\overrightarrow{0}\end{array}$

Полученный результат не зависит от $\overrightarrow{r}$, так как здесь используется лишь то, что $A\times B-C=0$. Таким образом, вероятность ошибки в данном случае:

$\mathrm{Pr}[\overrightarrow{P}\ne 0]=0$

Случай A × B ≠ C

Пусть матрица $D$ такова, что

$\overrightarrow{P}=D\times \overrightarrow{r}=(p_1,p_2,\dots ,p_n{)}^T$

Где

$D=A\times B-C=(d_{ij})$.

Так как $A\times B\ne C$, некоторые элементы матрицы $D$ не равны нулю. Пусть $d_{ij}\ne 0$. По определению матричного произведения:

$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$.

Для некоторой константы $y$. Используя теорему Байеса, можно разложить вероятность по $y$:

$\mathrm{Pr}[p_i=0]=\mathrm{Pr}[p_i=0|y=0]\cdot \mathrm{Pr}[y=0]+\mathrm{Pr}[p_i=0|y\ne 0]\cdot \mathrm{Pr}[y\ne 0]$.

Указанные вероятности можно оценить следующим образом:

$\mathrm{Pr}[p_i=0|y=0]=\mathrm{Pr}[r_j=0]=\frac{1}{2}$

$\mathrm{Pr}[p_i=0|y\ne 0]=\mathrm{Pr}[r_j=1\wedge d_{ij}=-y]\le \mathrm{Pr}[r_j=1]=\frac{1}{2}$

Подставляя эти выражения в исходное равенство, можно прийти к:

$\begin{array}{cc}\mathrm{Pr}[p_i=0]& \le \frac{1}{2}\cdot \mathrm{Pr}[y=0]+\frac{1}{2}\cdot \mathrm{Pr}[y\ne 0]\\ & =\frac{1}{2}\cdot \mathrm{Pr}[y=0]+\frac{1}{2}\cdot (1-\mathrm{Pr}[y=0])\\ & =\frac{1}{2}\end{array}$

Таким образом,

$\mathrm{Pr}[\overrightarrow{P}=0]=\mathrm{Pr}[p_1=0\wedge \dots \wedge p_i=0\wedge \dots \wedge p_n=0]\le \mathrm{Pr}[p_i=0]\le \frac{1}{2}.$

См. также

• Лемма Шварца — Зиппеля

Ссылки

• Freivalds, R. (1977), «Probabilistic Machines Can Use Less Running Time», IFIP Congress 1977, pp. 839—842.