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

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

  

✤  الگوریتم ضرب استراسن

همه ما با تعریف ضرب ماتریس‌های مربعی آشنایی داریم. حاصلضرب ماتریس‌های مربعی A و B به صورت زیر تعریف می‌شود:

  

\[ A=(a_{ij})_{n \times n} \qquad , \qquad B=(b_{ij})_{n \times n} \] \[ C = A \times B = (c_{ij})_{n \times n} \qquad ; \qquad c_{ij}= \sum_{k=1}^{n} a_{ik} \; b{kj} \]

  

به عنوان مثال در حالت $n = 2$ داریم:

  

\[ \begin{pmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{pmatrix} \times \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} \]

  

همانگونه که از تعریف پیداست، برای محاسبه هر درایه نیاز به $n$ عمل ضرب داریم. بنابراین برای محاسبه تمامی $n^2$ درایه ماتریس C به $n^3$ عمل ضرب نیاز خواهیم داشت. یعنی الگوریتم ضرب ماتریس‌ها با تعریف اصلی آن از مرتبه $O(n^3)$ است.

قبل از ادامه بحث به مثال زیر توجه کنید:

  

\[ A = \begin{pmatrix} 1 & 2 & 0 \\ 5 & 1 & 9 \\ -2 & 2 & 4 \end{pmatrix} \; \leftrightarrow \; A^\prime \begin{pmatrix} 1 & 2 & 0 & 0 \\ 5 & 1 & 9 & 0 \\ -2 & 2 & 4 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \] \[ B = \begin{pmatrix} -1 & 2 & 3 \\ 0 & 6 & 5 \\ 10 & 3 & 1 \end{pmatrix} \; \leftrightarrow \; B^\prime \begin{pmatrix} -1 & 2 & 3 & 0 \\ 0 & 6 & 5 & 0 \\ 10 & 3 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \] \[ C = A \times B = \begin{pmatrix} -1 & 14 & 13 \\ 85 & 43 & 29 \\ 42 & 20 & 8 \end{pmatrix} \; \leftrightarrow \; C^\prime = A^\prime \times B^\prime = \begin{pmatrix} -1 & 14 & 13 & 0 \\ 85 & 43 & 29 & 0 \\ 42 & 20 & 8 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \]

  

این مثال نشان می‌دهد که اضافه کردن سطرها و ستون‌های صفر به ماتریس، تاثیری در جواب نهایی حاصلضرب ندارد. این مطلب را به صورت منطقی و عبارات ریاضی هم می‌توان ثابت کرد.

حال فرض کنید $n$ توانی از عدد دو باشد. اگر اینطور نبود با اضافه کردن تعداد مناسبی از سطرها و ستون‌های صفر مرتبه ماتریس‌ها را به توانی از عدد 2 می‌رسانیم. سپس هر کدام از ماتریس‌های A و B را به چهار زیر ماتریس به فرم زیر تقسیم می‌کنیم:

  

\[ \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{pmatrix} \qquad , \qquad \begin{pmatrix} B_{11} & B_{12}\\ B_{21} & B_{22} \end{pmatrix} \]

  

به راحتی می‌توان ثابت کرد:

  

\[ C = A \times B = \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} \]

  

اما آیا این تقسیم‌بندی تاثیری در بهینه شدن تعداد محاسبات دارد؟

فرض کنیم $T(n)$ تعداد ضربهای لازم برای محاسبه حاصلضرب این دو ماتریس - با استفاده از زیرماتریس‌ها - باشد. پس داریم:

  

\[ T(n) = 8 \; T \Big( \frac{n}{2} \Big) \qquad , \qquad T(1) = 1 \]

  

با حل این رابطه بازگشتی به نتیجه زیر می‌رسیم:

  

\[ T(n) =  8 \; T \Big( \frac{n}{2} \Big) =  8^2 \; T \Big( \frac{n}{2^2} \Big) = \cdots =  8^k \; T \Big( \frac{n}{2^k} \Big) \] \[ n = 2 ^ k \; \Rightarrow \; T(n) = 8 ^ k \; T( \frac{n}{n} ) = {(2^3)}^k \; T(1) = {(2^k)}^3 \times 1 = n ^ 3 \]

  

که نشان می‌دهد همچنان $n^3$ عمل ضرب برای محاسبه حاصلضرب نیاز است.

ولکر استراسن با بررسی‌هایی که انجام داد، الگوریتم تقسیم و غلبه‌ای برای ضرب ماتریس‌ها با استفاده از تقسیم‌بندی ارائه داد که به جای هشت عمل ضرب در هر مرحله، هفت عمل نیاز دارد. به این ترتیب:

  

