الگوریتم فریوالد

**الگوریتم فریوالد** یک الگوریتم تصادفی احتمالاتی در زمینهٔ ضرب ماتریس‌ها ست. ضرب دو ماتریس n × n به روش معمول از مرتبهٔ زمانی O(n^3) است زیرا هر یک از n^2 درایهٔ ماتریس اول در n درایه از ماتریس دوم ضرب می‌شود. یکی از نیازهای رایج در اعمال ریاضی مختلف در ماتریس‌ها، بررسی این موضوع است که اگر سه ماتریس A، B و C داشته باشیم آیا A \times B = C. یک راه ساده محاسبهٔ A \times B با روش رایج و چک کردن برابری درایه به درایهٔ آن با C است. این روش، قطعی است و خطایی ندارد اما برای nهای بزرگ بسیار زمان‌بر است. بهترین الگوریتم قطعی ارائه شده برای این کار از مرتبهٔ زمانی O(n^{2.3729}) است. الگوریتم فریوالد، به وسیلهٔ یک فرایند تصادفی، این مرتبهٔ زمانی را تا O(n^2) کاهش می‌دهد و در k بار اجرای الگوریتم، احتمال خطای آن کم‌تر از 2^{-k} است.

## الگوریتم
سه ماتریس A، B و C داریم. یک ماتریس تصادفی n \times 1 به نام x متشکل از ۰ و ۱ تولید می‌کنیم. خروجی این الگوریتم برای A \times (Bx) = Cx «بله» و برای A \times (Bx) \neq Cx «خیر» خواهد بود.

### فرایند
# یک ماتریس تصادفی n \times 1 به نام x متشکل از ۰ و ۱ تولید می‌کنیم.
# در صورت برقراری A \times (Bx) = Cx، خروجی «بله» و در غیر اینصورت «خیر» خواهد بود.

## مثال
برای مثال سه ماتریس
 A = \begin{bmatrix}2 & 3 \\ 3 & 4\end{bmatrix} 
و
 B = \begin{bmatrix}1 & 0 \\ 1 & 2\end{bmatrix} 
و
 C = \begin{bmatrix}6 & 5 \\ 8 & 7\end{bmatrix} 
را در نظر بگیرید. می‌خواهیم A \times B \stackrel{?}{=} C را بررسی کنیم.

ماتریس تصادفی را x = \begin{bmatrix}1 \\ 1 \end{bmatrix} در نظر می‌گیریم؛ بنابراین:

 Bx = \begin{bmatrix}1 & 0 \\ 1 & 2\end{bmatrix} \begin{bmatrix}1 \\ 1 \end{bmatrix} = \begin{bmatrix}1 \\ 3 \end{bmatrix} 

 \Rightarrow A \times (Bx) = \begin{bmatrix}2 & 3 \\ 3 & 4\end{bmatrix} \begin{bmatrix}1 \\ 3 \end{bmatrix} = \begin{bmatrix}11 \\ 15 \end{bmatrix}

 Cx = \begin{bmatrix}6 & 5 \\ 8 & 7\end{bmatrix} \begin{bmatrix}1 \\ 1\end{bmatrix} = \begin{bmatrix}11 \\ 15 \end{bmatrix} 

بنابراین طبق روابط بالا A \times (Bx) = Cx و خروجی الگوریتم «بله» خواهد بود. اگر ماتریس تصادفی را x = \begin{bmatrix}1 \\ 0 \end{bmatrix} در نظر می‌گرفتیم، آنگاه:

A \times (Bx) = \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}2 & 3 \\ 3 & 4\end{bmatrix} \begin{bmatrix}1 \\ 1\end{bmatrix} = \begin{bmatrix}5 \\ 7\end{bmatrix} 

 Cx = \begin{bmatrix}6 & 5 \\ 8 & 7\end{bmatrix} \begin{bmatrix}1 \\ 0\end{bmatrix} = \begin{bmatrix}6 \\ 8 \end{bmatrix} 

