الگوریتم استراسن

در جبر خطی الگوریتم استراسن الگوریتمی برای ضرب ماتریس است که برای ماتریس‌های بزرگ سریع‌تر از الگوریتم ضرب ماتریس استاندارد است و پیچیدگی مجانبی بهتری دارد (${\displaystyle O(n^{\log _{2}7})}$ در برابر ${\displaystyle O(n^{3})}$)، البته الگوریتم ساده همچنان برای ماتریس‌های کوچک‌تر بهتر است. الگوریتم استراسن از سریع‌ترین الگوریتم شناخته‌شده برای ماتریس‌های بسیار بزرگ کندتر است، اما آن الگوریتم‌های کهکشانی در عمل مفید نیستند، زیرا برای ماتریس‌های در اندازه‌های رایج بسیار کندترند. برای ماتریس‌های کوچک، الگوریتم‌های سریع‌تری نیز هست.

الگوریتم استراسن برای هر حلقه‌ای، مانند جمع/ضرب، جواب می‌دهد، ولی برای همه‌ی نیم‌حلقه‌ها، مانند جبر کمینه جمع یا جبر بولی، که در آن‌ها الگوریتم ساده جواب می‌دهد، جواب نمی‌دهد.

ولکر استراسن الگوریتم استراسن را در سال ۱۹۶۹ منتشر کرد. او نخستین کسی بود که نشان داد الگوریتم رایج مرتبه ${\displaystyle n^{3}}$ بهینه نیست.

فرض کنید ${\displaystyle A}$, ${\displaystyle B}$ دو ماتریس مربعی روی یک حلقه ${\displaystyle {\mathcal {R}}}$،برای نمونه ماتریس‌هایی که عنصرهایشان عدد صحیح یا حقیقی است، باشند. هدف ضرب ماتریس محاسبه ماتریس ${\displaystyle C=AB}$ است. این توضیح الگوریتم فرض می‌کند که اندازه‌ی ماتریس‌ها توان‌های ۲ است (یعنی ${\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})}$). اگر ماتریس‌های ${\displaystyle A}$, ${\displaystyle B}$ با اندازه‌‌های ${\displaystyle 2^{n}\times 2^{n}}$ نباشند، ردیف‌ها و ستون‌های خالی را می‌توان با صفر پر کرد تا به این اندازه برسند - گرچه پیاده‌سازی‌های واقعی این الگوریتم در عمل این کار را نمی‌کنند.

الگوریتم ${\displaystyle A}$, ${\displaystyle B}$ و ${\displaystyle C}$ را به ماتریس‌های بلوکی هم اندازه افراز می‌کند:${\displaystyle A={\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}},\quad B={\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}},\quad C={\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}},\quad }$

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

${\displaystyle {\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}A_{11}{\color {red}\times }B_{11}+A_{12}{\color {red}\times }B_{21}\quad &A_{11}{\color {red}\times }B_{12}+A_{12}{\color {red}\times }B_{22}\\A_{21}{\color {red}\times }B_{11}+A_{22}{\color {red}\times }B_{21}\quad &A_{21}{\color {red}\times }B_{12}+A_{22}{\color {red}\times }B_{22}\end{bmatrix}}.}$

با این ساختار، تعداد ضرب‌ها کاهش نیافته است. هنوز هم به ۸ ضرب نیاز است تا ماتریس‌های ${\displaystyle C_{ij}}$ محاسبه شود.

استراسن این ماتریس‌های جدید را تعریف می‌کند:

${\displaystyle {\begin{aligned}M_{1}&=(A_{11}+A_{22}){\color {red}\times }(B_{11}+B_{22});\\M_{2}&=(A_{21}+A_{22}){\color {red}\times }B_{11};\\M_{3}&=A_{11}{\color {red}\times }(B_{12}-B_{22});\\M_{4}&=A_{22}{\color {red}\times }(B_{21}-B_{11});\\M_{5}&=(A_{11}+A_{12}){\color {red}\times }B_{22};\\M_{6}&=(A_{21}-A_{11}){\color {red}\times }(B_{11}+B_{12});\\M_{7}&=(A_{12}-A_{22}){\color {red}\times }(B_{21}+B_{22}),\\\end{aligned}}}$

