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

الگوریتم فریوالد یک الگوریتم تصادفی احتمالاتی در زمینهٔ ضرب ماتریس‌ها ست. ضرب دو ماتریس $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$ «خیر» خواهد بود.

فرایند

1. یک ماتریس تصادفی $n\times 1$ به نام $x$ متشکل از ۰ و ۱ تولید می‌کنیم.
2. در صورت برقراری $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<=1/2$.

در حالتی که $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{aligned}\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{aligned}}$

بنابراین:

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