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

در جبر خطی الگوریتم استراسن الگوریتمی برای ضرب ماتریس است که برای ماتریس‌های بزرگ سریع‌تر از الگوریتم ضرب ماتریس استاندارد است و پیچیدگی مجانبی بهتری دارد (O(n^{\log_2 7}) در برابر O(n^3))، البته الگوریتم ساده همچنان برای ماتریس‌های کوچک‌تر بهتر است. الگوریتم استراسن از سریع‌ترین الگوریتم شناخته‌شده برای ماتریس‌های بسیار بزرگ کندتر است، اما آن الگوریتم‌های کهکشانی در عمل مفید نیستند، زیرا برای ماتریس‌های در اندازه‌های رایج بسیار کندترند. برای ماتریس‌های کوچک، الگوریتم‌های سریع‌تری نیز هست.

الگوریتم استراسن برای هر حلقه‌ای، مانند جمع/ضرب، جواب می‌دهد، ولی برای همه‌ی نیم‌حلقه‌ها، مانند جبر کمینه جمع یا جبر بولی، که در آن‌ها الگوریتم ساده جواب می‌دهد، جواب نمی‌دهد.
## تاریخ
ولکر استراسن الگوریتم استراسن را در سال ۱۹۶۹ منتشر کرد. او نخستین کسی بود که نشان داد الگوریتم رایج مرتبه   n^3  بهینه نیست. 

## الگوریتم

فرض کنید A, B دو ماتریس مربعی روی یک حلقه \mathcal{R}،برای نمونه ماتریس‌هایی که عنصرهایشان عدد صحیح یا حقیقی است، باشند. هدف ضرب ماتریس محاسبه ماتریس  C = AB است. این توضیح الگوریتم فرض می‌کند که اندازه‌ی ماتریس‌ها توان‌های ۲ است (یعنی A, \, B, \, C \in \operatorname{Matr}_{2^n \times 2^n} (\mathcal{R})). اگر ماتریس‌های A, B با اندازه‌‌های 2^n \times 2^n نباشند، ردیف‌ها و ستون‌های خالی را می‌توان با صفر پر کرد تا به این اندازه برسند - گرچه پیاده‌سازی‌های واقعی این الگوریتم در عمل این کار را نمی‌کنند.

