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

والکر استراسن الگوریتم استراسن را در سال ۱۹۶۹ منتشر کرد. اگرچه الگوریتم او فقط کمی سریع تر از الگوریتم‌های استاندارد برای ضرب ماتریس است، اما او اولین کسی بود که اشاره کرد رویکرد استاندارد مطلوب نمی‌باشد. مقالهٔ او به جستجوی الگوریتم‌های سریعتر مانند الگوریتم پیچیده تر Coppersmith–Winograd منتشر شده در سال ۱۹۸۷ پرداخت.

الگوریتم

ستون سمت چپ، ضرب ماتریسی ۲x۲ را نشان می‌دهد. ضرب ماتریسی Naïve به یک ضرب برای هر “۱” از ستون سمت چپ نیاز دارد. هر یک از ستون‌های دیگر نشان دهندهٔ یک واحد از ۷ ضرب در الگوریتم می‌باشند و از مجموع ستون‌ها، ضرب ماتریس کامل در سمت چپ حاصل می‌شود.

بگذارید A،B دو ماتریس مربعی در یک حلقه R باشند. ما می‌خواهیم حاصل ماتریس C را به صورت زیر محاسبه کنیم:

اگر ماتریس‌های A،B از نوع ۲ⁿ * ۲ⁿ نباشند، ما ردیف‌ها و ستون‌های خالی را با صفر پر می‌کنیم.

ما A،B و C را به ماتریس‌های بلوکی هم سایز تجزیه می‌کنیم.

ما با این ساختار، تعداد ضرب‌ها را کاهش ندادیم. هنوز هم به ۸ ضرب نیاز داریم تا ماتریس‌های Ci،j را محاسبه کنیم، زمانی که از ضرب ماتریسی استاندارد استفاده می‌کنیم نیز به همان تعداد ضرب نیاز داریم.

حالا بخش مهم در اینجا آمده‌است. ما ماتریس‌های جدید را به شرح زیر تعریف می‌کنیم:

که سپس برای بیان C_i،j به صورت M_k مورد استفاده قرار می‌گیرند. با تعریف مان از M_k می‌توانیم یک ضرب ماتریس را حذف کنیم و تعداد ضرب‌ها را به ۷ کاهش دهیم (یک ضرب برای هر Mk) و Ci،j را به صورت زیر بیان کنیم:

${\begin{aligned}C_{1,1}=M_{1}+M_{4}-M_{5}+M_{7}\\C_{1,2}=M_{3}+M_{5}\\C_{2,1}=M_{2}+M_{4}\\C_{2,2}=M_{1}-M_{2}+M_{3}+M_{6}\end{aligned}}$

ما این فرایند تقسیم را n بار تکرار می‌کنیم تا زمانی که ماتریس‌های فرعی به اندازه کافی کوچک شده و قابل تقسیم نباشند. (اجزای حلقه R).

کاربردهای عملی الگوریتم استراسن با روش‌های استاندارد ضرب ماتریسی برای ماتریس‌های فرعی کوچک تعویض شدند که آن الگویتم‌ها برایشان موثرتر می‌باشند. نقطه هم گذری خاص که الگوریتم‌های استراسن برایشان موثرتر است به کاربرد و سخت‌افزار ویژه بستگی دارد.

پیچیدگی مجانبی

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

اجازه دهید (f(n تعداد عملیات برای یک ماتریس ۲ⁿ * ۲ⁿ باشد. آنگاه با عملیات بازگشتی الگوریتم استراسن می‌بینیم که برای برخی l ثابت که به تعداد جمع‌های انجام شده در هر عملیات الگوریتم وابسته‌است. یعنی پیچیدگی مجانبی برای ضرب ماتریسها با استفاده از الگوریتم استراسن به شرح زیر است:

هرچند کاهش در تعداد عملیات محاسباتی تا حدودی به بهای کاهش ثبات عددی می‌باشد.

همچنین مشاهده کنید

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

منابع

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

پیوند به بیرون

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