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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

الگوریتم[ویرایش]

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

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

AL-2.JPG

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

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

AL-3.JPG

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

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

AL-4.JPG

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

AL-5.JPG

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

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

پیچیدگی مجانبی[ویرایش]

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

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

AL-6.JPG

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

همچنین مشاهده کنید[ویرایش]

منابع[ویرایش]

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

پیوند به بیرون[ویرایش]