الگوریتم A, B و C را به ماتریس‌های بلوکی هم اندازه افراز می‌کند: 
A =
\begin{bmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{bmatrix}, \quad
B =
\begin{bmatrix}
B_{11} & B_{12} \\
B_{21} & B_{22}
\end{bmatrix}, \quad
C =
\begin{bmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22}
\end{bmatrix}, \quad


الگوریتم ضرب ماتریس استاندارد اینگونه می‌بود:
: 
\begin{bmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22}
\end{bmatrix}
=
\begin{bmatrix}
A_{11} {\color{red}\times} B_{11} + A_{12} {\color{red}\times} B_{21} \quad &
A_{11} {\color{red}\times} B_{12} + A_{12} {\color{red}\times} B_{22} \\
A_{21} {\color{red}\times} B_{11} + A_{22} {\color{red}\times} B_{21} \quad &
A_{21} {\color{red}\times} B_{12} + A_{22} {\color{red}\times} B_{22}
\end{bmatrix}.

با این ساختار، تعداد ضرب‌ها کاهش نیافته است. هنوز هم به ۸ ضرب نیاز است تا ماتریس‌های C_{ij} محاسبه شود.

استراسن این ماتریس‌های جدید را تعریف می‌کند:

: \begin{align}
M_1 &= (A_{11} + A_{22}) {\color{red}\times} (B_{11} + B_{22}); \\
M_2 &= (A_{21} + A_{22}) {\color{red}\times} B_{11}; \\
M_3 &= A_{11} {\color{red}\times} (B_{12} - B_{22}); \\
M_4 &= A_{22} {\color{red}\times} (B_{21} - B_{11}); \\
M_5 &= (A_{11} + A_{12}) {\color{red}\times} B_{22}; \\
M_6 &= (A_{21} - A_{11}) {\color{red}\times} (B_{11} + B_{12}); \\
M_7 &= (A_{12} - A_{22}) {\color{red}\times} (B_{21} + B_{22}), \\
\end{align}

با بیان C_{ij} به کمک M_k می‌توان یک ضرب ماتریس را حذف کرد و تعداد ضرب‌ها را به ۷ کاهش داد (یک ضرب برای هر M_k):
: 
\begin{bmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22}
\end{bmatrix}
=
\begin{bmatrix}
M_1 + M_4 - M_5 + M_7 \quad &
M_3 + M_5 \\
M_2 + M_4 \quad &
M_1 - M_2 + M_3 + M_6
\end{bmatrix}.

این فرآیند تقسیم به صورت بازگشتی تکرار شده تا زیرماتریس‌ها به عدد (عنصر‌های حلقه \mathcal{R}) تبدیل شوند. اگر ماتریس اصلی اندازه‌ای جز توان‌های ۲ داشته باشد، آنگاه نتیجه مانند خود A و B سطر و ستون صفر خواهد داشت. این سطرها و ستون‌ها زدوده می‌شوند تا ماتریس (کوچکتر) C که نتیجه اصلی ضرب است به دست آید.

در پیاده‌سازی‌های عملی الگوریتم استراسن برای زیرماتریس‌های به اندازه کافی کوچک از روش‌های استاندارد ضرب ماتریس استفاده می‌شود. نقطه‌ای که الگوریتم استراسن برای آن اندازه به بعد کارآمدتر است، به پیاده‌سازی و سخت‌افزار بستگی دارد. نویسندگان پیش‌تر تخمین زده بودند که الگوریتم استراسن برای ماتریس‌های با اندازه‌ی ۳۲ تا ۱۲۸ برای پیاده‌سازی‌های بهینه‌شده از روش استاندارد سریع‌تر است ولی مشاهده شده است که این نقطه  در سال‌های گذشته رو به افزایش بوده است. پژوهشی در سال ۲۰۱۰ نشان داد که حتی یک گام از الگوریتم استراسن در معماری‌های فعلی، در مقایسه با یک ضرب ساده‌ی بسیار بهینه‌شده، تا زمانی که اندازه‌ی ماتریس‌ها از ۱۰۰۰ بیشتر نشود، سودمند نیست و حتی برای ماتریس با اندازه‌ی چند هزار، این سودمندی در بهترین حالت حاشیه‌ای است (حدود ۱۰ درسد یا کمتر). پژوهشی جدیدتر (۲۰۱۶) سودمندی را برای ماتریس‌هایی به کوچکی 512 و به میزان حدود ۲۰ درسد مشاهده کرد.

## پیچیدگی مجانبی
ضرب ماتریسی استاندارد تقریباً عملیات محاسباتی ۲n^۳ (که n=۲^n) (جمعها و ضرب‌ها) را می‌پذیرد؛ پیچیدگی مجانبی (O(N۳می‌باشد.
تعداد جمع‌ها و ضرب‌های مورد نیاز در الگوریتم استراسن را می‌توان به صورت زیر محاسبه کرد:

فرض کنید (f(n تعداد عملیات برای یک ماتریس ۲n * ۲n باشد. آنگاه با عملیات بازگشتی الگوریتم استراسن می‌بینیم که برای برخی l ثابت که به تعداد جمع‌های انجام شده در هر عملیات الگوریتم وابسته‌است.
یعنی پیچیدگی مجانبی برای ضرب ماتریسها با استفاده از الگوریتم استراسن O([7+o(1)]^n) = O(N^{\log_{2}7+o(1)}) \approx O(N^{2.8074}) است.
هرچند کاهش در تعداد عملیات محاسباتی تا حدودی به بهای کاهش ثبات عددی می‌باشد.

## همچنین مشاهده کنید
* نمایش ماتریس Z-order

## منابع

* استراسن، ولکر، *حذف گاوسی بهینه نیست*، ص ۳۵۴-۳۵۶، ۱۹۶۹
* تامس اچ. کردمن، چارلز ای. لایسرسون، رانلد ال. روست، کلیفورد استاین، *آشنایی با الگوریتم*، ویرایش دوم، انتشارات موسسه فناوری ماساچوست، فصل ۲۸، الگوریتم استراسن برای ضرب ماتریس، ص ۷۳۴-۷۴۱، ۲۰۰۱

## پیوند به بیرون
* ویستین اچ. اریک، *فرمول‌های استراسن* ، (همچنین شامل فرمول برای وارونگی ماتریس سریع)
* تیلر جی. ارنست،*[https://web.archive.org/web/20110720085819/http://www.mc2.umbc.edu/docs/earnest.pdf الگوریتم استراسن در موتور پهنای باند همراه]*
* *[https://web.archive.org/web/20100301194110/http://gitorious.org/intelws2010/matrix-multiplication/blobs/master/src/matmul.c پیاده‌سازی ساده الگوریتم استراسن درC]*، (آسان برای اهداف آموزش و پرورش)

رده:الگوریتم‌های ضرب ماتریس
رده:جبر خطی عددی