خوارزمية ستراسن

في الجبر الخطي ، تُعد خوارزمية ستراسن ، التي سُميت نسبةً إلى فولكر ستراسن ، خوارزمية لضرب المصفوفات . وهي أسرع من خوارزمية ضرب المصفوفات القياسية للمصفوفات الكبيرة، مع تعقيد تقاربي أفضل .${\displaystyle O(n^{\log _{2}7})}$عكس${\displaystyle O(n^{3})}$على الرغم من أن الخوارزمية البسيطة غالبًا ما تكون أفضل للمصفوفات الصغيرة، إلا أن خوارزمية ستراسن أبطأ من أسرع الخوارزميات المعروفة للمصفوفات الكبيرة جدًا، ولكن هذه الخوارزميات الضخمة غير مجدية عمليًا، لأنها أبطأ بكثير للمصفوفات ذات الحجم العملي. أما بالنسبة للمصفوفات الصغيرة، فتوجد خوارزميات أسرع.

تعمل خوارزمية ستراسن مع أي حلقة ، مثل الجمع/الضرب، ولكن ليس مع جميع الحلقات شبه الحلقية ، مثل الجمع الأدنى أو الجبر البولياني ، حيث لا تزال الخوارزمية البسيطة تعمل، وما يسمى بضرب المصفوفات التوافقي .

نشر فولكر ستراسن هذه الخوارزمية لأول مرة عام 1969، وبذلك أثبت أن${\displaystyle n^{3}}$لم تكن خوارزمية ضرب المصفوفات العامة مثالية. ^{[ 1 ]} أدى نشر خوارزمية ستراسن إلى مزيد من الأبحاث حول ضرب المصفوفات، مما أدى إلى تحديد حدود دنيا تقاربية وتحسين الحدود العليا الحسابية.

يترك${\displaystyle A}$،${\displaystyle B}$ليكن مصفوفتين مربعتين فوق حلقة${\displaystyle {\mathcal {R}}}$على سبيل المثال، المصفوفات التي تكون عناصرها أعدادًا صحيحة أو أعدادًا حقيقية. الهدف من ضرب المصفوفات هو حساب حاصل ضرب المصفوفات.${\displaystyle C=AB}$يفترض الشرح التالي للخوارزمية أن جميع هذه المصفوفات لها أحجام من قوى العدد اثنين (أي،${\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})}$)، لكن هذا ضروري من الناحية النظرية فقط - إذا كانت المصفوفات${\displaystyle A}$،${\displaystyle B}$ليست من النوع${\displaystyle 2^{n}\times 2^{n}}$، ويمكن ملء الصفوف والأعمدة "المفقودة" بالأصفار للحصول على مصفوفات بأحجام قوى العدد اثنين - على الرغم من أن التطبيقات الحقيقية للخوارزمية لا تفعل ذلك عمليًا.

أقسام خوارزمية Strassen${\displaystyle A}$،${\displaystyle B}$و${\displaystyle C}$إلى مصفوفات كتل متساوية الحجم

${\displaystyle 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 }$

مع${\displaystyle A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})}$ستكون الخوارزمية البسيطة كالتالي:

${\displaystyle {\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}}.}$

لا يقلل هذا التركيب من عدد عمليات الضرب: لا تزال هناك حاجة إلى 8 عمليات ضرب لكتل ​​المصفوفة لحساب${\displaystyle C_{ij}}$المصفوفات، نفس عدد عمليات الضرب المطلوبة عند استخدام ضرب المصفوفات القياسي.

تحدد خوارزمية ستراسن قيمًا جديدة بدلاً من ذلك:

${\displaystyle {\begin{aligned}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{aligned}}}$

باستخدام 7 عمليات ضرب فقط (واحدة لكل${\displaystyle M_{k}}$) بدلاً من 8. يمكننا الآن التعبير عن${\displaystyle C_{ij}}$من ناحية${\displaystyle M_{k}}$:

${\displaystyle {\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}}.}$

نكرر عملية القسمة هذه بشكل متكرر حتى تتحول المصفوفات الفرعية إلى أعداد (عناصر الحلقة).${\displaystyle {\mathcal {R}}}$إذا كان حجم المصفوفة الأصلية، كما ذُكر أعلاه، ليس قوةً للعدد 2، فإن الناتج سيكون له صفوف وأعمدة صفرية تمامًا مثل${\displaystyle A}$و${\displaystyle B}$ثم يتم تجريد هذه العناصر عند هذه النقطة للحصول على المصفوفة (الأصغر).${\displaystyle C}$كنا نرغب بذلك حقاً.

