الگوریتم‌های ضرب ماتریس کیست؟ توضیح بده.
ضرب ماتریس یکی از اعمال پایه در بسیاری از الگوریتم‌های آنالیز عددی محسوب می‌شود به همین دلیل در راستای بهبود زمان آن تلاش‌های بسیاری انجام شده‌است. کاربردهای ضرب ماتریس در بسیاری از زمینه‌های مختلف همچون علم محاسبه، بازشناخت الگو ، پردازش تصویر ، کار با نرم افزارهای ۳ بعدی و حتی زمینه‌های به ظاهر بی‌ربط مانند شمردن تعداد گشت‌ها در یک گراف دیده می‌شود. الگوریتم‌های بسیاری برای این‌ کار روی سیستم‌های رایانش موازی طراحی شده‌ است که در آن چند هسته به صورت همزمان و موازی عملیات را انجام می‌دهند.اگر از تعریف ضرب ماتریس به صورت مستقیم استفاده کنیم برای ضرب دو ماتریس زمان طول خواهد کشید که به صورت می‌توانیم نمایش دهیم. الگوریتم‌هایی با زمان اجرای بهتری برای این‌کار ارائه شده‌اند. برای مثال در ده سال ۱۹۶۹ استراسن در این زمینه الگوریتمی بر پایه ماتریس های 2×2 ارائه داد اما به‌طور کلی هنوز نمی‌دانیم بهترین الگوریتم برای این کار چیست. (در واقع پیچیدگی زمانی آن مشخص نیست)الگوریتم پیمایشی.طبق تعریف ضرب ماتریس می‌توانیم یک الگوریتم برای این کار ارائه دهیم. به ازای ماتریسformula_1که یک ماتریسformula_2است و ماتریسformula_3که یک ماتریسformula_4است می‌خواهیم ماتریسformula_5که ماتریسیformula_6است را محسابه کنیم. طبق تعریف ضرب ماتریسformula_7بنابراین به ازای هر دوتاییformula_8می‌توانیم باformula_9مقدارformula_10را محاسبه کنیم. یعنی در کل الگوریتمی با زمان اجرایformula_11خواهیم داشت. اگر فرض کنیم هر سه ماتریسformula_12هستند آنگاه الگوریتمformula_13خواهد بود. 1 Input: matrices and 2 Let be a new matrix of the appropriate size 3 For from 1 to : 4 For from 1 to : 5 Let 6 For from 1 to : 7 Set 8 Set 9 Return بررسی رفتار حافظه نهان (کش).در الگوریتم بالا ترتیب حلقه‌ها را می‌توانیم جابه‌جا کنیم. اگر چه این جابه‌جایی در مدت زمان اجرای الگوریتم تأثیری نخواهد داشت اما این ترتیب در بحث‌های مربوط به دسترسی حافظه (access pattern) و مسائل مربوط به استفاده از حافظه نهان پردازنده مهم است. مثلاً اینکه ماتریس‌ها به ترتیب سطری یا ستونی (یا ترکیبی از این دو) ذخیره شوند در زمان حافظهٔ نهان پردازنده تأثیر گذار خواهد بود.حتی اگر حالت بهینه را در نظر بگیریم که حافظهٔ کش شرکت پذیر کامل باformula_14سطر حافظهٔformula_15بیتی باشد و ماتریس‌هایformula_16وformula_17به صورت سطری ذخیره شده‌باشند، این الگوریتم بهینه نخواهد بود. هنگامی کهformula_18از آنجایی که ماتریس‌ها به صورت سطری ذخیره شده‌اند هر پیمایش حلقهٔ داخلی در الگوریتم (یک پیمایش روی سطر ماتریس اول و ستون ماتریس دوم) یک خطای کش به هنگام دسترسی به خانه‌ی‌های ماتریس دوم به همراه خواهد داشت؛ و این به این معناست که الگوریتم در بدترین حالت حاویformula_19خطای کش خواهد بود. امروزه -یعنی از سال ۲۰۱۰- خطای کش‌ها به نسبت اعمال پردازنده تأثیر بیشتری روی زمان اجرا می‌گذارند بنابراین بهتر است با روشی این خطای کش‌ها را کاهش دهیم.برای حل این مشکل ماتریس‌ها را به بلوک‌هایی از اردرformula_20تایی تقسیم می‌کنیم. با اینکار کل یک زیرجدول در حافظهٔ کش قرار می‌گیرد و این بلوک‌ها در هم ضرب می‌شوند. ضرب هر بلوکی هیچ خطای کشی به همراه نخواهد داشت. 01 Input: matrices and 02 Let be a new matrix of the appropriate size 03 Pick a tile size 04 For from 1 to in steps of : 05 For from 1 to in steps of : 06 For from 1 to in steps of : 07 Multiply and into , that is: 08 For from to : 09 For from to : 10 Let 11 For from to : 12 Set 13 Set 14 Return تعداد خطاهای کش در این مدل برابرformula_21خواهدبود. مخرجformula_22باعث می‌شود در پردازنده‌های جدید خطاهای کش در زمان اجرا تأثیر گذار نشوند و صرفاً تحلیل زمانی الگوریتم تأثیر گذار باشد.الگوریتم تقسیم و حل.حال سعی می‌کنیم روشی تقسیم و حل برای ضرب ماتریس‌ها ارائه دهیم. ابتدا فرض کنید ماتریس‌هایمانformula_12هستند. در این روش مطابق زیر ماتریس‌ها را به چهار بلوک تقسیم می‌کنیم که اندازهٔ آن‌ها تقریباً برابرند.اگر ماتریس‌های‌مان اندازه‌شان توانی از دو باشد (یعنی ماتریسی با ابعادformula_25) می‌توانیم این الگوریتم را به کار بگیریم. به صورت زیر دو ماتریس را در هم ضرب می‌کنیم.این الگوریتم شامل ۸ ضرب ماتریس‌های کوچکترformula_27خواهد بود که به‌صورت بازگشتی محاسبه می‌شود و پایهٔ آن ضرب اسکالرformula_28است. همچنین جمع کردن ماتریس‌ها به صورتی که در بالا گفته‌شدهformula_29طول خواهد کشید.توجه کنید اگر ماتریس ما ابعادش توانی از ۲ نبود باز هم می‌توانیم این الگوریتم را به کار ببریم. کافیست با اضافه کردن سطرهایی تمام صفر و ستون‌هایی تمام صفر به پایین و راست ماتریس ابعادش را توانی از دو کنیم. با اضافه کردن آن‌ها اندازهٔ ماتریس حداکثر ۴ برابر خواهد شد (تعداد ستون‌ها و سطرها هر کدام ۲ برابر خواهند شد) بنابراین تفاوتی در تحلیل زمانی ایجاد نمی‌شود به‌علاوه افزودن سطر و ستون تمام صفر تأثیری در حاصل‌ضرب نخواهدگذاشت.با توجه به مطالب گفته‌شده برای تحلیل زمانی آن می‌توانیم رابطهٔ زیر را بنویسیم:بر طبق قضیه‌ی اصلی می‌توانیم این الگوریتم را تحلیل زمانی کنیم. می‌دانیمformula_32بنابراینformula_33خواهد بود.در نتیجه این الگوریتم با الگوریتم ابتدایی‌ای که بررسی کردیم تفاوتی از نظر زمانی ندارد.ماتریس‌های غیر مربعی.این الگوریتم در عمل برای ماتریس‌های غیر مربعی سریع‌تر عمل می‌کند. کافیست به جای تقسیم کردن هر دو ماتریس به چهار تکه یکی از ماتریس‌ها را به دو تکهٔ برابر (یا تقریباً برابر) با تقسیم کردن سطرها یا ستون‌ها تقسیم کنیم. در زیر می‌توانید الگوریتم چنین کاری را ببینید: Inputs: matrices of size , of size . Base case: if is below some threshold, use an unrolled version ofthe iterative algorithm. Recursive cases: If , split horizontally: formula_34 Else, If , split vertically: formula_35 Otherwise, . Split vertically and horizontally: formula_36بررسی رفتار حافظه نهان (کش).الگوریتم گفته‌شده در این بخش تقسیم‌بندی را تا جایی می‌تواند ادامه دهد که کل ماتریس در حافظهٔ کش جا شوند و بنابراین از نظر تعداد خطاهای کش مانند روش تقسیم‌بندی بلوکی عمل می‌کند. با این تفاوت که در آن الگوریتم خود پیاده‌سازی الگوریتم با توجه به اندازهٔ کش پردازندهٔ هدف انجام می‌شود (پارامترformula_37ای را باید در خود متن الگوریتم تعیین کنیم) در حالیکه این الگوریتم برای کش‌های پویا با اندازه‌های مختلف بهینه‌تر عمل خواهد کرد.تعداد خطاهای کش در این الگوریتم باformula_14خط حافظهٔ کش که هر خطformula_15بیت دارد به صورت زیر خواهد بود:الگوریتم‌های بهتر از formula_41.الگوریتم‌هایی وجود دارند که زمان اجرای بهتری از الگوریتم‌های فوق دارند. اولین الگوریتم کشف شده که اینگونه بود الگوریتم استراسن بود که در سال ۱۹۶۹ توسط وولکر استراسن (Volker Strassen) کشف شد. این الگوریتم به «الگوریتم سریع ضرب ماتریس» نیز معروف است. این الگوریتم بر مبنای ضرب دو ماتریسformula_42با ۷ عملیات ضرب است که در عوض تعداد بیشتری جمع و عملیات ریاضی این‌چنینی لازم دارد. با استفاده از این ایده به‌صورت بازگشتی الگوریتمی ازformula_43به ما می‌دهد. این الگوریتم پیچیده‌است و ضرایب ثابت آن در تحلیل زمانی به اندازه‌ای زیاد است که تنها برای ماتریس‌های بزرگ کارامدتر از الگوریتم‌های قبلی عمل خواهد کرد.سریعترین الگوریتم باformula_44الگوریتمی است که از تعمیم الگوریتم کوپراسمیت–وینوگارد به‌دست آمده و از نظر زمانیformula_45می‌باشد. این الگوریتم توسط François Le Gall کشف شد و به قدری ضرایب زیادی دارد و سربار الگوریتم بالاست که تنها برای ماتریس‌های بسیار بزرگی که هم‌اکنون در علوم کامپیوتر کاربردی ندارند، کارامد خواهد بود.با توجه به این‌که باید حداقل روی همهٔ اعضای دو ماتریسformula_12پیمایش انجام بشود کران‌پایینformula_47برای الگوریتم‌های ضرب ماتریس وجود دارد. راز (Raz) ثابت کرد که کران پایینformula_48نیز برای هر الگوریتم ضرب ماتریس نیز وجود دارد.همچنین الگوریتم الگوریتم فریوالد یک الگوریتم احتمالی و مونت کارلو است که درformula_49چک می‌کند که آیا ضرب دو ماتریسformula_50برابرformula_51هست یا نه.