بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
ضرب استراسن - الگوریتمستان
الگوریتمستان
4314.075.00
  »  

       

آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «ضرب استراسن» آبان ماه 1386 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


همه‌ی ما با تعریف ضرب ماتریس‌های مربعی آشنایی داریم. حاصلضرب ماتریس‌های مربعی 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 از نظر میزان عمل جمع و تفریق هم کاراتر است.


این نوشته آخرین بار در تاریخ مورد بازنویسی علمی قرار گرفته است.
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» فاطمه

دوشنبه، ۱۱ آبان ماه ۱۳۹۴، ساعت ۲۱:۳۰
خیلی عالی توضیح دادین. مختصر و مفید. خیلی ممنون 12

» سعید

سه‌شنبه، ۵ خرداد ماه ۱۳۹۴، ساعت ۱۶:۴۸
خیلی بد بود چی بود این؟ضرب اترایست فقط همینه داداشه من؟ 10 10 11 11

» 1

شنبه، ۱۸ آبان ماه ۱۳۹۲، ساعت ۱۷:۴۲
0505050505050505

» lili

یکشنبه، ۱۴ آبان ماه ۱۳۹۱، ساعت ۱۰:۵۴
سلام.
ممنون میشم اگه سوالما تا 3شنبه جواب بدین اخرین وقتشه.
ضرب دو ماتریس 3*3 به روش استراسنوساده وتعداد جمع ها وضربهادر هر یک کدام روش بهتر است؟؟؟؟06

» سحر

دوشنبه، ۸ اسفند ماه ۱۳۹۰، ساعت ۰۱:۰۳
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

» رضا

سه‌شنبه، ۶ مهر ماه ۱۳۸۹، ساعت ۱۳:۲۵
احسن   جالب بود

» همتا

سه‌شنبه، ۱۷ فروردین ماه ۱۳۸۹، ساعت ۱۵:۱۶
سلام دوست عزیز
راه حلی به نظرتون میرسه که طول آرایه رو بشه تو پشته نگهداری کرد؟

» goli

دوشنبه، ۱۷ اسفند ماه ۱۳۸۸، ساعت ۱۱:۰۰
04خیلی چرت بود

» zebel

جمعه، ۱۶ بهمن ماه ۱۳۸۸، ساعت ۲۱:۴۷
سلام
میشه الگوریتم ضرب دو ماتریس به روش استراسن رو پیاده سازی کنید؟
یا الگوریتم ضرب اعداد صحیح بسیار بزرگ را (به روش تقسیم و غلبه) پیاده سازی کنید.
اینا پروژه دانشگاهمه
متشکرم

» راضیه

سه‌شنبه، ۵ آبان ماه ۱۳۸۸، ساعت ۱۹:۱۸
سلام ببخشید من برنامه ضرب اعداد بزرگ را به روش تقسیم وحل میخوام اگه دارین ممنون میشیم تا 5 شنبه برام بزارین10


دوشنبه، ۱۱ آبان ماه ۱۳۸۸، ساعت ۱۹:۱۲
مسعود:
سلام
اگر قوانین ارسال پیام رو مطالعه کرده بودید متوجه می شدید که به درخواست برنامه آماده پاسخی داده نمی شه.
ممنون از حضورتون.

» پرستو

سه‌شنبه، ۲۱ مهر ماه ۱۳۸۸، ساعت ۱۳:۵۰
به که با این کارت لطفی بزرگ به من و بشریت می کنی . خیلی بخشنده ای که علمتو در اختیار دیگران بدون هیچ چشم داشتی میگذاری واقعا خسته نباشید . یه روز جواب این همه مهربونی هاتو از خدا می گیری. چون مشکل منو حل کردی .

» acm

پنجشنبه، ۱۹ شهریور ماه ۱۳۸۸، ساعت ۱۰:۵۵
سلام رفیق برا چی وقتی باهنر قبول شدی نرفتی


شنبه، ۲۱ شهریور ماه ۱۳۸۸، ساعت ۱۸:۲۶
مسعود:
سلام رفيق
خدمت سربازي اجازه ادامه تحصيل بهم نداد. تا تموم شدن اين دوره حق ادامه تحصيل ندارم.
ممنون كه به يادم بودي. 01