تتحول التطبيقات العملية لخوارزمية ستراسن إلى طرق ضرب المصفوفات القياسية للمصفوفات الفرعية الصغيرة بما يكفي، حيث تكون هذه الخوارزميات أكثر كفاءة. وتعتمد نقطة التحول التي تكون عندها خوارزمية ستراسن أكثر كفاءة على التطبيق المحدد والأجهزة. وقد قدّر باحثون سابقون أن خوارزمية ستراسن أسرع للمصفوفات التي يتراوح عرضها بين 32 و128 في التطبيقات المُحسّنة. ^{[ 2 ]} ومع ذلك، لوحظ أن نقطة التحول هذه تتزايد في السنوات الأخيرة، ووجدت دراسة أجريت عام 2010 أن خطوة واحدة من خوارزمية ستراسن غالبًا ما تكون غير مفيدة على البنى الحالية، مقارنةً بالضرب التقليدي المُحسّن للغاية، إلى أن يتجاوز حجم المصفوفة 1000 أو أكثر، وحتى بالنسبة لأحجام المصفوفات التي تبلغ عدة آلاف، تكون الفائدة هامشية في أحسن الأحوال (حوالي 10% أو أقل). ^{[ 3 ]} ولاحظت دراسة أحدث (2016) فوائد للمصفوفات الصغيرة التي يصل حجمها إلى 512، وفائدة تقارب 20%. ^{[ 4 ]}

من الممكن تقليل عدد عمليات جمع المصفوفات باستخدام الشكل التالي الذي اكتشفه وينوغراد في عام 1971: ^{[ 5 ]}

${\displaystyle {\begin{bmatrix}a&b\\c&d\end{bmatrix}}{\begin{bmatrix}A&C\\B&D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&w+v+(a+bcd){\color {red}\times }D\\w+u+d{\color {red}\times }(B+CAD)&w+u+v\end{bmatrix}}}$

أين${\displaystyle t=a{\color {red}\times }A,\;u=(ca){\color {red}\times }(CD),\;v=(c+d){\color {red}\times }(CA),\;w=t+(c+da){\color {red}\times }(A+DC)}$.

يؤدي هذا إلى تقليل عدد عمليات جمع وطرح المصفوفات من 18 إلى 15. ويبقى عدد عمليات ضرب المصفوفات 7، ويبقى التعقيد التقاربي كما هو. ^{[ 6 ]}

تم تحسين الخوارزمية بشكل أكبر في عام 2017 باستخدام أساس بديل، ^{[ 7 ]} مما أدى إلى تقليل عدد عمليات جمع المصفوفات لكل خطوة ثنائية الخطية إلى 12 مع الحفاظ على عدد عمليات ضرب المصفوفات، ومرة ​​أخرى في عام 2023: ^{[ 8 ]}

${\displaystyle {\begin{aligned}A_{22}&=A_{12}-A_{21}+A_{22};\\B_{22}&=B_{12}-B_{21}+B_{22},\end{aligned}}}$

${\displaystyle {\begin{aligned}C_{12}&=C_{12}-C_{22};\\C_{21}&=C_{22}-C_{21},\end{aligned}}}$

أظهرت الخطوط العريضة للخوارزمية أعلاه أنه يمكن الاكتفاء بسبع عمليات ضرب مصفوفات فقط، بدلاً من ثماني عمليات كما هو معتاد، للكتل الفرعية للمصفوفة. من ناحية أخرى، يجب إجراء عمليات جمع وطرح للكتل، مع أن هذا لا يؤثر على التعقيد الكلي: جمع مصفوفات بحجم${\displaystyle N/2}$لا يتطلب الأمر سوى${\displaystyle (N/2)^{2}}$العمليات الحسابية، بينما عملية الضرب أكثر تكلفة بكثير (تقليديًا)${\displaystyle 2(N/2)^{3}}$عمليات الجمع أو الضرب).

السؤال إذن هو: ما عدد العمليات التي يحتاجها المرء بالضبط لخوارزميات ستراسن، وكيف يقارن ذلك بضرب المصفوفات القياسي الذي يستغرق تقريبًا${\displaystyle 2N^{3}}$(أين${\displaystyle N=2^{n}}$) العمليات الحسابية، أي التعقيد التقاربي${\displaystyle \Theta (N^{3})}$.