با بیان ${\displaystyle C_{ij}}$ به کمک ${\displaystyle M_{k}}$ می‌توان یک ضرب ماتریس را حذف کرد و تعداد ضرب‌ها را به ۷ کاهش داد (یک ضرب برای هر ${\displaystyle M_{k}}$):

${\displaystyle {\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}\quad &M_{3}+M_{5}\\M_{2}+M_{4}\quad &M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.}$

این فرآیند تقسیم به صورت بازگشتی تکرار شده تا زیرماتریس‌ها به عدد (عنصر‌های حلقه ${\displaystyle {\mathcal {R}}}$) تبدیل شوند. اگر ماتریس اصلی اندازه‌ای جز توان‌های ۲ داشته باشد، آنگاه نتیجه مانند خود ${\displaystyle A}$ و ${\displaystyle B}$ سطر و ستون صفر خواهد داشت. این سطرها و ستون‌ها زدوده می‌شوند تا ماتریس (کوچکتر) ${\displaystyle C}$ که نتیجه اصلی ضرب است به دست آید.

در پیاده‌سازی‌های عملی الگوریتم استراسن برای زیرماتریس‌های به اندازه کافی کوچک از روش‌های استاندارد ضرب ماتریس استفاده می‌شود. نقطه‌ای که الگوریتم استراسن برای آن اندازه به بعد کارآمدتر است، به پیاده‌سازی و سخت‌افزار بستگی دارد. نویسندگان پیش‌تر تخمین زده بودند که الگوریتم استراسن برای ماتریس‌های با اندازه‌ی ۳۲ تا ۱۲۸ برای پیاده‌سازی‌های بهینه‌شده از روش استاندارد سریع‌تر است ولی مشاهده شده است که این نقطه در سال‌های گذشته رو به افزایش بوده است. پژوهشی در سال ۲۰۱۰ نشان داد که حتی یک گام از الگوریتم استراسن در معماری‌های فعلی، در مقایسه با یک ضرب ساده‌ی بسیار بهینه‌شده، تا زمانی که اندازه‌ی ماتریس‌ها از ۱۰۰۰ بیشتر نشود، سودمند نیست و حتی برای ماتریس با اندازه‌ی چند هزار، این سودمندی در بهترین حالت حاشیه‌ای است (حدود ۱۰ درسد یا کمتر). پژوهشی جدیدتر (۲۰۱۶) سودمندی را برای ماتریس‌هایی به کوچکی 512 و به میزان حدود ۲۰ درسد مشاهده کرد.

ضرب ماتریسی استاندارد تقریباً عملیات محاسباتی ۲n^۳ (که n=۲^n) (جمعها و ضرب‌ها) را می‌پذیرد؛ پیچیدگی مجانبی (O(N۳می‌باشد. تعداد جمع‌ها و ضرب‌های مورد نیاز در الگوریتم استراسن را می‌توان به صورت زیر محاسبه کرد:

فرض کنید (f(n تعداد عملیات برای یک ماتریس ۲ⁿ * ۲ⁿ باشد. آنگاه با عملیات بازگشتی الگوریتم استراسن می‌بینیم که برای برخی l ثابت که به تعداد جمع‌های انجام شده در هر عملیات الگوریتم وابسته‌است. یعنی پیچیدگی مجانبی برای ضرب ماتریسها با استفاده از الگوریتم استراسن ${\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})}$ است. هرچند کاهش در تعداد عملیات محاسباتی تا حدودی به بهای کاهش ثبات عددی می‌باشد.

• نمایش ماتریس Z-order

• استراسن، ولکر، حذف گاوسی بهینه نیست، ص ۳۵۴-۳۵۶، ۱۹۶۹
• تامس اچ. کردمن، چارلز ای. لایسرسون، رانلد ال. روست، کلیفورد استاین، آشنایی با الگوریتم، ویرایش دوم، انتشارات موسسه فناوری ماساچوست، فصل ۲۸، الگوریتم استراسن برای ضرب ماتریس، ص ۷۳۴-۷۴۱، ۲۰۰۱

• ویستین اچ. اریک، فرمول‌های استراسن بایگانی‌شده در ۱۴ فوریه ۲۰۱۵ توسط Wayback Machine، (همچنین شامل فرمول برای وارونگی ماتریس سریع)
• تیلر جی. ارنست،الگوریتم استراسن در موتور پهنای باند همراه
• پیاده‌سازی ساده الگوریتم استراسن درC، (آسان برای اهداف آموزش و پرورش)