स्ट्रैसेन एल्गोरिदम

Not to be confused with बहुपदों के गुणन के लिए शॉनहेज-स्ट्रैसेन एल्गोरिथ्म.

रैखिक बीजगणित में, स्ट्रैसेन एल्गोरिदम, जिसका नाम वोल्कर स्ट्रैसेन के नाम पर रखा गया है, जो आव्यूह गुणन के लिए एल्गोरिदम है। यह उत्तम एसिम्प्टोटिक समिष्टता के साथ बड़े आव्यूह के लिए मानक आव्यूह गुणन एल्गोरिदम से तीव्र है, चूँकि छोटे आव्यूह के लिए अनुभवहीन एल्गोरिदम प्रायः उत्तम होता है। स्ट्रैसन एल्गोरिदम अत्यधिक बड़े आव्यूह के लिए सबसे तीव्र ज्ञात एल्गोरिदम से धीमा है, किन्तु ऐसे गैलेक्टिक एल्गोरिदम व्यवहार में उपयोगी नहीं हैं, क्योंकि वे व्यावहारिक आकार के आव्यूहके लिए अधिक धीमे होते हैं। छोटे आव्यूह के लिए और भी तीव्र एल्गोरिदम उपस्थित हैं।

स्ट्रैसन का एल्गोरिदम किसी भी वलय के लिए कार्य करता है, जैसे कि प्लस/गुणा, किन्तु सभी सेमीरिंग्स के लिए नहीं, जैसे कि मिन-प्लस या बूलियन बीजगणित, जहां अनुभवहीन एल्गोरिदम अभी भी कार्य करता है, और तथाकथित कॉम्बिनेटरियल आव्यूह गुणन है।

इतिहास

वोल्कर स्ट्रैसन ने पहली बार इस एल्गोरिदम को 1969 में प्रकाशित किया और इस तरह यह साबित हुआ कि $n^{3}$ सामान्य आव्यूहगुणन एल्गोरिथ्म इष्टतम नहीं था। स्ट्रैसेन एल्गोरिदम के प्रकाशन के परिणामस्वरूप आव्यूहगुणन के बारे में अधिक शोध हुआ, जिससे असम्बद्ध रूप से निचली सीमाएं और कम्प्यूटेशनल ऊपरी सीमाएं उत्तम हुईं।

एल्गोरिथम

केंद्र। सरल आव्यूहगुणन के लिए बाएं कॉलम के प्रत्येक 1 के लिए गुणन की आवश्यकता होती है। प्रत्येक अन्य कॉलम (M1-M7) स्ट्रैसेन एल्गोरिथ्म में 7 गुणन में से का प्रतिनिधित्व करता है। कॉलम M1-M7 का योग बाईं ओर पूर्ण आव्यूहगुणन के समान परिणाम देता है।

होने देना $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$

साथ $A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})$. अनुभवहीन एल्गोरिदम होगा:

${\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}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{bmatrix}}.$

यह निर्माण गुणन की संख्या को कम नहीं करता है: गणना के लिए आव्यूहब्लॉक के 8 गुणन की अभी भी आवश्यकता है $C_{ij}$ मैट्रिक्स, मानक आव्यूहगुणन का उपयोग करते समय समान संख्या में गुणन की आवश्यकता होती है।

स्ट्रैसेन एल्गोरिथ्म इसके अतिरिक्त नए आव्यूहको परिभाषित करता है:

${\begin{aligned}M_{1}&=(A_{11}+A_{22})(B_{11}+B_{22});\\M_{2}&=(A_{21}+A_{22})B_{11};\\M_{3}&=A_{11}(B_{12}-B_{22});\\M_{4}&=A_{22}(B_{21}-B_{11});\\M_{5}&=(A_{11}+A_{12})B_{22};\\M_{6}&=(A_{21}-A_{11})(B_{11}+B_{12});\\M_{7}&=(A_{12}-A_{22})(B_{21}+B_{22}),\\\end{aligned}}$

