ضرب استراسن

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