الگوریتم‌های ضرب ماتریس

مسئله حل نشده در علوم کامپیوتر:

سریع‌ترین الگوریتم برای ضرب ماتریس چیست؟

ضرب ماتریس یکی از اعمال پایه در بسیاری از الگوریتم‌های آنالیز عددی محسوب می‌شود به همین دلیل در راستای بهبود زمان آن تلاش‌های بسیاری انجام شده‌است. کاربردهای ضرب ماتریس در بسیاری از زمینه‌های مختلف همچون علم محاسبه، بازشناخت الگو ، پردازش تصویر ، کار با نرم افزارهای ۳ بعدی و حتی زمینه‌های به ظاهر بی‌ربط مانند شمردن تعداد گشت‌ها در یک گراف دیده می‌شود. الگوریتم‌های بسیاری برای این‌ کار روی سیستم‌های رایانش موازی طراحی شده‌ است که در آن چند هسته به صورت همزمان و موازی عملیات را انجام می‌دهند.

اگر از تعریف ضرب ماتریس به صورت مستقیم استفاده کنیم برای ضرب دو ماتریس $n \times n$ زمان $n 3$ طول خواهد کشید که به صورت $(O(n 3$ می‌توانیم نمایش دهیم. الگوریتم‌هایی با زمان اجرای بهتری برای این‌کار ارائه شده‌اند. برای مثال در ده سال ۱۹۶۹ استراسن در این زمینه الگوریتمی بر پایه ماتریس های 2×2 ارائه داد اما به‌طور کلی هنوز نمی‌دانیم بهترین الگوریتم برای این کار چیست. (در واقع پیچیدگی زمانی آن مشخص نیست)^[۱]

الگوریتم پیمایشی

طبق تعریف ضرب ماتریس می‌توانیم یک الگوریتم برای این کار ارائه دهیم. به ازای ماتریس $A$ که یک ماتریس $n\times m$ است و ماتریس $B$ که یک ماتریس $m\times p$ است می‌خواهیم ماتریس $C=AB$ که ماتریسی $n\times p$ است را محسابه کنیم. طبق تعریف ضرب ماتریس $c_{i,j}=\sum _{k=1}^{m}a_{i,k}\times b_{k,j}$ بنابراین به ازای هر دوتایی $(i,j)$ می‌توانیم با $O(m)$ مقدار $c_{i,j}$ را محاسبه کنیم. یعنی در کل الگوریتمی با زمان اجرای $O(n\times m\times p)$ خواهیم داشت. اگر فرض کنیم هر سه ماتریس $n\times n$ هستند آنگاه الگوریتم $O(n^{3})$ خواهد بود.

1 Input: matrices  $A$  and  $B$ 
2 Let  $C$  be a new matrix of the appropriate size
3 For  $i$  from 1 to  $n$ :
4 For  $j$  from 1 to  $p$ :
5 Let  $sum = 0$ 
6 For  $k$  from 1 to  $m$ :
7 Set  $sum \leftarrow sum + A ik \times B kj$ 
8 Set  $C ij \leftarrow sum$ 
9 Return  $C$

بررسی رفتار حافظه نهان (کش)

در الگوریتم بالا ترتیب حلقه‌ها را می‌توانیم جابه‌جا کنیم. اگر چه این جابه‌جایی در مدت زمان اجرای الگوریتم تأثیری نخواهد داشت اما این ترتیب در بحث‌های مربوط به دسترسی حافظه (access pattern) و مسائل مربوط به استفاده از حافظه نهان پردازنده مهم است. مثلاً اینکه ماتریس‌ها به ترتیب سطری یا ستونی (یا ترکیبی از این دو) ذخیره شوند در زمان حافظهٔ نهان پردازنده تأثیر گذار خواهد بود.

حتی اگر حالت بهینه را در نظر بگیریم که حافظهٔ کش شرکت پذیر کامل با $M$ سطر حافظهٔ $b$ بیتی باشد و ماتریس‌های $A$ و $B$ به صورت سطری ذخیره شده‌باشند، این الگوریتم بهینه نخواهد بود. هنگامی که $n>{\frac {M}{b}}$ از آنجایی که ماتریس‌ها به صورت سطری ذخیره شده‌اند هر پیمایش حلقهٔ داخلی در الگوریتم (یک پیمایش روی سطر ماتریس اول و ستون ماتریس دوم) یک خطای کش به هنگام دسترسی به خانه‌ی‌های ماتریس دوم به همراه خواهد داشت؛ و این به این معناست که الگوریتم در بدترین حالت حاوی $\Theta (n^{3})$ خطای کش خواهد بود. امروزه -یعنی از سال ۲۰۱۰- خطای کش‌ها به نسبت اعمال پردازنده تأثیر بیشتری روی زمان اجرا می‌گذارند بنابراین بهتر است با روشی این خطای کش‌ها را کاهش دهیم.

برای حل این مشکل ماتریس‌ها را به بلوک‌هایی از اردر ${\sqrt {M}}\times {\sqrt {M}}$ تایی تقسیم می‌کنیم. با اینکار کل یک زیرجدول در حافظهٔ کش قرار می‌گیرد و این بلوک‌ها در هم ضرب می‌شوند. ضرب هر بلوکی هیچ خطای کشی به همراه نخواهد داشت.^[۲]

01 Input: matrices  $A$  and  $B$ 
02 Let  $C$  be a new matrix of the appropriate size
03 Pick a tile size  $T = Θ(\sqrt M)$ 
04 For  $I$  from 1 to  $n$  in steps of  $T$ :
05 For  $J$  from 1 to  $p$  in steps of  $T$ :
06 For  $K$  from 1 to  $m$  in steps of  $T$ :
07 Multiply  $A I : I + T, K : K + T$  and  $B K : K + T, J : J + T$  into  $C I : I + T, J : J + T$ , that is:
08 For  $i$  from  $I$  to  $min(I + T, n)$ :
09 For  $j$  from  $J$  to  $min(J + T, p)$ :
10 Let  $sum = 0$ 
11 For  $k$  from  $K$  to  $min(K + T, m)$ :
12 Set  $sum \leftarrow sum + A ik \times B kj$ 
13 Set  $C ij \leftarrow C ij + sum$ 
14 Return  $C$

تعداد خطاهای کش در این مدل برابر ${\frac {n^{3}}{b{\sqrt {M}}}}$ خواهدبود. مخرج $b\times {\sqrt {M}}$ باعث می‌شود در پردازنده‌های جدید خطاهای کش در زمان اجرا تأثیر گذار نشوند و صرفاً تحلیل زمانی الگوریتم تأثیر گذار باشد.^[۳]

الگوریتم تقسیم و حل

حال سعی می‌کنیم روشی تقسیم و حل برای ضرب ماتریس‌ها ارائه دهیم. ابتدا فرض کنید ماتریس‌هایمان $n\times n$ هستند. در این روش مطابق زیر ماتریس‌ها را به چهار بلوک تقسیم می‌کنیم که اندازهٔ آن‌ها تقریباً برابرند.

C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}}

