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

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

जहां u = (c - a)(C - D), v = (c + d)(C - A), w = aA + (c + d - a)(A + D - C) है। इससे आव्यूह में जोड़ और घटाव की संख्या 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 में मानचित्र सम्मिलित होते हैं, (अर्थात इस स्थिति में हैडामर्ड उत्पाद की सभी प्रविष्टियों का योग होता है।)

	मानक एल्गोरिदम				स्ट्रैसेन एल्गोरिथ्म
$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-ऑर्डर आव्यूह प्रतिनिधित्व
• करात्सुबा एल्गोरिदम, n-अंकीय पूर्णांकों को गुणा करने के लिए $O(n^{\log _{2}3})$ के अतिरिक्त $O(n^{2})$ समय
  • समान गुणन एल्गोरिथ्म 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