آنچه میخوانید ویراست جدید نوشتهای است که اولین بار با عنوان «ضرب استراسن»
آبان ماه ۱۳۸۶
از طریق وبگاه برنامهنویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان)
منتشر شده بود.
همهی ما با تعریف ضرب ماتریسهای مربعی آشنایی داریم. حاصلضرب ماتریسهای مربعی 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 از نظر میزان عمل جمع و تفریق هم کاراتر است
.