.

اگر ماتریس‌های‌مان اندازه‌شان توانی از دو باشد (یعنی ماتریسی با ابعاد $2^{n}\times 2^{n}$ ) می‌توانیم این الگوریتم را به کار بگیریم. به صورت زیر دو ماتریس را در هم ضرب می‌کنیم.

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}

این الگوریتم شامل ۸ ضرب ماتریس‌های کوچکتر $2^{n-1}\times 2^{n-1}$ خواهد بود که به‌صورت بازگشتی محاسبه می‌شود و پایهٔ آن ضرب اسکالر $c_{1,1}=a_{1,1}\times b_{1,1}$ است. همچنین جمع کردن ماتریس‌ها به صورتی که در بالا گفته‌شده $\Theta (n^{2})$ طول خواهد کشید.

توجه کنید اگر ماتریس ما ابعادش توانی از ۲ نبود باز هم می‌توانیم این الگوریتم را به کار ببریم. کافیست با اضافه کردن سطرهایی تمام صفر و ستون‌هایی تمام صفر به پایین و راست ماتریس ابعادش را توانی از دو کنیم. با اضافه کردن آن‌ها اندازهٔ ماتریس حداکثر ۴ برابر خواهد شد (تعداد ستون‌ها و سطرها هر کدام ۲ برابر خواهند شد) بنابراین تفاوتی در تحلیل زمانی ایجاد نمی‌شود به‌علاوه افزودن سطر و ستون تمام صفر تأثیری در حاصل‌ضرب نخواهدگذاشت.