केवल 7 गुणन का उपयोग करके (प्रत्येक के लिए )। $M_{k}$) के अतिरिक्त 8. अब हम व्यक्त कर सकते हैं $C_{ij}$ के अनुसार $M_{k}$:

${\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}&M_{3}+M_{5}\\M_{2}+M_{4}&M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.$

हम इस विभाजन प्रक्रिया को तब तक दोहराते रहते हैं जब तक कि उपमात्राएं संख्याओं (वलयके तत्व) में परिवर्तित न हो जाएं ${\mathcal {R}}$). यदि, जैसा कि ऊपर बताया गया है, मूल आव्यूहका आकार 2 की शक्ति नहीं था, तो परिणामी उत्पाद में शून्य पंक्तियाँ और स्तंभ होंगे जैसे $A$ और $B$, और फिर इन्हें (छोटा) आव्यूहप्राप्त करने के लिए इस बिंदु पर हटा दिया जाएगा $C$ हम वास्तव में चाहते थे।

स्ट्रैसेन के एल्गोरिदम का व्यावहारिक कार्यान्वयन छोटे पर्याप्त सबमैट्रिस के लिए आव्यूहगुणन के मानक तरीकों पर स्विच करता है, जिसके लिए वे एल्गोरिदम अधिक कुशल होते हैं। वह विशेष क्रॉसओवर बिंदु जिसके लिए स्ट्रैसेन का एल्गोरिदम अधिक कुशल है, विशिष्ट कार्यान्वयन और हार्डवेयर पर निर्भर करता है। पहले के लेखकों ने अनुमान लगाया था कि अनुकूलित कार्यान्वयन के लिए स्ट्रैसेन का एल्गोरिदम 32 से 128 तक की चौड़ाई वाले आव्यूहके लिए तेज़ है। चूँकि, यह देखा गया है कि यह क्रॉसओवर पॉइंट हाल के वर्षों में बढ़ रहा है, और 2010 के अध्ययन में पाया गया कि स्ट्रैसेन के एल्गोरिथ्म का भी चरण प्रायः वर्तमान आर्किटेक्चर पर अत्यधिक अनुकूलित पारंपरिक गुणन की तुलना में फायदेमंद नहीं होता है, जब तक कि आव्यूहका आकार अधिक न हो जाए 1000 या अधिक, और यहां तक ​​कि कई हजार के आव्यूहआकार के लिए भी लाभ सामान्यतः सीमांत (लगभग 10% या उससे कम) होता है। हालिया अध्ययन (2016) में 512 जितने छोटे आव्यूहके लिए लाभ और लगभग 20% का लाभ देखा गया।

विनोग्राड फॉर्म

विनोग्राड द्वारा खोजे गए निम्नलिखित फॉर्म का उपयोग करके आव्यूहपरिवर्धन की संख्या को कम करना संभव है:

${\begin{bmatrix}a&b\\c&d\end{bmatrix}}{\begin{bmatrix}A&C\\B&D\end{bmatrix}}={\begin{bmatrix}aA+bB&w+v+(a+b-c-d)D\\w+u+d(B+C-A-D)&w+u+v\end{bmatrix}}$ जहां यू = (सी - ए) (सी - डी), वी = (सी + डी) (सी - ए), डब्ल्यू = एए + (सी + डी - ए) (ए + डी - सी)। इससे आव्यूहजोड़ और घटाव की संख्या 18 से घटकर 15 हो जाती है। आव्यूहगुणन की संख्या अभी भी 7 है, और स्पर्शोन्मुख जटिलता समान है।

स्पर्शोन्मुख जटिलता

उपरोक्त एल्गोरिदम की रूपरेखा से पता चला है कि आव्यूहके उप-ब्लॉकों के लिए पारंपरिक 8, मैट्रिक्स-आव्यूहगुणन के अतिरिक्त, केवल 7 से ही छुटकारा पाया जा सकता है। दूसरी ओर, किसी को ब्लॉकों का जोड़ और घटाव करना पड़ता है, चूँकि यह समग्र जटिलता के लिए कोई चिंता का विषय नहीं है: आकार के आव्यूहजोड़ना $N/2$ केवल आवश्यकता है $(N/2)^{2}$ संचालन जबकि गुणन काफी हद तक अधिक महंगा है (परंपरागत रूप से)। $2(N/2)^{3}$ जोड़ या गुणन संक्रियाएँ)।