يمكن حساب عدد عمليات الجمع والضرب المطلوبة في خوارزمية ستراسن على النحو التالي: ليكن${\displaystyle f(n)}$ليكن عدد العمليات لـ${\displaystyle 2^{n}\times 2^{n}}$المصفوفة. ثم بتطبيق خوارزمية ستراسن بشكل متكرر، نرى أن${\displaystyle f(n)=7f(n-1)+l4^{n}}$، لبعض الثوابت${\displaystyle l}$يعتمد ذلك على عدد عمليات الجمع التي تُجرى في كل تطبيق للخوارزمية.${\displaystyle f(n)=(7+o(1))^{n}}$أي، التعقيد التقاربي لضرب المصفوفات ذات الحجم${\displaystyle N=2^{n}}$استخدام خوارزمية ستراسن هو ${\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})}$مع ذلك، يأتي انخفاض عدد العمليات الحسابية على حساب انخفاض طفيف في الاستقرار العددي ^{[ 9 ]} ، كما تتطلب الخوارزمية ذاكرة أكبر بكثير مقارنةً بالخوارزمية البسيطة. يجب توسيع أبعاد المصفوفتين الأوليتين إلى أقرب قوة للعدد 2، مما يؤدي إلى تخزين ما يصل إلى أربعة أضعاف عدد العناصر، وتحتوي كل مصفوفة من المصفوفات المساعدة السبع على ربع عدد العناصر في المصفوفات الموسعة.

يجب مقارنة خوارزمية ستراسن بالطريقة "البسيطة" لضرب المصفوفات، والتي تتطلب 8 عمليات ضرب للكتل الفرعية بدلاً من 7. وهذا من شأنه أن يُنتج التعقيد المتوقع من الطريقة القياسية.${\displaystyle O(8^{n})=O(N^{\log _{2}8})=O(N^{3})}$تُظهر مقارنة هاتين الخوارزميتين أن خوارزمية ستراسن أسرع تقاربياً : يوجد حجم${\displaystyle N_{\text{threshold}}}$لذا، فإن ضرب المصفوفات الأكبر حجمًا باستخدام خوارزمية ستراسن يكون أكثر كفاءة من الطريقة "التقليدية". مع ذلك، لا يعني هذا بالضرورة أن خوارزمية ستراسن أسرع دائمًا حتى مع المصفوفات الصغيرة، وفي الواقع العملي، هذا ليس هو الحال: فبالنسبة للمصفوفات الصغيرة، تفوق تكلفة عمليات الجمع الإضافية لكتل ​​المصفوفة التوفير في عدد عمليات الضرب. هناك أيضًا عوامل أخرى لم يشملها التحليل أعلاه، مثل الفرق في التكلفة على الأجهزة الحالية بين تحميل البيانات من الذاكرة إلى المعالجات مقابل تكلفة إجراء العمليات الفعلية على هذه البيانات. نتيجةً لهذه الاعتبارات، تُستخدم خوارزمية ستراسن عادةً مع المصفوفات "الكبيرة" فقط. هذا التأثير أكثر وضوحًا مع الخوارزميات البديلة مثل خوارزمية كوبرسميث ووينوغراد : فبينما تكون أسرع تقاربًا ، إلا أن نقطة التحول${\displaystyle N_{\text{threshold}}}$إنها كبيرة جدًا لدرجة أن الخوارزمية لا تُستخدم بشكل عام على المصفوفات التي يصادفها المرء في الممارسة العملية.

الرتبة أو التعقيد الثنائي الخطي

يُعدّ التعقيد الثنائي الخطي أو رتبة التحويل الثنائي الخطي مفهومًا مهمًا في التعقيد التقاربي لضرب المصفوفات. رتبة التحويل الثنائي الخطي${\displaystyle \phi$ :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C} } فوق الحقل F يتم تعريفه على أنه (إلى حد ما إساءة استخدام التدوين )

${\displaystyle R(\phi /\mathbf {F} )=\min \left\{r\left|\exists f_{i}\in \mathbf {A} ^{*},g_{i}\in \mathbf {B} ^{*},w_{i}\in \mathbf {C} ,\forall \mathbf {a} \in \mathbf {A} ,\mathbf {b} \in \mathbf {B} ,\phi (\mathbf {a} ,\mathbf {b} )=\sum _{i=1}^{r}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}\right.\right\}}$