\[ T^\prime(n) =  7 \; T^\prime \Big( \frac{n}{2} \Big) =  7^2 \; T^\prime \Big( \frac{n}{2^2} \Big) = \cdots =  7^k \; T^\prime \Big( \frac{n}{2^k} \Big) \] \[ n = 2 ^ k \; \Rightarrow \; T^\prime(n) = 7 ^ k \; T^\prime( \frac{n}{n} ) = {(2^{log_27})}^k \; T^\prime(1) = {(2^k)}^{log_27} \times 1 = n ^ {log_27} \]

  

در نتیجه مرتبه اجرای الگوریتم به $O(n^{2.81})$ تبدیل می‌شود. به عنوان مثال اگر n برابر 1024 باشد:

  

\[ n = 1024 = 2^{10} \Rightarrow k = 10 \] \[ T(1024) = 8 ^{10} = 1073741824 \] \[ T^\prime(1024) = 7 ^{10} = 282475249 \] \[ \frac{T(1024)}{T^\prime(1024)} \simeq 3.8 \]

  

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

در روش استراسن ماتریس‌های زیر که همه از مرتبه $\frac{n}{2}$ هستند از روی زیرماتریس‌های ماتریس‌های A و B ساخته می‌شوند:

  

\[ P=(A_{11}+A_{22})(B_{11}+B_{22}) \] \[ Q=(A_{21}+A_{22})B_{11} \] \[ R=A_{11}(B_{12}-B_{22}) \] \[ S=A_{22}(B_{21}-B_{11}) \] \[ T=(A_{11}+A_{12})B_{22} \] \[ U=(A_{21}-A_{11})(B_{11}+B_{12}) \] \[ V=(A_{12}-A_{22})(B_{21}+B_{22}) \]

  

که تنها هفت عمل ضرب برای محاسبه نیاز دارند. استراسن ثابت کرد زیرماتریس‌های متناظر ماتریس حاصلضرب از رابطه‌های زیر به دست می‌آید:

  

\[ C_{11}=P+S-T+V \] \[ C_{12}=R+T \] \[ C_{21}=Q+S \] \[ C_{22}=P-Q+R+U \]

  

تقسیم کردن ماتریس‌ها به چهار بخش - برای محاسبه به روش استراسن - تا زمانی ادامه پیدا می‌کند که مرتبه ماتریس‌ها به 2 برسند. وقتی به این مرحله رسیدیم، با تعریف اصلی ضرب ماتریس‌ها حاصلضرب را محاسبه می‌کنیم.

نکته: علت اینکه چرا تنها عمل ضرب را بررسی کردیم این بود که عمل ضرب هزینه زمانی بیشتری نسبت به عمل جمع و تفریق دارد. اگرچه می‌توان ثابت کرد که این روش به ازای مقادیر بزرگ n از نظر میزان عمل جمع و تفریق هم کاراتر است.

مسعود اقدسی فام

مسعود اقدسی فام هستم.

دانش‌آموخته علوم کامپیوتر و فعال حوزه‌های برنامه‌نویسی پایتون، علم داده و یادگیری ماشین

algs.ir/spxnc4s     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
نوشته‌های پرمخاطب
       ✦   برج هانوی
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• merinaz
۲۸ آذر ۱۳۸۶، ساعت ۰۰:۲۲

salam

email oomade bood ke codesh ham hast..pas koo codesh?

inke faghat tarife matrise!!!

merc

مسعود اقدسی فام
۲۸ آذر ۱۳۸۶، ساعت ۱۰:۲۹

مریناز خانوم

کد این کلاس به همراه معرفی کامل اون در مطلبی با عنوان "کلاس ماتریس" ارائه شده، نه اینجا.

این مظلب از ستون سمت راست در دسترس شماست.

• maryam
۱ دی ۱۳۸۶، ساعت ۱۷:۵۰

با عرض سلام وخسته نباشید خدمت شما از شما بدلیل سایت خوبتان متشکرم وخواهشمندم که نکات به روزو جدید ی را  که در مورد کامپیوتر و الگوریتم وتمام مسائل درسی وغیر درسی در مورد کامپیوتر و مطالب درسی

در مورد رشته ی کامپیوتر را یا در سایتتان بیاورید یا اگر می شود به ایمیل من بفرستید .

                                                                                                    مرسی

• مريم فيروززاده
۱۰ دی ۱۳۸۶، ساعت ۰۱:۰۷

سلامسلام                                                                                                                                                                           . با تشكر از اينكه به سوالات ما كاربران پاسخ مي گوييد بسيار متشكرم. ميخواستم بپرسم آيا به جز روشي كه براي ضرب ماتريس ها به روش استراسن گفته ايد ، روش ديگري وجود دارد يا خير.               از توجه شما بسيار سپاسگزارم .