با توجه به مطالب گفته‌شده برای تحلیل زمانی آن می‌توانیم رابطهٔ زیر را بنویسیم:

T(1)=\Theta (1)

;

T(n)=8T(n/2)+\Theta (n^{2})

،

بر طبق قضیه‌ی اصلی ^[۴] می‌توانیم این الگوریتم را تحلیل زمانی کنیم. می‌دانیم $f(n)=\Theta (n^{2})\subset {\mathcal {O}}(n^{log_{2}8-\varepsilon })$ بنابراین $T(n)=\Theta (n^{3})$ خواهد بود.

در نتیجه این الگوریتم با الگوریتم ابتدایی‌ای که بررسی کردیم تفاوتی از نظر زمانی ندارد.

ماتریس‌های غیر مربعی

این الگوریتم در عمل برای ماتریس‌های غیر مربعی سریع‌تر عمل می‌کند. کافیست به جای تقسیم کردن هر دو ماتریس به چهار تکه یکی از ماتریس‌ها را به دو تکهٔ برابر (یا تقریباً برابر) با تقسیم کردن سطرها یا ستون‌ها تقسیم کنیم. در زیر می‌توانید الگوریتم چنین کاری را ببینید:

 Inputs: matrices  $A$  of size  $n \times m$ ,  $B$  of size  $m \times p$ .
 Base case: if  $max(n, m, p)$  is below some threshold, use an unrolled version ofthe iterative algorithm.
 Recursive cases:
 If  $max(n, m, p) = n$ , split  $A$  horizontally:
        $C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}$ 
 Else, If  $max(n, m, p) = p$ , split  $B$  vertically:
        $C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}$ 
 Otherwise,  $max(n, m, p) = m$ . Split  $A$  vertically and  $B$  horizontally:
        $C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2}$

بررسی رفتار حافظه نهان (کش)

الگوریتم گفته‌شده در این بخش تقسیم‌بندی را تا جایی می‌تواند ادامه دهد که کل ماتریس در حافظهٔ کش جا شوند و بنابراین از نظر تعداد خطاهای کش مانند روش تقسیم‌بندی بلوکی عمل می‌کند. با این تفاوت که در آن الگوریتم خود پیاده‌سازی الگوریتم با توجه به اندازهٔ کش پردازندهٔ هدف انجام می‌شود (پارامتر $\Theta (sqrt{M})$ ای را باید در خود متن الگوریتم تعیین کنیم) در حالیکه این الگوریتم برای کش‌های پویا با اندازه‌های مختلف بهینه‌تر عمل خواهد کرد.

تعداد خطاهای کش در این الگوریتم با $M$ خط حافظهٔ کش که هر خط $b$ بیت دارد به صورت زیر خواهد بود:

\Theta \left(m+n+p+{\frac {mn+np+mp}{b}}+{\frac {mnp}{b{\sqrt {M}}}}\right)

الگوریتم‌های بهتر از $\Theta (n^{3})$