بمعنى آخر، رتبة الخريطة الثنائية الخطية هي طول أقصر عملية حسابية ثنائية خطية لها. ^{[ 10 ]} يُظهر وجود خوارزمية ستراسن أن رتبة${\displaystyle 2\times 2}$لا تتجاوز عملية ضرب المصفوفات سبعة. ولتوضيح ذلك، دعونا نعبر عن هذه الخوارزمية (إلى جانب الخوارزمية القياسية) كعملية حسابية ثنائية الخطية. في حالة المصفوفات، تتكون الفضاءات الثنائية A * و B * من دوال في الحقل F ناتجة عن ضرب نقطي مزدوج قياسي (أي في هذه الحالة مجموع جميع عناصر ضرب هادامارد ).

	الخوارزمية القياسية				خوارزمية ستراسن
${\displaystyle i}$	${\displaystyle f_{i}(\mathbf {a} )}$	${\displaystyle g_{i}(\mathbf {b} )}$	${\displaystyle w_{i}}$		${\displaystyle f_{i}(\mathbf {a} )}$	${\displaystyle g_{i}(\mathbf {b} )}$	${\displaystyle w_{i}}$
1	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}}$
2	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&-1\end{bmatrix}}}$
3	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&1\end{bmatrix}}}$
4	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\1&0\end{bmatrix}}}$
5	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}-1&1\\0&0\end{bmatrix}}}$
6	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$
7	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$
8	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$
	${\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}$				${\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}$

يمكن إثبات أن العدد الإجمالي لعمليات الضرب الأولية${\displaystyle L}$إن المطلوب لضرب المصفوفات مرتبط ارتباطًا وثيقًا بالرتبة تقاربًا${\displaystyle R}$، أي${\displaystyle L=\Theta (R)}$أو بتعبير أدق، بما أن الثوابت معروفة،${\displaystyle R/2\leq L\leq R}$إحدى الخصائص المفيدة للرتبة هي أنها شبه ضربية بالنسبة لحاصل ضرب الموترات ، وهذا يمكّن المرء من إثبات أن${\displaystyle 2^{n}\times 2^{n}\times 2^{n}}$يمكن إنجاز عملية ضرب المصفوفات بما لا يزيد عن${\displaystyle 7^{n}}$عمليات الضرب الأساسية لأي${\displaystyle n}$. (هذا${\displaystyle n}$حاصل ضرب الموتر ذي الرتبة n${\displaystyle 2\times 2\times 2}$عملية ضرب المصفوفات مع نفسها —${\displaystyle n}$يتم تحقيق قوة الموتر رقم -th من خلال الخطوة التكرارية في الخوارزمية الموضحة.)

يذكر الوصف أعلاه أن المصفوفات مربعة، وأن حجمها قوة من قوى العدد اثنين ، وأنه ينبغي استخدام الحشو عند الحاجة. يسمح هذا القيد بتقسيم المصفوفات إلى نصفين، بشكل متكرر، حتى الوصول إلى حد الضرب القياسي . يُبسط هذا القيد الشرح وتحليل التعقيد، ولكنه ليس ضروريًا في الواقع؛ ^{[ 12 ]} وفي الحقيقة، سيؤدي حشو المصفوفة كما هو موضح إلى زيادة وقت الحساب، وقد يُلغي بسهولة التوفير الطفيف في الوقت الذي تم الحصول عليه باستخدام الطريقة في المقام الأول.

سيراعي التنفيذ الجيد ما يلي:

• ليس من الضروري ولا من المستحسن استخدام خوارزمية ستراسن حتى في حالة الأعداد القياسية. بالمقارنة مع ضرب المصفوفات التقليدي، تضيف الخوارزمية قيمة كبيرة${\displaystyle O(n^{2})}$عبء العمل في عمليات الجمع والطرح؛ لذا، عند التعامل مع أعداد أقل من حجم معين، يُفضّل استخدام الضرب التقليدي. على سبيل المثال،${\displaystyle 1600\times 1600}$لا حاجة إلى إضافة حشو إلى${\displaystyle 2048\times 2048}$لأنه يمكن تقسيمه إلى${\displaystyle 25\times 25}$يمكن بعد ذلك استخدام المصفوفات والضرب التقليدي على هذا المستوى.
• يمكن تطبيق هذه الطريقة على المصفوفات المربعة ذات أي بُعد. ^{[ 3 ]} إذا كان البُعد زوجيًا، تُقسّم المصفوفة إلى نصفين كما هو موضح. أما إذا كان البُعد فرديًا، فيُضاف صف وعمود واحد من الأصفار أولًا. يمكن تطبيق هذه الأصفار أثناء المعالجة أو عند الحاجة، ثم تُحذف الصفوف والأعمدة الزائدة عند تكوين النتيجة. على سبيل المثال، لنفترض أن المصفوفات هي${\displaystyle 199\times 199}$يمكن تقسيمها بحيث يكون الجزء العلوي الأيسر${\displaystyle 100\times 100}$والجزء السفلي الأيمن هو${\displaystyle 99\times 99}$أينما تتطلب العمليات ذلك، أبعاد${\displaystyle 99}$يتم إضافة أصفار إلى${\displaystyle 100}$أولاً. لاحظ، على سبيل المثال، أن المنتج${\displaystyle M_{2}}$يُستخدم فقط في الصف السفلي من المخرجات، لذا فهو مطلوب فقط أن يكون${\displaystyle 99}$صفوف عالية؛ وبالتالي العامل الأيسر${\displaystyle A_{21}+A_{22}}$لا يلزم استخدام ما يلي لتوليده${\displaystyle 99}$صفوف عالية؛ وبالتالي، لا حاجة لزيادة هذا المجموع إلى${\displaystyle 100}$صفوف؛ من الضروري فقط إضافة حشو.${\displaystyle A_{22}}$ل${\displaystyle 100}$أعمدة للمطابقة${\displaystyle A_{21}}$.

