ضرب ماتریس‌ها یک عمل ریاضی است برای ترکیب دو ماتریس است که در مباحث مختلفی مانند گرافیک کامپیوتری، فیزیک و یادگیری ماشین کاربرد دارد. در این عملیات، برای هر عنصر از ماتریس حاصل، عناصر سطرهای ماتریس اول با عناصر ستون‌های ماتریس دوم ضرب می‌شوند و مجموع این ضرب‌ها به‌عنوان عنصر متناظر در ماتریس جدید قرار می‌گیرد. برای اینکه ضرب ماتریس‌ها امکان‌پذیر باشد، تعداد ستون‌های ماتریس اول باید برابر با تعداد سطرهای ماتریس دوم باشد. نتیجه این عمل، یک ماتریس با تعداد سطرهای ماتریس اول و تعداد ستون‌های ماتریس دوم خواهد بود.
\[ 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 از نظر میزان عمل جمع و تفریق هم کاراتر است.