الگوریتم‌هایی وجود دارند که زمان اجرای بهتری از الگوریتم‌های فوق دارند. اولین الگوریتم کشف شده که اینگونه بود الگوریتم استراسن بود که در سال ۱۹۶۹ توسط وولکر استراسن (Volker Strassen) کشف شد. این الگوریتم به «الگوریتم سریع ضرب ماتریس» نیز معروف است. این الگوریتم بر مبنای ضرب دو ماتریس $2\times 2$ با ۷ عملیات ضرب است که در عوض تعداد بیشتری جمع و عملیات ریاضی این‌چنینی لازم دارد. با استفاده از این ایده به‌صورت بازگشتی الگوریتمی از ${\mathcal {O}}(n^{log_{2}7})\approx {\mathcal {O}}(n^{2.807})$ به ما می‌دهد. این الگوریتم پیچیده‌است و ضرایب ثابت آن در تحلیل زمانی به اندازه‌ای زیاد است که تنها برای ماتریس‌های بزرگ کارامدتر از الگوریتم‌های قبلی عمل خواهد کرد.

سریعترین الگوریتم با ${\mathcal {O}}(n^{k})$ الگوریتمی است که از تعمیم الگوریتم کوپراسمیت–وینوگارد به‌دست آمده و از نظر زمانی ${\mathcal {O}}(n^{2.3728639})$ می‌باشد. این الگوریتم توسط François Le Gall کشف شد و به قدری ضرایب زیادی دارد و سربار الگوریتم بالاست که تنها برای ماتریس‌های بسیار بزرگی که هم‌اکنون در علوم کامپیوتر کاربردی ندارند، کارامد خواهد بود.

با توجه به این‌که باید حداقل روی همهٔ اعضای دو ماتریس $n\times n$ پیمایش انجام بشود کران‌پایین $\Omega (n^{2})$ برای الگوریتم‌های ضرب ماتریس وجود دارد. راز (Raz) ثابت کرد که کران پایین $\Omega (n^{2}log_{n})$ نیز برای هر الگوریتم ضرب ماتریس نیز وجود دارد.^[۵]^[۶]^[۷]

همچنین الگوریتم الگوریتم فریوالد یک الگوریتم احتمالی و مونت کارلو است که در ${\mathcal {O}}(n^{2})$ چک می‌کند که آیا ضرب دو ماتریس $A,B$ برابر $C$ هست یا نه.

جستارهای وابسته

منابع

↑ https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm
↑ Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 Performance Engineering of Software Systems, Lecture 8". MIT OpenCourseWare. Massachusetts Institute of Technology. Archived from the original on 22 June 2015. Retrieved 27 January 2015.
↑ Skiena, Steven (2008). "Sorting and Searching". The Algorithm Design Manual. Springer. pp. 45–46, 401–403. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
↑ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
↑ Alon, Shpilka, Umans, On Sunflowers and Matrix Multiplication
↑ Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. آرخیو:math.GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.
↑ Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. آرخیو:math.GR/0307321. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438–449.

[1] ttps://en.wikipedia.org/wiki/Matrix_multiplication_algorithm

[ocw-2] Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 Performance Engineering of Software Systems, Lecture 8". MIT OpenCourseWare. Massachusetts Institute of Technology. Archived from the original on 22 June 2015. Retrieved 27 January 2015.

[skiena-3] Skiena, Steven (2008). "Sorting and Searching". The Algorithm Design Manual. Springer. pp. 45–46, 401–403. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[4] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.

[5] Alon, Shpilka, Umans, On Sunflowers and Matrix Multiplication

[6] Henry Cohn, Robert Kleinberg, Balázs Szegedy, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. آرخیو:math.GR/0511460. Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388.

[7] Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. آرخیو:math.GR/0307321. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438–449.

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

الگوریتم‌های ضرب ماتریس

الگوریتم پیمایشی

بررسی رفتار حافظه نهان (کش)

الگوریتم تقسیم و حل

ماتریس‌های غیر مربعی

بررسی رفتار حافظه نهان (کش)

الگوریتم‌های بهتر از Θ ( n 3 ) {\displaystyle \Theta (n^{3})}

جستارهای وابسته

منابع

الگوریتم‌های بهتر از $\Theta (n^{3})$