که در این حالت A \times (Bx) \neq Cx و خروجی الگوریتم «نه» خواهد بود. در این مثال، کل حالات برای ماتریس x چهار حالت است که در نصف حالات (x = \begin{bmatrix}1 \\ 1 \end{bmatrix} و x = \begin{bmatrix}0 \\ 0 \end{bmatrix}) خروجی الگوریتم «بله» و برای دو حالت دیگر خروجی «نه» خواهد بود؛ بنابراین در یک بار اجرای الگوریتم، به احتمال  1/2  خروجی الگوریتم «بله» خواهد بود که خروجی اشتباهی است. حال در صورتی که این الگوریتم را k بار اجرا کنیم، اگر تنها یک بار خروجی الگوریتم «نه» باشد، نشان می‌دهد که A \times B \neq C. بنابراین به احتمال  {1/2}^k هر k خروجی الگوریتم «بله» خواهد بود و پاسخی اشتباه می‌دهد که با زیاد کردن k این احتمال خطا بسیار اندک می‌شود.

## تحلیل خطا
فرض کنید  p  احتمال خطا در این الگوریتم باشد. ما اثبات می‌کنیم اگر A \times B = C،  p = 0  و اگر A \times B \neq C،  p .

; در حالتی که A \times B = C
:\vec{L} = A \times (Bx) - Cx = (A \times B)x - Cx

\Leftrightarrow \vec{L} = (A \times B - C)x = 0

\Rightarrow  A \times (Bx) = Cx 

در این حالت مستقل از مقدار درایه‌های  x ، همیشه رابطه فوق برقرار است بنابراین:

\Pr[A \times (Bx) \neq Cx] = 0

یعنی احتمال خطا در این حالت صفر است.

; در حالتی که A \times B \neq C
فرض کنید \vec{L} = D \times \vec{x} = (l_1, l_2, \dots, l_n)^T

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

جون A \times B \neq C، پس درایه‌ای از ماتریس D وجود دارد که صفر نیست. فرض می‌کنیم d_{ij} \neq 0. بنابراین طبق تعریف ضرب ماتریس‌ها داریم:

:l_i = \sum_{k = 1}^n d_{ik}x_k = d_{i1}x_1 + \cdots + d_{ij}x_j + \cdots + d_{in}x_n = d_{ij}x_j + y

که y مقداری ثابت است. طبق قضیه بیز داریم:

\Pr[l_i = 0] = \Pr[y = 0]\cdot \Pr[l_i = 0 | y = 0]\, +\, \Pr[y \neq 0] \cdot \Pr[l_i = 0 | y \neq 0]

داریم:

:\Pr[l_i = 0 | y = 0] = \Pr[x_j = 0] = \frac{1}{2}
:\Pr[l_i = 0 | y \neq 0] = \Pr[x_j = 1 \land d_{ij}=-y] \leq \Pr[x_j = 1] = \frac{1}{2}

بنابراین با جایگذاری دو رابطه بالا در معادله داریم:

:
\begin{align}
\Pr[l_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}


بنابراین:
:\Pr[\vec{L} = 0] = \Pr[l_1 = 0 \land \dots \land l_i = 0 \land \dots \land l_n = 0] \leq \Pr[l_i = 0] \leq \frac{1}{2}.
در نتیجه اثبات شد در این حالت احتمال اینکه الگوریتم خروجی اشتباه بدهد کوچک‌تر یا مساوی 1/2 است.

## جمع‌بندی
مرتبه‌زمانی اجرای الگوریتم احتمالاتی فریوالد از o(n^2) است در صورتی که بهترین الگوریتم قطعی معرفی شده برای این کار از مرتبهٔ زمانی O(n^{2.3729}) است. با توجه به اثبات ارائه شده، احتمال خطای الگوریتم فریوالد در هر بار اجرا کم‌تر یا مساوی 1/2 است که با k بار اجرای الگوریتم می‌توان به کران بالای {1/2}^k برای خطا رسید که برای kهای بزرگ مقداری ناچیز و قابل قبول است.

## مقایسهٔ جالب
: الگوریتم مرتب‌سازی سریع همیشه صحیح عمل می‌کند، اما با احتمال بسیار کم ممکن است کند اجرا شود.
: الگوریتم فریوالد همیشه سریع است، اما با احتمال بسیار کم ممکن است پاسخ نادرست بدهد.

## جستارهای وابسته
* الگوریتم کوپراسمیت–وینوگارد

## پانویس

## منابع
** https://courses.cs.washington.edu/courses/cse312 ,---
* Freivalds, R. (1977), “Probabilistic Machines Can Use Less Running Time”, IFIP Congress 1977, pp. 839–842.

رده:الگوریتم‌ها
رده:الگوریتم‌های تصادفی
رده:الگوریتم‌های ضرب ماتریس
رده:ماتریس‌ها