علاوة على ذلك، ليس من الضروري أن تكون المصفوفات مربعة. يمكن تقسيم المصفوفات غير المربعة إلى نصفين باستخدام نفس الطرق، مما ينتج عنه مصفوفات غير مربعة أصغر. إذا كانت المصفوفات غير مربعة بدرجة كافية، فسيكون من المفيد تقليل العملية الأولية إلى عمليات ضرب أكثر مربعة، باستخدام طرق بسيطة هي في الأساس ${\displaystyle O(n^{2})}$، على سبيل المثال:

• منتج ذو حجم${\displaystyle [2N\times N]\ast [N\times 10N]}$يمكن القيام بذلك على شكل 20 عملية منفصلة${\displaystyle [N\times N]\ast [N\times N]}$العمليات، المرتبة لتشكيل النتيجة؛
• منتج ذو حجم${\displaystyle [N\times 10N]\ast [10N\times N]}$يمكن القيام بذلك على شكل 10 أجزاء منفصلة${\displaystyle [N\times N]\ast [N\times N]}$العمليات، التي يتم جمعها لتشكيل النتيجة.

ستجعل هذه التقنيات التنفيذ أكثر تعقيدًا، مقارنةً بمجرد إضافة الحشو إلى مربع قوة اثنين؛ ومع ذلك، من المعقول افتراض أن أي شخص يقوم بتنفيذ Strassen، بدلاً من الضرب التقليدي، سيضع أولوية أعلى على الكفاءة الحسابية من بساطة التنفيذ.

عمليًا، يمكن تطبيق خوارزمية ستراسن لتحقيق أداء أفضل من الضرب التقليدي حتى بالنسبة للمصفوفات الصغيرة جدًا${\displaystyle 500\times 500}$^{[ 4 ]} بالنسبة للمصفوفات غير المربعة على الإطلاق، ودون الحاجة إلى مساحة عمل تتجاوز المخازن المؤقتة اللازمة بالفعل لعملية الضرب التقليدية عالية الأداء.

• التعقيد الحسابي للعمليات الرياضية
• حذف جاوس-جوردان
• التعقيد الحسابي لضرب المصفوفات
• منحنى ترتيب Z
• خوارزمية كاراتسوبا ، لضرب الأعداد الصحيحة المكونة من n رقمًا في${\displaystyle O(n^{\log _{2}3})}$بدلاً من في${\displaystyle O(n^{2})}$وقت
  • تستخدم خوارزمية ضرب الأعداد المركبة المماثلة 3 عمليات ضرب حقيقية بدلاً من 4 عمليات لضرب عددين مركبين
• خوارزمية توم-كوك ، وهي تعميم أسرع لخوارزمية كاراتسوبا، تسمح بتقسيم البيانات بشكل متكرر إلى أكثر من كتلتين في وقت واحد.

• توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7الفصل 28: القسم 28.2: خوارزمية ستراسن لضرب المصفوفات، الصفحات  735-741 .
• كنوت، دونالد (1997). فن برمجة الحاسوب ، الخوارزميات شبه العددية . المجلد  الثاني (  الطبعة الثالثة). أديسون-ويسلي. ISBN 0-201-89684-2.

• وايسشتاين، اريك دبليو “صيغ ستراسين” . عالم الرياضيات .(يتضمن أيضًا صيغًا لعكس المصفوفة بسرعة )
• تايلر ج. إرنست، خوارزمية ستراسن على محرك النطاق العريض الخلوي