फिर सवाल यह है कि स्ट्रैसेन के एल्गोरिदम के लिए वास्तव में कितने ऑपरेशनों की आवश्यकता होती है, और इसकी तुलना मानक आव्यूहगुणन से कैसे की जाती है जो लगभग लेता है $2N^{3}$ (कहाँ $N=2^{n}$) अंकगणितीय संक्रियाएं, अर्थात स्पर्शोन्मुख जटिलता $\Theta (N^{3})$.

स्ट्रैसेन एल्गोरिथ्म में आवश्यक जोड़ और गुणन की संख्या की गणना निम्नानुसार की जा सकती है: चलो $f(n)$ a के लिए परिचालनों की संख्या हो $2^{n}\times 2^{n}$ आव्यूह। फिर स्ट्रैसेन एल्गोरिथम के पुनरावर्ती अनुप्रयोग द्वारा, हम इसे देखते हैं $f(n)=7f(n-1)+l4^{n}$, कुछ स्थिरांक के लिए $l$ यह एल्गोरिथम के प्रत्येक अनुप्रयोग में किए गए परिवर्धन की संख्या पर निर्भर करता है। इस तरह $f(n)=(7+o(1))^{n}$, अर्थात, आकार के आव्यूहों को गुणा करने के लिए स्पर्शोन्मुख जटिलता $N=2^{n}$ स्ट्रैसेन एल्गोरिथ्म का उपयोग करना है $O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})$. चूँकि, अंकगणितीय परिचालनों की संख्या में कमी कुछ हद तक कम संख्यात्मक स्थिरता की कीमत पर आती है, और एल्गोरिथ्म को भी अनुभवहीन एल्गोरिदम की तुलना में काफी अधिक मेमोरी की आवश्यकता होती है। दोनों प्रारंभिक आव्यूहमें उनके आयामों को 2 की अगली शक्ति तक विस्तारित किया जाना चाहिए, जिसके परिणामस्वरूप चार गुना तक तत्व संग्रहीत होते हैं, और सात सहायक आव्यूहमें प्रत्येक विस्तारित में चौथाई तत्व होते हैं।

स्ट्रैसेन के एल्गोरिदम की तुलना आव्यूहगुणन करने के सरल तरीके से करने की आवश्यकता है जिसके लिए उप-ब्लॉक के 7 गुणन के अतिरिक्त 8 की आवश्यकता होगी। इसके बाद मानक दृष्टिकोण से अपेक्षित जटिलता उत्पन्न हो जाएगी: $O(8^{\log _{2}n})=O(N^{\log _{2}8})=O(N^{3})$. इन दो एल्गोरिदम की तुलना से पता चलता है कि स्पर्शोन्मुख रूप से, स्ट्रैसेन का एल्गोरिदम तेज़ है: आकार उपस्थित है $N_{\text{threshold}}$ ताकि बड़े आव्यूहको पारंपरिक तरीके की तुलना में स्ट्रैसेन के एल्गोरिदम के साथ अधिक कुशलता से गुणा किया जा सके। चूँकि, एसिम्प्टोटिक कथन का अर्थ यह नहीं है कि स्ट्रैसेन का एल्गोरिथ्म हमेशा छोटे आव्यूहके लिए भी तेज़ होता है, और व्यवहार में यह वास्तव में मामला नहीं है: छोटे आव्यूहके लिए, आव्यूहब्लॉक के अतिरिक्त परिवर्धन की लागत संख्या में बचत से अधिक है गुणन. ऐसे अन्य कारक भी हैं जिन्हें ऊपर दिए गए विश्लेषण में सम्मिलित नहीं किया गया है, जैसे कि मेमोरी से प्रोसेसर पर डेटा लोड करने के मध्य आज के हार्डवेयर की लागत में अंतर और इस डेटा पर वास्तव में संचालन करने की लागत। इस प्रकार के विचारों के परिणामस्वरूप, स्ट्रैसेन का एल्गोरिदम सामान्यतः केवल बड़े आव्यूहपर उपयोग किया जाता है। इस प्रकार का प्रभाव वैकल्पिक एल्गोरिदम के साथ और भी अधिक स्पष्ट होता है जैसे कि कॉपरस्मिथ-विनोग्राड एल्गोरिदम द्वारा: जबकि स्पर्शोन्मुख रूप से और भी तेज़, क्रॉस-ओवर बिंदु $N_{\text{threshold}}$ इतना बड़ा है कि एल्गोरिथ्म का उपयोग सामान्यतः व्यवहार में आने वाले आव्यूहपर नहीं किया जाता है।