• فریبا
۲۳ دی ۱۳۸۶، ساعت ۲۳:۴۶

سلام

میخواستم بپورسم درباره الگوریتم استراسنباهزینیهکمتر از3.8مثلا2.7مطلبیدارید؟

• arsalan
۱ بهمن ۱۳۸۶، ساعت ۰۰:۳۹

mer30

• jalil
۵ بهمن ۱۳۸۶، ساعت ۰۱:۱۱

سلام . دوست عزیر تو ضرب استراسن ماتریس رو تا دو تایی نمی شکنن بلکه تا جایی می شکنن هزینه ضرب معمولی کمتر از استراسن باشه.

مسعود اقدسی فام
۵ بهمن ۱۳۸۶، ساعت ۱۲:۳۲

جلیل جان

حق با شماست. تا جایی که من می دونم با تقسیمات متوالی این عمل انجام می شه.

• f.n
۱۳ فروردین ۱۳۸۷، ساعت ۱۷:۲۴

سلام خدمت شما

معادله بازگشتي  كه ساموئل وينوگراد در ضرب ماتريسهاي استراسن ارائه داده كه در آن 18 عمل جمع  را به 15 عمل جمع كاهش داده را مي خواستم  و حل آن معادله بازگشتي مي تونم خواهش كنم به ايميلم ارسال فرماييد ؟ متشكرم

• shima
۴ اردیبهشت ۱۳۸۷، ساعت ۲۳:۲۰

با سلام . من به برنامه ضرب استراسن احتياج دارم . اگه مي شه لطف كنيد و به من بديد. 1 دنيا ممنون . حياتيه(به زبان c)

• زهرا
۸ اردیبهشت ۱۳۸۷، ساعت ۱۱:۳۹

سلام، خسته نباشید

من به برنامه ضرب استراسن نیاز دارم

اگه امکان داره برام بفرستید

خیلی ممنون می شم

• nasrin
۱۰ اردیبهشت ۱۳۸۷، ساعت ۱۷:۳۹

ba salam va khaste nabashi

age lotf konido barname zarbe estersseno baram send konid mamnun misham.

• سمیر
۱۱ خرداد ۱۳۸۷، ساعت ۱۵:۰۲

متشکرم

مسعود اقدسی فام
۳۰ تیر ۱۳۸۷، ساعت ۱۴:۰۷

شیما خانم، زهرا خانم، نسرین خانم

کدهای کمکی اینجا قرار داده شده. اگه برنامه نویسیتون خوب باشه خیلی راحت می تونید به برنامه برسید!

سمیر جان ممنون از لطفت.

• صلاح حسین پناهی
۱ مرداد ۱۳۸۷، ساعت ۱۰:۵۰

لطفا برنامه ضرب الگوریتم استراسن را به این آدرس بفرستید ممنون می شم

• yaqoub
۷ مرداد ۱۳۸۷، ساعت ۰۸:۰۳

salam

khaste nabashin

lotf konin barname zarbe matrise strassen n*n ro baram mail konin

dastetoon dard nakone

• سارا ج
۲۴ اسفند ۱۳۸۷، ساعت ۱۸:۱۵

سلام .من اگه بخوام ضرب استراس رو پیاده سازی کنم چه جوری باید شروع کنم .

مسعود اقدسی فام
۲۵ اسفند ۱۳۸۷، ساعت ۰۰:۱۴

سلام سارا خانم

با چه زبانی و چه نسخه ای و چه روشی؟

• Fatemeh
۱ فروردین ۱۳۸۸، ساعت ۰۶:۳۷

salam

sale no mobarak

mer30 az site khoobetoon

mishe lotf konin va barname nevisie "zarb estrasen" ro baram befresin

merc

• ستاره
۴ فروردین ۱۳۸۸، ساعت ۱۶:۵۷

لام خسته نباشيد

ميشه لطف كنيد كد برنامه ضرب استراسن رو بفرستيد برامون

مرسي

خيلي

• shokoofeh
۸ فروردین ۱۳۸۸، ساعت ۱۷:۵۷

سلام .الگوريتم وينوگراد كه روش اصلاح شده استراسن هست رو دارين؟خواهش ميكنم انجا بذارين.من فردا هم يه سر ميزنم.فوريه.........................

• مصطفي
۲۰ فروردین ۱۳۸۸، ساعت ۱۱:۲۴

سلام،خواهش مي كنم برنامه ضرب ماتريسها را نيز به روش تقسيم وحل (ازروش استراسن) براي من بفرستين ؟فوريه؟باتشكر

• یاسی
۲۶ فروردین ۱۳۸۸، ساعت ۲۱:۴۳

salam.lotfan algoritm esterasen ro be eimailam ersal konid mamnon misham

• متوسل
۳۰ فروردین ۱۳۸۸، ساعت ۱۹:۳۳

سلام.توضیحی در مورد برنامه skyline می خواستم.ممنون از لطفتون.

• مقداد
۱۵ اردیبهشت ۱۳۸۸، ساعت ۱۵:۰۵

سلام  اگه میشه برام توضیح بدین آیا نسخه ی موازی (برای کامپیوتر های موازی ) طراحی شده است ؟Mer 30

• ؟
۲۴ اردیبهشت ۱۳۸۸، ساعت ۱۰:۱۸

بر و  بابا !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

• acm
۱۹ شهریور ۱۳۸۸، ساعت ۱۰:۵۵

سلام رفیق برا چی وقتی باهنر قبول شدی نرفتی

۲۱ شهریور ۱۳۸۸، ساعت ۱۸:۲۶
• مسعود اقدسی فام

سلام رفيق

خدمت سربازي اجازه ادامه تحصيل بهم نداد. تا تموم شدن اين دوره حق ادامه تحصيل ندارم.

ممنون كه به يادم بودي. 06

• پرستو
۲۱ مهر ۱۳۸۸، ساعت ۱۳:۵۰

به که با این کارت لطفی بزرگ به من و بشریت می کنی . خیلی بخشنده ای که علمتو در اختیار دیگران بدون هیچ چشم داشتی میگذاری واقعا خسته نباشید . یه روز جواب این همه مهربونی هاتو از خدا می گیری. چون مشکل منو حل کردی .

• راضیه
۵ آبان ۱۳۸۸، ساعت ۱۹:۱۸

سلام ببخشید من برنامه ضرب اعداد بزرگ را به روش تقسیم وحل میخوام اگه دارین ممنون میشیم تا 5 شنبه برام بزارین10

۱۱ آبان ۱۳۸۸، ساعت ۱۹:۱۲
• مسعود اقدسی فام

سلام

اگر قوانین ارسال پیام رو مطالعه کرده بودید متوجه می شدید که به درخواست برنامه آماده پاسخی داده نمی شه.

ممنون از حضورتون.

• zebel
۱۶ بهمن ۱۳۸۸، ساعت ۲۱:۴۷

سلام

میشه الگوریتم ضرب دو ماتریس به روش استراسن رو پیاده سازی کنید؟

یا الگوریتم ضرب اعداد صحیح بسیار بزرگ را (به روش تقسیم و غلبه) پیاده سازی کنید.

اینا پروژه دانشگاهمه

متشکرم

• goli
۱۷ اسفند ۱۳۸۸، ساعت ۱۱:۰۰

04خیلی چرت بود

• همتا
۱۷ فروردین ۱۳۸۹، ساعت ۱۵:۱۶

سلام دوست عزیز

راه حلی به نظرتون میرسه که طول آرایه رو بشه تو پشته نگهداری کرد؟

• رضا
۶ مهر ۱۳۸۹، ساعت ۱۳:۲۵

احسن   جالب بود

• سحر
۸ اسفند ۱۳۹۰، ساعت ۰۱:۰۳

salam, merc az matalebe por mohtavatoon, mikhastam khahesh konam algoritme zarbe matris ro ham be zabane ++c benevisin, man kheyli gashtam vali peyda nakardam , mamnoon

• lili
۱۴ آبان ۱۳۹۱، ساعت ۱۰:۵۴

سلام.

ممنون میشم اگه سوالما تا 3شنبه جواب بدین اخرین وقتشه.

ضرب دو ماتریس 3*3 به روش استراسنوساده وتعداد جمع ها وضربهادر هر یک کدام روش بهتر است؟؟؟؟06

• 1
۱۸ آبان ۱۳۹۲، ساعت ۱۷:۴۲

0505050505050505

• سعید
۵ خرداد ۱۳۹۴، ساعت ۱۶:۴۸

خیلی بد بود چی بود این؟ضرب اترایست فقط همینه داداشه من؟ 10 10 11 11

• فاطمه
۱۱ آبان ۱۳۹۴، ساعت ۲۱:۳۰

خیلی عالی توضیح دادین. مختصر و مفید. خیلی ممنون 12

• جابر
۲۲ آذر ۱۳۹۵، ساعت ۱۳:۲۳

به نظرم زیاد جال نبود

• ترنم باران
۱۵ اردیبهشت ۱۳۹۷، ساعت ۲۲:۴۸

سلام خیلی ممنونم عالی بوود و کاملا متوجه شدم

• طیبه
۵ خرداد ۱۳۹۷، ساعت ۱۳:۴۳

نمیدونین این الگوریتم چجوری بهینه میشه؟