रैंक या द्विरेखीय जटिलता

द्विरेखीय जटिलता या द्विरेखीय मानचित्र की रैंक आव्यूहगुणन की स्पर्शोन्मुख जटिलता में महत्वपूर्ण अवधारणा है। द्विरेखीय मानचित्र की श्रेणी $\phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C}$ फ़ील्ड F को इस प्रकार परिभाषित किया गया है (कुछ हद तक संकेतन का दुरुपयोग)

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

दूसरे शब्दों में, द्विरेखीय मानचित्र की रैंक उसकी सबसे छोटी द्विरेखीय गणना की लंबाई है। स्ट्रैसेन के एल्गोरिदम के अस्तित्व से पता चलता है कि रैंक $2\times 2$ आव्यूहगुणन सात से अधिक नहीं है। इसे देखने के लिए, आइए हम इस एल्गोरिदम को (मानक एल्गोरिदम के साथ) ऐसे द्विरेखीय गणना के रूप में व्यक्त करें। आव्यूहके मामले में, दोहरे स्थान A* और B* में अदिश डायडिक्स#डायडिक और डायडिक|डबल-डॉट उत्पाद द्वारा प्रेरित फ़ील्ड F में मानचित्र सम्मिलित होते हैं, (अर्थात इस मामले में सभी प्रविष्टियों का योग होता है) हैडामर्ड उत्पाद (मैट्रिसेस)।)

	Standard algorithm				Strassen algorithm
$i$	$f_{i}(\mathbf {a} )$	$g_{i}(\mathbf {b} )$	$w_{i}$		$f_{i}(\mathbf {a} )$	$g_{i}(\mathbf {b} )$	$w_{i}$
1	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$		${\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\0&1\end{bmatrix}}$
2	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$		${\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\1&-1\end{bmatrix}}$
3	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}$		${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&1\\0&1\end{bmatrix}}$
4	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}$		${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\1&0\end{bmatrix}}$
5	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}$		${\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}-1&1\\0&0\end{bmatrix}}$
6	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}$		${\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$
7	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$		${\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$
8	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$
	$\mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$				$\mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$

यह दिखाया जा सकता है कि प्रारंभिक गुणन की कुल संख्या $L$ आव्यूहगुणन के लिए आवश्यक रूप से रैंक के साथ कसकर बंधा हुआ है $R$, अर्थात। $L=\Theta (R)$, या अधिक विशेष रूप से, चूंकि स्थिरांक ज्ञात हैं, $R/2\leq L\leq R$. रैंक की उपयोगी संपत्ति यह है कि यह टेंसर उत्पादों के लिए उपगुणक है, और यह किसी को यह दिखाने में सक्षम बनाता है $2^{n}\times 2^{n}\times 2^{n}$ आव्यूहगुणन इससे अधिक नहीं के साथ पूरा किया जा सकता है $7n$ किसी के लिए प्राथमिक गुणन $n$. (यह $n$-फोल्ड टेंसर उत्पाद का $2\times 2\times 2$ स्वयं के साथ आव्यूहगुणन मानचित्र - $n$-वें टेंसर पावर-दिखाए गए एल्गोरिदम में पुनरावर्ती चरण द्वारा महसूस किया जाता है।)

कैश व्यवहार

स्ट्रैसेन का एल्गोरिदम कैश-विस्मृत एल्गोरिथ्म है। इसके सीपीयू कैश व्यवहार एल्गोरिदम के विश्लेषण से पता चला है कि ऐसा हुआ है

$\Theta \left(1+{\frac {n^{2}}{b}}+{\frac {n^{\log _{2}7}}{b{\sqrt {M}}}}\right)$

कैश अपने निष्पादन के दौरान चूक जाता है, आकार का आदर्श कैश मान लिया जाता है $M$ (अर्थात साथ $M/b$ लंबाई की रेखाएँ $b$).

कार्यान्वयन संबंधी विचार

उपरोक्त विवरण में कहा गया है कि आव्यूहवर्गाकार हैं, और आकार दो की घात है, और यदि आवश्यक हो तो पैडिंग का उपयोग किया जाना चाहिए। यह प्रतिबंध अदिश गुणन की सीमा तक पहुंचने तक आव्यूहको पुनरावर्ती रूप से आधे में विभाजित करने की अनुमति देता है। प्रतिबंध स्पष्टीकरण और जटिलता के विश्लेषण को सरल बनाता है, किन्तु वास्तव में यह आवश्यक नहीं है; और वास्तव में, वर्णित आव्यूहको पैडिंग करने से गणना का समय बढ़ जाएगा और पहली जगह में विधि का उपयोग करके प्राप्त काफी संकीर्ण समय की बचत को आसानी से समाप्त किया जा सकता है।

अच्छा कार्यान्वयन निम्नलिखित का पालन करेगा:

• स्केलर की सीमा तक स्ट्रैसन एल्गोरिदम का उपयोग करना आवश्यक या वांछनीय नहीं है। पारंपरिक आव्यूहगुणन की तुलना में, एल्गोरिथ्म काफी कुछ जोड़ता है $O(n^{2})$ जोड़/घटाव में कार्यभार; इसलिए निश्चित आकार से नीचे, पारंपरिक गुणन का उपयोग करना उत्तम होगा। इस प्रकार, उदाहरण के लिए, ए $1600\times 1600$ गद्देदार होने की जरूरत नहीं है $2048\times 2048$, चूँकि इसे निम्न में विभाजित किया जा सकता है $25\times 25$ फिर आव्यूहऔर पारंपरिक गुणन का उपयोग उस स्तर पर किया जा सकता है।
• यह विधि वास्तव में किसी भी आयाम के वर्ग आव्यूहों पर लागू की जा सकती है। यदि आयाम सम है, तो वे वर्णित के अनुसार आधे में विभाजित हो जाते हैं। यदि आयाम विषम है, तो पहले पंक्ति और कॉलम द्वारा शून्य पैडिंग लागू की जाती है। इस तरह की पैडिंग को तुरंत और आलस्य से लागू किया जा सकता है, और परिणाम बनते ही अतिरिक्त पंक्तियों और स्तंभों को हटा दिया जाता है। उदाहरण के लिए, मान लीजिए आव्यूहहैं $199\times 199$. उन्हें विभाजित किया जा सकता है ताकि ऊपरी-बाएँ भाग हो $100\times 100$ और निचला-दायाँ है $99\times 99$. जहां भी संचालन के लिए इसकी आवश्यकता होती है, वहां के आयाम $99$ शून्य गद्देदार हैं $100$ पहला। उदाहरण के लिए, ध्यान दें कि उत्पाद $M_{2}$ इसका उपयोग केवल आउटपुट की निचली पंक्ति में किया जाता है, इसलिए इसे केवल होना आवश्यक है $99$ ऊँची पंक्तियाँ; और इस प्रकार बायाँ कारक $A_{21}+A_{22}$ इसे उत्पन्न करने के लिए केवल आवश्यकता होती है $99$ ऊँची पंक्तियाँ; तदनुसार, उस राशि को पैड करने की कोई आवश्यकता नहीं है $100$ पंक्तियाँ; इसे केवल पैड करना आवश्यक है $A_{22}$ को $100$ मिलान करने के लिए कॉलम $A_{21}$.

इसके अतिरिक्त, आव्यूहों का वर्गाकार होना आवश्यक नहीं है। गैर-वर्ग आव्यूहों को समान तरीकों का उपयोग करके आधे में विभाजित किया जा सकता है, जिससे छोटे गैर-वर्ग आव्यूह प्राप्त होते हैं। यदि आव्यूहपर्याप्त रूप से गैर-वर्ग हैं तो सरल तरीकों का उपयोग करके प्रारंभिक ऑपरेशन को अधिक वर्ग उत्पादों में कम करना सार्थक होगा जो अनिवार्य रूप से हैं $O(n^{2})$, उदाहरण के लिए:

• आकार का उत्पाद $[2N\times N]\ast [N\times 10N]$ 20 अलग-अलग के रूप में किया जा सकता है $[N\times N]\ast [N\times N]$ संचालन, परिणाम बनाने के लिए व्यवस्थित;
• आकार का उत्पाद $[N\times 10N]\ast [10N\times N]$ 10 अलग-अलग के रूप में किया जा सकता है $[N\times N]\ast [N\times N]$ संचालन, परिणाम बनाने के लिए संक्षेपित।

ये तकनीकें कार्यान्वयन को और अधिक जटिल बना देंगी, केवल दो वर्ग की शक्ति तक पैडिंग करने की तुलना में; चूँकि, यह उचित धारणा है कि पारंपरिक गुणन के अतिरिक्त स्ट्रैसेन का कार्यान्वयन करने वाला कोई भी व्यक्ति, कार्यान्वयन की सरलता की तुलना में कम्प्यूटेशनल दक्षता को अधिक प्राथमिकता देगा।

व्यवहार में, स्ट्रैसेन के एल्गोरिदम को छोटे आव्यूहके लिए भी पारंपरिक गुणन की तुलना में उत्तम प्रदर्शन प्राप्त करने के लिए लागू किया जा सकता है, ऐसे आव्यूहके लिए जो बिल्कुल भी वर्गाकार नहीं हैं, और उच्च प्रदर्शन वाले पारंपरिक गुणन के लिए पहले से ही आवश्यक बफ़र्स से परे कार्यक्षेत्र की आवश्यकता के बिना।

यह भी देखें

• गणितीय संक्रियाओं की कम्प्यूटेशनल जटिलता
• गॉस-जॉर्डन उन्मूलन
• कॉपरस्मिथ-विनोग्राड एल्गोरिथम
• Z-ऑर्डर (वक्र)|Z-ऑर्डर आव्यूहप्रतिनिधित्व
• करात्सुबा एल्गोरिदम, एन-अंकीय पूर्णांकों को गुणा करने के लिए $O(n^{\log _{2}3})$ के अतिरिक्त अंदर $O(n^{2})$ समय
  • समान गुणन एल्गोरिथ्म#Complex_number_multiplication 4 के अतिरिक्त 3 वास्तविक गुणन का उपयोग करके दो जटिल संख्याओं को गुणा करता है
• टूम-कुक गुणन|टूम-कुक एल्गोरिदम, करात्सुबा एल्गोरिदम का तेज़ सामान्यीकरण जो समय में 2 से अधिक ब्लॉकों में पुनरावर्ती विभाजन और जीत अपघटन की अनुमति देता है

संदर्भ

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Section 28.2: Strassen's algorithm for matrix multiplication, pp. 735–741.
• Knuth, Donald (1997). The Art of Computer Programming, Seminumerical Algorithms. Vol. II (3rd ed.). Addison-Wesley. ISBN 0-201-89684-2.

बाहरी संबंध

• Weisstein, Eric W. "Strassen's Formulas". MathWorld. (also includes formulas for fast matrix inversion)
• Tyler J. Earnest, Strassen's Algorithm on the Cell Broadband Engine