स्ट्रैसेन एल्गोरिदम: Difference between revisions

Latest revision as of 13:17, 1 November 2023

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

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

इतिहास

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

एल्गोरिथम

केंद्र। सरल आव्यूह गुणन के लिए बाएं कॉलम के प्रत्येक 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 तक की चौड़ाई वाले आव्यूह के लिए स्ट्रैसेन का एल्गोरिदम तीव्र है।^[2] चूँकि, यह देखा गया है कि यह क्रॉसओवर पॉइंट वर्तमान के वर्षों में बढ़ रहा है, और 2010 के अध्ययन में पाया गया कि स्ट्रैसेन के एल्गोरिथ्म का चरण प्रायः वर्तमान संरचना पर अत्यधिक अनुकूलित पारंपरिक गुणन की तुलना में लाभदायक नहीं होता है, जब तक कि आव्यूह का आकार 1000 या उससे अधिक न हो जाए, और यहां तक कि कई हजार के आव्यूह आकार के लिए भी लाभ सामान्यतः सबसे उचित सीमांत (लगभग 10% या उससे कम) होता है।^[3] वर्तमान अध्ययन (2016) में 512 जितने छोटे आव्यूह के लिए लाभ और लगभग 20% का लाभ देखा गया है।^[4]

विनोग्राड रूप

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

${\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 है, और स्पर्शोन्मुख समिष्टता समान है।^[5]

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

उपरोक्त एल्गोरिदम की रूपरेखा से ज्ञात होता है कि आव्यूह के उप-ब्लॉकों के लिए पारंपरिक 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})$ उपयोग करता है। चूँकि, अंकगणितीय परिचालनों की संख्या में अल्पता कुछ सीमा तक कम संख्यात्मक स्थिरता की कीमत पर आती है,^[6] और एल्गोरिथ्म को भी अनुभवहीन एल्गोरिदम की तुलना में अत्यधिक मेमोरी की आवश्यकता होती है। दोनों प्रारंभिक आव्यूह में उनके आयामों को 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\}

दूसरे शब्दों में, द्विरेखीय मानचित्र की श्रेणी उसकी सबसे छोटी द्विरेखीय गणना की लंबाई है।^[7] स्ट्रैसेन के एल्गोरिदम के अस्तित्व से ज्ञात होता है कि श्रेणी $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$ है)।^[8]^: 13

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

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

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

अदिश की सीमा तक स्ट्रैसन एल्गोरिदम का उपयोग करना आवश्यक या वांछनीय नहीं है। पारंपरिक आव्यूह गुणन की तुलना में, एल्गोरिथ्म अधिक जोड़ता है $O(n^{2})$ जोड़/घटाव में कार्यभार; इसलिए निश्चित आकार से नीचे, पारंपरिक गुणन का उपयोग करना उत्तम होगा। इस प्रकार, उदाहरण के लिए, a $1600\times 1600$ पैडेड बनाने की आवश्यकता नहीं है $2048\times 2048$ , चूँकि इसे निम्न में विभाजित किया जा सकता है $25\times 25$ फिर आव्यूह और पारंपरिक गुणन का उपयोग उस स्तर पर किया जा सकता है।
यह विधि वास्तव में किसी भी आयाम के वर्ग आव्यूहों पर प्रारम्भ की जा सकती है।^[3] यदि आयाम सम है, तो वे वर्णित के अनुसार अर्ध में विभाजित हो जाते हैं। यदि आयाम विषम है, तो प्रथम पंक्ति और स्तंभ द्वारा शून्य पैडिंग प्रारम्भ की जाती है। इस प्रकार की पैडिंग को शीघ्र और आलस्य से प्रारम्भ किया जा सकता है, और परिणाम बनते ही अतिरिक्त पंक्तियों और स्तंभों को विस्थापित कर दिया जाता है। उदाहरण के लिए, मान लीजिए आव्यूह $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]$ संचालन, परिणाम बनाने के लिए संक्षेपित है।

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

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

यह भी देखें

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

संदर्भ

↑ Strassen, Volker (1969). "गाऊसी उन्मूलन इष्टतम नहीं है". Numer. Math. 13 (4): 354–356. doi:10.1007/BF02165411. S2CID 121656251.
↑ Skiena, Steven S. (1998), "§8.2.3 Matrix multiplication", The Algorithm Design Manual, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94860-7.
↑ ^3.0 ^3.1 D'Alberto, Paolo; Nicolau, Alexandru (2005). एटलस के प्रदर्शन को बढ़ावा देने के लिए रिकर्सन का उपयोग करना (PDF). Sixth Int'l Symp. on High Performance Computing.
↑ ^4.0 ^4.1 Huang, Jianyu; Smith, Tyler M.; Henry, Greg M.; van de Geijn, Robert A. (13 Nov 2016). स्ट्रैसेन का एल्गोरिदम पुनः लोड किया गया. SC16: The International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Press. pp. 690–701. doi:10.1109/SC.2016.58. ISBN 9781467388153. Retrieved 1 Nov 2022.
↑ Knuth (1997), p. 500.
↑ Webb, Miller (1975). "कम्प्यूटेशनल जटिलता और संख्यात्मक स्थिरता". SIAM J. Comput. 4 (2): 97–107. doi:10.1137/0204009.
↑ Burgisser; Clausen; Shokrollahi (1997). बीजगणितीय जटिलता सिद्धांत. Springer-Verlag. ISBN 3-540-60582-7.
↑ Frigo, M.; Leiserson, C. E.; Prokop, H.; Ramachandran, S. (1999). कैश-विस्मृत एल्गोरिदम (PDF). Proc. IEEE Symp. on Foundations of Computer Science (FOCS). pp. 285–297.
↑ Higham, Nicholas J. (1990). "Exploiting fast matrix multiplication within the level 3 BLAS" (PDF). ACM Transactions on Mathematical Software. 16 (4): 352–368. doi:10.1145/98267.98290. hdl:1813/6900. S2CID 5715053.

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

[1] Strassen, Volker (1969). "गाऊसी उन्मूलन इष्टतम नहीं है". Numer. Math. 13 (4): 354–356. doi:10.1007/BF02165411. S2CID 121656251.

[2] Skiena, Steven S. (1998), "§8.2.3 Matrix multiplication", The Algorithm Design Manual, Berlin, New York: Springer-Verlag, ISBN 978-0-387-94860-7.

[dalberto-3] 3.0 ^3.1 D'Alberto, Paolo; Nicolau, Alexandru (2005). एटलस के प्रदर्शन को बढ़ावा देने के लिए रिकर्सन का उपयोग करना (PDF). Sixth Int'l Symp. on High Performance Computing.

[huang_et_al.-4] 4.0 ^4.1 Huang, Jianyu; Smith, Tyler M.; Henry, Greg M.; van de Geijn, Robert A. (13 Nov 2016). स्ट्रैसेन का एल्गोरिदम पुनः लोड किया गया. SC16: The International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Press. pp. 690–701. doi:10.1109/SC.2016.58. ISBN 9781467388153. Retrieved 1 Nov 2022.

[FOOTNOTEKnuth1997500-5] Knuth (1997), p. 500.

[6] Webb, Miller (1975). "कम्प्यूटेशनल जटिलता और संख्यात्मक स्थिरता". SIAM J. Comput. 4 (2): 97–107. doi:10.1137/0204009.

[7] Burgisser; Clausen; Shokrollahi (1997). बीजगणितीय जटिलता सिद्धांत. Springer-Verlag. ISBN 3-540-60582-7.

[prokop-8] Frigo, M.; Leiserson, C. E.; Prokop, H.; Ramachandran, S. (1999). कैश-विस्मृत एल्गोरिदम (PDF). Proc. IEEE Symp. on Foundations of Computer Science (FOCS). pp. 285–297.

[9] Higham, Nicholas J. (1990). "Exploiting fast matrix multiplication within the level 3 BLAS" (PDF). ACM Transactions on Mathematical Software. 16 (4): 352–368. doi:10.1145/98267.98290. hdl:1813/6900. S2CID 5715053.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
-{{Short description|Recursive algorithm for matrix multiplication}}
+{{Short description|Recursive algorithm for matrix multiplication}}रैखिक बीजगणित में, '''स्ट्रैसेन एल्गोरिदम''', जिसका नाम वोल्कर स्ट्रैसेन के नाम पर रखा गया है, जो आव्यूह गुणन के लिए एल्गोरिदम है। यह उत्तम एसिम्प्टोटिक समिष्टता के साथ बड़े आव्यूह के लिए मानक आव्यूह गुणन एल्गोरिदम से तीव्र है, चूँकि छोटे आव्यूह के लिए अनुभवहीन एल्गोरिदम प्रायः उत्तम होता है। स्ट्रैसन एल्गोरिदम अत्यधिक बड़े आव्यूह के लिए [[मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता|सबसे तीव्र ज्ञात एल्गोरिदम]] से धीमा है, किन्तु ऐसे [[गैलेक्टिक एल्गोरिदम]] व्यवहार में उपयोगी नहीं हैं, क्योंकि वे व्यावहारिक आकार के आव्यूहके लिए अधिक धीमे होते हैं। छोटे आव्यूह के लिए और भी तीव्र एल्गोरिदम उपस्थित हैं।
-{{distinguish|text=the [[Schönhage–Strassen algorithm]] for multiplication of polynomials}}
-रैखिक बीजगणित में, स्ट्रैसेन एल्गोरिदम, जिसका नाम [[वोल्कर स्ट्रैस]]ेन के नाम पर रखा गया है, एक मैट्रिक्स गुणन एल्गोरिदम है। यह बेहतर एसिम्प्टोटिक जटिलता के साथ बड़े मैट्रिक्स के लिए मानक मैट्रिक्स गुणन एल्गोरिदम से तेज़ है, हालांकि छोटे मैट्रिक्स के लिए अनुभवहीन एल्गोरिदम अक्सर बेहतर होता है। स्ट्रैसन एल्गोरिदम अत्यधिक बड़े मैट्रिक्स के लिए [[मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता]] से धीमा है, लेकिन ऐसे [[गैलेक्टिक एल्गोरिदम]] व्यवहार में उपयोगी नहीं हैं, क्योंकि वे व्यावहारिक आकार के मैट्रिक्स के लिए बहुत धीमे हैं। छोटे मैट्रिक्स के लिए और भी तेज़ एल्गोरिदम मौजूद हैं।
+स्ट्रैसन का एल्गोरिदम किसी भी वलय के लिए कार्य करता है, जैसे कि प्लस/गुणा, किन्तु सभी [[सेमीरिंग्स]] के लिए नहीं, जैसे कि मिन-प्लस या [[बूलियन बीजगणित]], जहां अनुभवहीन एल्गोरिदम अभी भी कार्य करता है, और तथाकथित [[कॉम्बिनेटरियल मैट्रिक्स गुणन|कॉम्बिनेटरियल आव्यूह गुणन]] है।
-स्ट्रैसन का एल्गोरिदम किसी भी रिंग (गणित) के लिए काम करता है, जैसे कि प्लस/गुणा, लेकिन सभी [[सेमीरिंग्स]] के लिए नहीं, जैसे कि मिन-प्लस मैट्रिक्स गुणन|मिन-प्लस या [[बूलियन बीजगणित]], जहां अनुभवहीन एल्गोरिदम अभी भी काम करता है, और तथाकथित [[कॉम्बिनेटरियल मैट्रिक्स गुणन]]
 == इतिहास ==
-वोल्कर स्ट्रैसन ने पहली बार इस एल्गोरिदम को 1969 में प्रकाशित किया और इस तरह यह साबित हुआ कि <math>n^3</math> सामान्य मैट्रिक्स गुणन एल्गोरिथ्म इष्टतम नहीं था।<ref>{{cite journal |last=Strassen |first=Volker |title=गाऊसी उन्मूलन इष्टतम नहीं है|journal=Numer. Math. |volume=13 |issue= 4 |pages=354–356 |year=1969 |doi=10.1007/BF02165411 |s2cid=121656251 }}</ref> स्ट्रैसेन एल्गोरिदम के प्रकाशन के परिणामस्वरूप मैट्रिक्स गुणन के बारे में अधिक शोध हुआ, जिससे असम्बद्ध रूप से निचली सीमाएं और कम्प्यूटेशनल ऊपरी सीमाएं बेहतर हुईं।
+वोल्कर स्ट्रैसन ने प्रथम बार इस एल्गोरिदम को 1969 में प्रकाशित किया और इस प्रकार यह प्रमाणित हुआ कि <math>n^3</math> सामान्य आव्यूह गुणन एल्गोरिथ्म इष्टतम नहीं था।<ref>{{cite journal |last=Strassen |first=Volker |title=गाऊसी उन्मूलन इष्टतम नहीं है|journal=Numer. Math. |volume=13 |issue= 4 |pages=354–356 |year=1969 |doi=10.1007/BF02165411 |s2cid=121656251 }}</ref> स्ट्रैसेन एल्गोरिदम के प्रकाशन के परिणामस्वरूप आव्यूह गुणन के संबंध में अधिक शोध हुआ, जिससे असम्बद्ध रूप से निचली सीमाएं और कम्प्यूटेशनल ऊपरी सीमाएं उत्तम हुईं।
 == एल्गोरिथम ==
-[[Image:Strassen algorithm.svg|thumb|800px|केंद्र। सरल [[मैट्रिक्स गुणन]] के लिए बाएं कॉलम के प्रत्येक 1 के लिए एक गुणन की आवश्यकता होती है। प्रत्येक अन्य कॉलम (M1-M7) स्ट्रैसेन एल्गोरिथ्म में 7 गुणन में से एक का प्रतिनिधित्व करता है। कॉलम M1-M7 का योग बाईं ओर पूर्ण मैट्रिक्स गुणन के समान परिणाम देता है।<!-- Feel free to rewrite this description so it actually makes sense. -->]]होने देना <math>A</math>, <math>B</math> एक रिंग के ऊपर दो [[वर्ग मैट्रिक्स]] बनें (गणित) <math>\mathcal{R}</math>, उदाहरण के लिए आव्यूह जिनकी प्रविष्टियाँ पूर्णांक या वास्तविक संख्याएँ हैं। मैट्रिक्स गुणन का लक्ष्य मैट्रिक्स उत्पाद की गणना करना है <math>C = AB</math>. एल्गोरिथम की निम्नलिखित व्याख्या मानती है कि इन सभी आव्यूहों के आकार दो की घात हैं (अर्थात्, <math>A, \, B, \, C \in \operatorname{Matr}_{2^n \times 2^n} (\mathcal{R})</math>), लेकिन यह केवल वैचारिक रूप से आवश्यक है - यदि मैट्रिक्स <math>A</math>, <math>B</math> प्रकार के नहीं हैं <math>2^n \times 2^n</math>, दो की घात के आकार वाले मैट्रिक्स प्राप्त करने के लिए लुप्त पंक्तियों और स्तंभों को शून्य से भरा जा सकता है - हालांकि एल्गोरिथ्म के वास्तविक कार्यान्वयन व्यवहार में ऐसा नहीं करते हैं।
+[[Image:Strassen algorithm.svg|thumb|800px|केंद्र। सरल [[मैट्रिक्स गुणन|आव्यूह गुणन]] के लिए बाएं कॉलम के प्रत्येक 1 के लिए  गुणन की आवश्यकता होती है। प्रत्येक अन्य कॉलम (M1-M7) स्ट्रैसेन एल्गोरिथ्म में 7 गुणन में से एक का प्रतिनिधित्व करता है। कॉलम M1-M7 का योग बाईं ओर पूर्ण आव्यूह गुणन के समान परिणाम देता है।]]मान लीजिये कि <math>A</math>, <math>B</math>  वलय के ऊपर दो [[वर्ग मैट्रिक्स|वर्ग]] आव्यूह <math>\mathcal{R}</math> हों, उदाहरण के लिए आव्यूह जिनकी प्रविष्टियाँ पूर्णांक या वास्तविक संख्याएँ हैं। आव्यूह गुणन का लक्ष्य आव्यूह उत्पाद <math>C = AB</math> की गणना करना है। एल्गोरिथम की निम्नलिखित व्याख्या मानती है कि इन सभी आव्यूहों के आकार दो की घात हैं (अर्थात्, <math>A, \, B, \, C \in \operatorname{Matr}_{2^n \times 2^n} (\mathcal{R})</math>), किन्तु यह केवल वैचारिक रूप से आवश्यक है - यदि आव्यूह<math>A</math>, <math>B</math> <math>2^n \times 2^n</math> प्रकार के नहीं हैं, दो की घात के आकार वाले आव्यूह प्राप्त करने के लिए लुप्त पंक्तियों और स्तंभों को शून्य से भरा जा सकता है - चूँकि एल्गोरिथ्म के वास्तविक कार्यान्वयन व्यवहार में ऐसा नहीं करते हैं।
-स्ट्रैसेन एल्गोरिथम विभाजन <math>A</math>, <math>B</math> और <math>C</math> समान आकार के [[ब्लॉक मैट्रिक्स]] में
+स्ट्रैसेन एल्गोरिथम विभाजन <math>A</math>, <math>B</math> और <math>C</math> समान आकार के [[ब्लॉक मैट्रिक्स|ब्लॉक]] आव्यूह में हैं;
 :<math>
 A =
@@ Line 30: / Line 27: @@
 \end{bmatrix}, \quad
 </math>
-साथ <math>A_{ij}, B_{ij}, C_{ij} \in \operatorname{Mat}_{2^{n-1} \times 2^{n-1}} (\mathcal{R})</math>. अनुभवहीन एल्गोरिदम होगा:
+साथ <math>A_{ij}, B_{ij}, C_{ij} \in \operatorname{Mat}_{2^{n-1} \times 2^{n-1}} (\mathcal{R})</math> अनुभवहीन एल्गोरिदम होगा:
 : <math>
@@ Line 45: / Line 42: @@
 \end{bmatrix}.
 </math>
-यह निर्माण गुणन की संख्या को कम नहीं करता है: गणना के लिए मैट्रिक्स ब्लॉक के 8 गुणन की अभी भी आवश्यकता है <math>C_{ij}</math> मैट्रिक्स, मानक मैट्रिक्स गुणन का उपयोग करते समय समान संख्या में गुणन की आवश्यकता होती है।
+यह निर्माण गुणन की संख्या को कम नहीं करता है: गणना के लिए आव्यूह ब्लॉक के 8 गुणन की अभी भी आवश्यकता है <math>C_{ij}</math> आव्यूह, मानक आव्यूह गुणन का उपयोग करते समय समान संख्या में गुणन की आवश्यकता होती है।
-स्ट्रैसेन एल्गोरिथ्म इसके बजाय नए मैट्रिक्स को परिभाषित करता है:
+स्ट्रैसेन एल्गोरिथ्म इसके अतिरिक्त नए आव्यूह को परिभाषित करता है:
 : <math>
@@ Line 60: / Line 57: @@
 \end{align}
 </math>
-केवल 7 गुणन का उपयोग करके (प्रत्येक के लिए एक)। <math>M_k</math>) के बजाय 8. अब हम व्यक्त कर सकते हैं <math>C_{ij}</math> के अनुसार <math>M_k</math>:
+केवल 7 गुणन का उपयोग करके (प्रत्येक के लिए)। <math>M_k</math>) के अतिरिक्त 8 है। अब हम <math>C_{ij}</math> के अनुसार <math>M_k</math> व्यक्त कर सकते हैं:
 : <math>
@@ Line 75: / Line 72: @@
 \end{bmatrix}.
 </math>
-हम इस विभाजन प्रक्रिया को तब तक दोहराते रहते हैं जब तक कि उपमात्राएं संख्याओं (रिंग के तत्व) में परिवर्तित न हो जाएं <math>\mathcal{R}</math>). यदि, जैसा कि ऊपर बताया गया है, मूल मैट्रिक्स का आकार 2 की शक्ति नहीं था, तो परिणामी उत्पाद में शून्य पंक्तियाँ और स्तंभ होंगे जैसे <math>A</math> और <math>B</math>, और फिर इन्हें (छोटा) मैट्रिक्स प्राप्त करने के लिए इस बिंदु पर हटा दिया जाएगा <math>C</math> हम वास्तव में चाहते थे।
+हम इस विभाजन प्रक्रिया को तब तक दोहराते रहते हैं जब तक कि उपमात्राएं संख्याओं (वलय के तत्व) <math>\mathcal{R}</math> में परिवर्तित न हो जाएं। यदि, जैसा कि ऊपर बताया गया है, मूल आव्यूह का आकार 2 की शक्ति नहीं था, तो परिणामी उत्पाद में शून्य पंक्तियाँ और स्तंभ होंगे जैसे <math>A</math> और <math>B</math>, और फिर इन्हें (छोटा) आव्यूह प्राप्त करने के लिए इस बिंदु पर विस्थापित कर दिया जाएगा <math>C</math> हम वास्तव में चाहते थे।
-स्ट्रैसेन के एल्गोरिदम का व्यावहारिक कार्यान्वयन छोटे पर्याप्त सबमैट्रिस के लिए मैट्रिक्स गुणन के मानक तरीकों पर स्विच करता है, जिसके लिए वे एल्गोरिदम अधिक कुशल होते हैं। वह विशेष क्रॉसओवर बिंदु जिसके लिए स्ट्रैसेन का एल्गोरिदम अधिक कुशल है, विशिष्ट कार्यान्वयन और हार्डवेयर पर निर्भर करता है। पहले के लेखकों ने अनुमान लगाया था कि अनुकूलित कार्यान्वयन के लिए स्ट्रैसेन का एल्गोरिदम 32 से 128 तक की चौड़ाई वाले मैट्रिक्स के लिए तेज़ है।<ref>{{Citation | last1=Skiena | first1=Steven S. | title=The Algorithm Design Manual | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-94860-7 | year=1998 | chapter=§8.2.3 Matrix multiplication}}.</ref> हालाँकि, यह देखा गया है कि यह क्रॉसओवर पॉइंट हाल के वर्षों में बढ़ रहा है, और 2010 के एक अध्ययन में पाया गया कि स्ट्रैसेन के एल्गोरिथ्म का एक भी चरण अक्सर वर्तमान आर्किटेक्चर पर अत्यधिक अनुकूलित पारंपरिक गुणन की तुलना में फायदेमंद नहीं होता है, जब तक कि मैट्रिक्स का आकार अधिक न हो जाए 1000 या अधिक, और यहां तक कि कई हजार के मैट्रिक्स आकार के लिए भी लाभ आम तौर पर सीमांत (लगभग 10% या उससे कम) होता है।<ref name="dalberto"/>  एक हालिया अध्ययन (2016) में 512 जितने छोटे मैट्रिक्स के लिए लाभ और लगभग 20% का लाभ देखा गया।<ref name="huang et al."/>
+स्ट्रैसेन के एल्गोरिदम का व्यावहारिक कार्यान्वयन छोटे पर्याप्त सबमैट्रिस के लिए आव्यूह गुणन के मानक विधियों पर स्विच करता है, जिसके लिए वे एल्गोरिदम अधिक कुशल होते हैं। वह विशेष क्रॉसओवर बिंदु जिसके लिए स्ट्रैसेन का एल्गोरिदम अधिक कुशल है, विशिष्ट कार्यान्वयन और हार्डवेयर पर निर्भर करता है। पूर्व के लेखकों ने अनुमान लगाया था कि अनुकूलित कार्यान्वयन के लिए 32 से 128 तक की चौड़ाई वाले आव्यूह के लिए स्ट्रैसेन का एल्गोरिदम तीव्र है।<ref>{{Citation | last1=Skiena | first1=Steven S. | title=The Algorithm Design Manual | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-94860-7 | year=1998 | chapter=§8.2.3 Matrix multiplication}}.</ref> चूँकि, यह देखा गया है कि यह क्रॉसओवर पॉइंट वर्तमान के वर्षों में बढ़ रहा है, और 2010 के  अध्ययन में पाया गया कि स्ट्रैसेन के एल्गोरिथ्म का चरण प्रायः वर्तमान संरचना पर अत्यधिक अनुकूलित पारंपरिक गुणन की तुलना में लाभदायक नहीं होता है, जब तक कि आव्यूह का आकार 1000 या उससे अधिक न हो जाए, और यहां तक कि कई हजार के आव्यूह आकार के लिए भी लाभ सामान्यतः सबसे उचित सीमांत (लगभग 10% या उससे कम) होता है।<ref name="dalberto"/> वर्तमान अध्ययन (2016) में 512 जितने छोटे आव्यूह के लिए लाभ और लगभग 20% का लाभ देखा गया है।<ref name="huang et al."/>
+== विनोग्राड रूप ==
-== विनोग्राड फॉर्म ==
+विनोग्राड द्वारा शोध किये गए निम्नलिखित रूप का उपयोग करके आव्यूह परिवर्धन की संख्या को कम करना संभव है:
-विनोग्राड द्वारा खोजे गए निम्नलिखित फॉर्म का उपयोग करके मैट्रिक्स परिवर्धन की संख्या को कम करना संभव है:
 <math>
@@ Line 99: / Line 94: @@
 \end{bmatrix}
 </math>
-जहां यू = (सी - ए) (सी - डी), वी = (सी + डी) (सी - ए), डब्ल्यू = एए + (सी + डी - ए) (ए + डी - सी)। इससे मैट्रिक्स जोड़ और घटाव की संख्या 18 से घटकर 15 हो जाती है। मैट्रिक्स गुणन की संख्या अभी भी 7 है, और स्पर्शोन्मुख जटिलता समान है।{{sfnp|Knuth|1997|p=500}}
-== स्पर्शोन्मुख जटिलता ==
+जहां u = (c - a)(C - D), v = (c + d)(C - A), w = aA + (c + d - a)(A + D - C) है। इससे आव्यूह में जोड़ और घटाव की संख्या 18 से घटकर 15 हो जाती है। आव्यूह गुणन की संख्या अभी भी 7 है, और स्पर्शोन्मुख समिष्टता समान है।{{sfnp|Knuth|1997|p=500}}
-उपरोक्त एल्गोरिदम की रूपरेखा से पता चला है कि मैट्रिक्स के उप-ब्लॉकों के लिए पारंपरिक 8, मैट्रिक्स-मैट्रिक्स गुणन के बजाय, केवल 7 से ही छुटकारा पाया जा सकता है। दूसरी ओर, किसी को ब्लॉकों का जोड़ और घटाव करना पड़ता है, हालांकि यह समग्र जटिलता के लिए कोई चिंता का विषय नहीं है: आकार के मैट्रिक्स जोड़ना <math>N/2</math> केवल आवश्यकता है <math>(N/2)^2</math> संचालन जबकि गुणन काफी हद तक अधिक महंगा है (परंपरागत रूप से)। <math>2 (N/2)^3</math> जोड़ या गुणन संक्रियाएँ)।
+== स्पर्शोन्मुख समिष्टता ==
-फिर सवाल यह है कि स्ट्रैसेन के एल्गोरिदम के लिए वास्तव में कितने ऑपरेशनों की आवश्यकता होती है, और इसकी तुलना मानक मैट्रिक्स गुणन से कैसे की जाती है जो लगभग लेता है <math>2 N^3</math> (कहाँ <math>N = 2^n</math>) अंकगणितीय संक्रियाएं, यानी एक स्पर्शोन्मुख जटिलता <math>\Theta (N^3)</math>.
+उपरोक्त एल्गोरिदम की रूपरेखा से  ज्ञात होता है कि आव्यूह के उप-ब्लॉकों के लिए पारंपरिक 8, आव्यूह गुणन के अतिरिक्त, केवल 7 से ही छुटकारा पाया जा सकता है। दूसरी ओर, किसी को ब्लॉकों का जोड़ और घटाव करना पड़ता है, चूँकि यह समग्र समिष्टता के लिए कोई चिंता का विषय नहीं है: आकार के आव्यूह जोड़न केवल <math>N/2</math> की आवश्यकता है <math>(N/2)^2</math> संचालन जबकि गुणन अधिक सीमा तक अधिक महंगा है (परंपरागत रूप से)। <math>2 (N/2)^3</math> जोड़ या गुणन संक्रियाएँ)।
-स्ट्रैसेन एल्गोरिथ्म में आवश्यक जोड़ और गुणन की संख्या की गणना निम्नानुसार की जा सकती है: चलो <math>f(n)</math> a के लिए परिचालनों की संख्या हो <math>2^n \times 2^n</math> आव्यूह। फिर स्ट्रैसेन एल्गोरिथम के पुनरावर्ती अनुप्रयोग द्वारा, हम इसे देखते हैं <math>f(n) = 7 f(n-1) + l 4^n</math>, कुछ स्थिरांक के लिए <math>l</math> यह एल्गोरिथम के प्रत्येक अनुप्रयोग में किए गए परिवर्धन की संख्या पर निर्भर करता है। इस तरह <math>f(n) = (7 + o(1))^n</math>, यानी, आकार के आव्यूहों को गुणा करने के लिए स्पर्शोन्मुख जटिलता <math>N = 2^n</math> स्ट्रैसेन एल्गोरिथ्म का उपयोग करना है  <math>O([7+o(1)]^n) = O(N^{\log_{2}7+o(1)}) \approx O(N^{2.8074})</math>. हालाँकि, अंकगणितीय परिचालनों की संख्या में कमी कुछ हद तक कम [[संख्यात्मक स्थिरता]] की कीमत पर आती है,<ref>{{cite journal|last=Webb|first=Miller|title=कम्प्यूटेशनल जटिलता और संख्यात्मक स्थिरता|journal=SIAM J. Comput.|year=1975|volume=4|issue=2|pages=97–107 |doi=10.1137/0204009 }}</ref> और एल्गोरिथ्म को भी अनुभवहीन एल्गोरिदम की तुलना में काफी अधिक मेमोरी की आवश्यकता होती है। दोनों प्रारंभिक मैट्रिक्स में उनके आयामों को 2 की अगली शक्ति तक विस्तारित किया जाना चाहिए, जिसके परिणामस्वरूप चार गुना तक तत्व संग्रहीत होते हैं, और सात सहायक मैट्रिक्स में प्रत्येक विस्तारित में एक चौथाई तत्व होते हैं।
+तब प्रश्न यह है कि स्ट्रैसेन के एल्गोरिदम के लिए वास्तव में कितने संचालनों की आवश्यकता होती है, और इसकी तुलना मानक आव्यूह गुणन से कैसे की जाती है जो लगभग <math>2 N^3</math> (जहाँ <math>N = 2^n</math>) अंकगणितीय संक्रियाएं, अर्थात स्पर्शोन्मुख समिष्टता <math>\Theta (N^3)</math> लेता है।
-स्ट्रैसेन के एल्गोरिदम की तुलना मैट्रिक्स गुणन करने के सरल तरीके से करने की आवश्यकता है जिसके लिए उप-ब्लॉक के 7 गुणन के बजाय 8 की आवश्यकता होगी। इसके बाद मानक दृष्टिकोण से अपेक्षित जटिलता उत्पन्न हो जाएगी: <math>O(8^{\log_{2}n}) = O(N^{\log_{2}8}) = O(N^3)</math>. इन दो एल्गोरिदम की तुलना से पता चलता है कि स्पर्शोन्मुख रूप से, स्ट्रैसेन का एल्गोरिदम तेज़ है: एक आकार मौजूद है <math>N_\text{threshold}</math> ताकि बड़े मैट्रिक्स को पारंपरिक तरीके की तुलना में स्ट्रैसेन के एल्गोरिदम के साथ अधिक कुशलता से गुणा किया जा सके। हालाँकि, एसिम्प्टोटिक कथन का अर्थ यह नहीं है कि स्ट्रैसेन का एल्गोरिथ्म हमेशा छोटे मैट्रिक्स के लिए भी तेज़ होता है, और व्यवहार में यह वास्तव में मामला नहीं है: छोटे मैट्रिक्स के लिए, मैट्रिक्स ब्लॉक के अतिरिक्त परिवर्धन की लागत संख्या में बचत से अधिक है गुणन. ऐसे अन्य कारक भी हैं जिन्हें ऊपर दिए गए विश्लेषण में शामिल नहीं किया गया है, जैसे कि मेमोरी से प्रोसेसर पर डेटा लोड करने के बीच आज के हार्डवेयर की लागत में अंतर और इस डेटा पर वास्तव में संचालन करने की लागत। इस प्रकार के विचारों के परिणामस्वरूप, स्ट्रैसेन का एल्गोरिदम आमतौर पर केवल बड़े मैट्रिक्स पर उपयोग किया जाता है। इस प्रकार का प्रभाव वैकल्पिक एल्गोरिदम के साथ और भी अधिक स्पष्ट होता है जैसे कि [[कॉपरस्मिथ-विनोग्राड एल्गोरिदम]] द्वारा: जबकि स्पर्शोन्मुख रूप से और भी तेज़, क्रॉस-ओवर बिंदु <math>N_\text{threshold}</math> इतना बड़ा है कि एल्गोरिथ्म का उपयोग आम तौर पर व्यवहार में आने वाले मैट्रिक्स पर नहीं किया जाता है।
+स्ट्रैसेन एल्गोरिथ्म में आवश्यक जोड़ और गुणन की संख्या की गणना निम्नानुसार की जा सकती है: मान लीजिये कि <math>f(n)</math> a के लिए परिचालनों की संख्या <math>2^n \times 2^n</math> आव्यूह हो। तब स्ट्रैसेन एल्गोरिथम के पुनरावर्ती अनुप्रयोग द्वारा, हम इसे देखते हैं <math>f(n) = 7 f(n-1) + l 4^n</math>, कुछ स्थिरांक के लिए <math>l</math> यह एल्गोरिथम के प्रत्येक अनुप्रयोग में किए गए परिवर्धन की संख्या पर निर्भर करता है। इस प्रकार <math>f(n) = (7 + o(1))^n</math>, अर्थात, आकार के आव्यूहों को गुणा करने के लिए स्पर्शोन्मुख समिष्टता <math>N = 2^n</math> स्ट्रैसेन एल्गोरिथ्म का  <math>O([7+o(1)]^n) = O(N^{\log_{2}7+o(1)}) \approx O(N^{2.8074})</math>उपयोग करता है। चूँकि, अंकगणितीय परिचालनों की संख्या में अल्पता कुछ सीमा तक कम [[संख्यात्मक स्थिरता]] की कीमत पर आती है,<ref>{{cite journal|last=Webb|first=Miller|title=कम्प्यूटेशनल जटिलता और संख्यात्मक स्थिरता|journal=SIAM J. Comput.|year=1975|volume=4|issue=2|pages=97–107 |doi=10.1137/0204009 }}</ref> और एल्गोरिथ्म को भी अनुभवहीन एल्गोरिदम की तुलना में अत्यधिक मेमोरी की आवश्यकता होती है। दोनों प्रारंभिक आव्यूह में उनके आयामों को 2 की अगली शक्ति तक विस्तारित किया जाना चाहिए, जिसके परिणामस्वरूप चार गुना तक तत्व संग्रहीत होते हैं, और सात सहायक आव्यूहमें प्रत्येक विस्तारित में एक चौथाई तत्व होते हैं।
-=== रैंक या द्विरेखीय जटिलता ===
+स्ट्रैसेन के एल्गोरिदम की तुलना आव्यूह गुणन करने के सरल प्रकार से करने की आवश्यकता है जिसके लिए उप-ब्लॉक के 7 गुणन के अतिरिक्त 8 की आवश्यकता होगी। इसके पश्चात मानक दृष्टिकोण से अपेक्षित समिष्टता उत्पन्न हो जाएगी: <math>O(8^{\log_{2}n}) = O(N^{\log_{2}8}) = O(N^3)</math> इन दो एल्गोरिदम की तुलना से ज्ञात होता है कि स्पर्शोन्मुख रूप से, स्ट्रैसेन का एल्गोरिदम तीव्र है: आकार उपस्थित है <math>N_\text{threshold}</math> जिससे बड़े आव्यूह को पारंपरिक रूप की तुलना में स्ट्रैसेन के एल्गोरिदम के साथ अधिक कुशलता से गुणा किया जा सके। चूँकि, एसिम्प्टोटिक कथन का अर्थ यह नहीं है कि स्ट्रैसेन का एल्गोरिथ्म सदैव छोटे आव्यूह के लिए भी तीव्र होता है, और व्यवहार में यह वास्तव में स्थिति नहीं है: छोटे आव्यूह के लिए, आव्यूह ब्लॉक के अतिरिक्त परिवर्धन के व्यय गुणन संख्या में बचत से अधिक है। ऐसे अन्य कारक भी हैं जिन्हें ऊपर दिए गए विश्लेषण में सम्मिलित नहीं किया गया है, जैसे कि मेमोरी से प्रोसेसर पर डेटा लोड करने के मध्य वर्तमान के हार्डवेयर के व्यय में अंतर और इस डेटा पर वास्तव में संचालन करने के व्यय से है। इस प्रकार के विचारों के परिणामस्वरूप, स्ट्रैसेन का एल्गोरिदम सामान्यतः केवल बड़े आव्यूह पर उपयोग किया जाता है। [[कॉपरस्मिथ-विनोग्राड एल्गोरिदम|कॉपरस्मिथ]] और [[कॉपरस्मिथ-विनोग्राड एल्गोरिदम|विनोग्राड]] जैसे वैकल्पिक एल्गोरिदम के साथ इस प्रकार का प्रभाव और भी अधिक स्पष्ट होता है: जबकि स्पर्शोन्मुख रूप से और भी तीव्र, क्रॉस-ओवर बिंदु <math>N_\text{threshold}</math> इतना बड़ा है कि एल्गोरिथ्म का उपयोग सामान्यतः व्यवहार में आने वाले आव्यूह पर नहीं किया जाता है।
-द्विरेखीय जटिलता या [[द्विरेखीय मानचित्र]] की रैंक मैट्रिक्स गुणन की स्पर्शोन्मुख जटिलता में एक महत्वपूर्ण अवधारणा है। द्विरेखीय मानचित्र की श्रेणी <math>\phi:\mathbf A \times \mathbf B \rightarrow \mathbf C</math> फ़ील्ड F को इस प्रकार परिभाषित किया गया है (कुछ हद तक संकेतन का दुरुपयोग)
+=== श्रेणी या द्विरेखीय समिष्टता ===
+द्विरेखीय समिष्टता या [[द्विरेखीय मानचित्र]] की श्रेणी आव्यूह गुणन की स्पर्शोन्मुख समिष्टता में महत्वपूर्ण अवधारणा है। द्विरेखीय मानचित्र की श्रेणी <math>\phi:\mathbf A \times \mathbf B \rightarrow \mathbf C</math> क्षेत्र F को इस प्रकार परिभाषित किया गया है (कुछ सीमा तक संकेतन का दुरुपयोग)।
 :<math>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\}</math>
-दूसरे शब्दों में, एक द्विरेखीय मानचित्र की रैंक उसकी सबसे छोटी द्विरेखीय गणना की लंबाई है।<ref>{{cite book |last1=Burgisser |last2=Clausen |last3=Shokrollahi |title=बीजगणितीय जटिलता सिद्धांत|publisher=Springer-Verlag |year=1997 |isbn=3-540-60582-7 }}</ref> स्ट्रैसेन के एल्गोरिदम के अस्तित्व से पता चलता है कि रैंक <math>2 \times 2</math> मैट्रिक्स गुणन सात से अधिक नहीं है। इसे देखने के लिए, आइए हम इस एल्गोरिदम को (मानक एल्गोरिदम के साथ) ऐसे द्विरेखीय गणना के रूप में व्यक्त करें। मैट्रिक्स के मामले में, दोहरे स्थान A* और B* में एक अदिश डायडिक्स#डायडिक और डायडिक|डबल-डॉट उत्पाद द्वारा प्रेरित फ़ील्ड F में मानचित्र शामिल होते हैं, (यानी इस मामले में सभी प्रविष्टियों का योग होता है) एक [[हैडामर्ड उत्पाद (मैट्रिसेस)]]।)
+दूसरे शब्दों में, द्विरेखीय मानचित्र की श्रेणी उसकी सबसे छोटी द्विरेखीय गणना की लंबाई है।<ref>{{cite book |last1=Burgisser |last2=Clausen |last3=Shokrollahi |title=बीजगणितीय जटिलता सिद्धांत|publisher=Springer-Verlag |year=1997 |isbn=3-540-60582-7 }}</ref> स्ट्रैसेन के एल्गोरिदम के अस्तित्व से ज्ञात होता है कि श्रेणी <math>2 \times 2</math> आव्यूह गुणन सात से अधिक नहीं है। इसे देखने के लिए, आइए हम इस एल्गोरिदम को (मानक एल्गोरिदम के साथ) ऐसे द्विरेखीय गणना के रूप में व्यक्त करें। आव्यूह की स्थिति में, दोहरे स्थान A* और B* में अदिश '''डबल-डॉट उत्पाद''' द्वारा प्रेरित क्षेत्र F में मानचित्र सम्मिलित होते हैं, (अर्थात इस स्थिति में [[हैडामर्ड उत्पाद (मैट्रिसेस)|हैडामर्ड उत्पाद]] की सभी प्रविष्टियों का योग होता है।)
 {| class = "wikitable"
-| || colspan="3" | Standard algorithm || ||colspan="3" | Strassen algorithm
+| || colspan="3" | मानक एल्गोरिदम || ||colspan="3" | स्ट्रैसेन एल्गोरिथ्म
 |-
 || <math>i</math> || <math>f_i (\mathbf{a})</math> || <math>g_i (\mathbf{b})</math> || <math>w_i</math> || || <math>f_i (\mathbf{a})</math> || <math>g_i (\mathbf{b})</math> || <math>w_i</math>
@@ Line 195: / Line 191: @@
 |colspan="3"|<math>\mathbf a\mathbf b = \sum_{i=1}^7 f_i(\mathbf a)g_i(\mathbf b)w_i</math>
 |}
-यह दिखाया जा सकता है कि प्रारंभिक गुणन की कुल संख्या <math>L</math> मैट्रिक्स गुणन के लिए आवश्यक रूप से रैंक के साथ कसकर बंधा हुआ है <math>R</math>, अर्थात। <math>L = \Theta(R)</math>, या अधिक विशेष रूप से, चूंकि स्थिरांक ज्ञात हैं, <math>R / 2 \le L \le R</math>. रैंक की एक उपयोगी संपत्ति यह है कि यह [[टेंसर उत्पाद]]ों के लिए उपगुणक है, और यह किसी को यह दिखाने में सक्षम बनाता है <math>2^n \times 2^n \times 2^n</math> मैट्रिक्स गुणन इससे अधिक नहीं के साथ पूरा किया जा सकता है <math>7n</math> किसी के लिए प्राथमिक गुणन <math>n</math>. (यह <math>n</math>-फोल्ड टेंसर उत्पाद का <math>2 \times 2 \times 2</math> स्वयं के साथ मैट्रिक्स गुणन मानचित्र - एक <math>n</math>-वें टेंसर पावर-दिखाए गए एल्गोरिदम में पुनरावर्ती चरण द्वारा महसूस किया जाता है।)
+यह दिखाया जा सकता है कि प्रारंभिक गुणन की कुल संख्या आव्यूह गुणन के लिए आवश्यक <math>L</math> श्रेणी के साथ बंधा हुआ है <math>R</math>, अर्थात। <math>L = \Theta(R)</math>, या अधिक विशेष रूप से, चूंकि स्थिरांक <math>R / 2 \le L \le R</math> ज्ञात हैं। श्रेणी की उपयोगी संपत्ति यह है कि यह [[टेंसर उत्पाद|टेंसर उत्पादों]] के लिए उपगुणक है, और यह किसी को यह दिखाने में सक्षम बनाता है <math>2^n \times 2^n \times 2^n</math> आव्यूह गुणन इससे अधिक नहीं पूर्ण किया जा सकता है <math>7n</math> किसी के लिए प्राथमिक गुणन <math>n</math> है। (यह <math>n</math>-फोल्ड टेंसर उत्पाद का <math>2 \times 2 \times 2</math> स्वयं के साथ आव्यूह गुणन मानचित्र -  <math>n</math>-वें टेंसर पावर-दिखाए गए एल्गोरिदम में पुनरावर्ती चरण द्वारा अनुभूत किया जाता है।)
 ===कैश व्यवहार===
-स्ट्रैसेन का एल्गोरिदम [[कैश-विस्मृत एल्गोरिथ्म]] है। इसके [[सीपीयू कैश]] व्यवहार एल्गोरिदम के विश्लेषण से पता चला है कि ऐसा हुआ है
+स्ट्रैसेन का एल्गोरिदम [[कैश-विस्मृत एल्गोरिथ्म]] है। इसके [[सीपीयू कैश|कैश]] व्यवहार एल्गोरिदम के विश्लेषण से ज्ञात होता है कि ऐसा हुआ है:
 :<math>\Theta \left(1 + \frac{n^2}{b} + \frac{n^{\log_2 7}}{b\sqrt{M}} \right)</math>
-कैश अपने निष्पादन के दौरान चूक जाता है, आकार का एक आदर्श कैश मान लिया जाता है <math>M</math> (अर्थात साथ <math>M / b</math> लंबाई की रेखाएँ <math>b</math>).<ref name="prokop">{{cite conference |first1=M. |last1=Frigo |first2=C. E. |last2=Leiserson |authorlink2=Charles Leiserson |first3=H. |last3=Prokop |authorlink3=Harald Prokop |first4=S. |last4=Ramachandran |title=कैश-विस्मृत एल्गोरिदम|conference=Proc. IEEE Symp. on Foundations of Computer Science (FOCS) |pages=285–297 |year=1999 |url=http://supertech.csail.mit.edu/papers/FrigoLePr99.pdf}}</ref>{{rp|13}}
+कैश अपने निष्पादन के समय छूट जाता है, आकार का आदर्श कैश मान <math>M</math> लिया जाता है (अर्थात साथ <math>M / b</math> लंबाई की रेखाएँ <math>b</math> है)।<ref name="prokop">{{cite conference |first1=M. |last1=Frigo |first2=C. E. |last2=Leiserson |authorlink2=Charles Leiserson |first3=H. |last3=Prokop |authorlink3=Harald Prokop |first4=S. |last4=Ramachandran |title=कैश-विस्मृत एल्गोरिदम|conference=Proc. IEEE Symp. on Foundations of Computer Science (FOCS) |pages=285–297 |year=1999 |url=http://supertech.csail.mit.edu/papers/FrigoLePr99.pdf}}</ref>{{rp|13}}
 == कार्यान्वयन संबंधी विचार ==
-{{refimprove section|date=January 2015}}
+उपरोक्त विवरण में कहा गया है कि आव्यूह वर्गाकार हैं, और आकार दो की घात है, और यदि आवश्यक हो तो पैडिंग का उपयोग किया जाना चाहिए। यह प्रतिबंध अदिश गुणन की सीमा तक पहुंचने तक आव्यूह को पुनरावर्ती रूप से अर्ध में विभाजित करने की अनुमति देता है। प्रतिबंध स्पष्टीकरण और समिष्टता के विश्लेषण को सरल बनाता है, किन्तु वास्तव में यह आवश्यक नहीं है;<ref>{{cite journal |last=Higham |first=Nicholas J. |title=Exploiting fast matrix multiplication within the level 3 BLAS |journal=ACM Transactions on Mathematical Software |volume=16 |issue=4 |year=1990 |pages=352–368 |url=http://www.maths.manchester.ac.uk/~higham/papers/high90s.pdf |doi=10.1145/98267.98290|hdl=1813/6900 |s2cid=5715053 |hdl-access=free }}</ref> और वास्तव में, वर्णित आव्यूह को पैडिंग करने से गणना का समय बढ़ जाएगा और प्रथम समिष्ट में विधि का उपयोग करके प्राप्त संकीर्ण समय की बचत को सरलता से समाप्त किया जा सकता है।
-उपरोक्त विवरण में कहा गया है कि मैट्रिक्स वर्गाकार हैं, और आकार दो की घात है, और यदि आवश्यक हो तो पैडिंग का उपयोग किया जाना चाहिए। यह प्रतिबंध अदिश गुणन की सीमा तक पहुंचने तक मैट्रिक्स को पुनरावर्ती रूप से आधे में विभाजित करने की अनुमति देता है। प्रतिबंध स्पष्टीकरण और जटिलता के विश्लेषण को सरल बनाता है, लेकिन वास्तव में यह आवश्यक नहीं है;<ref>{{cite journal |last=Higham |first=Nicholas J. |title=Exploiting fast matrix multiplication within the level 3 BLAS |journal=ACM Transactions on Mathematical Software |volume=16 |issue=4 |year=1990 |pages=352–368 |url=http://www.maths.manchester.ac.uk/~higham/papers/high90s.pdf |doi=10.1145/98267.98290|hdl=1813/6900 |s2cid=5715053 |hdl-access=free }}</ref>
-और वास्तव में, वर्णित मैट्रिक्स को पैडिंग करने से गणना का समय बढ़ जाएगा और पहली जगह में विधि का उपयोग करके प्राप्त काफी संकीर्ण समय की बचत को आसानी से समाप्त किया जा सकता है।
-एक अच्छा कार्यान्वयन निम्नलिखित का पालन करेगा:
-* स्केलर की सीमा तक स्ट्रैसन एल्गोरिदम का उपयोग करना आवश्यक या वांछनीय नहीं है। पारंपरिक मैट्रिक्स गुणन की तुलना में, एल्गोरिथ्म काफी कुछ जोड़ता है <math>O(n^{2})</math> जोड़/घटाव में कार्यभार; इसलिए एक निश्चित आकार से नीचे, पारंपरिक गुणन का उपयोग करना बेहतर होगा। इस प्रकार, उदाहरण के लिए, ए <math>1600 \times 1600</math> गद्देदार होने की जरूरत नहीं है <math>2048 \times 2048</math>, चूँकि इसे निम्न में विभाजित किया जा सकता है <math>25 \times 25</math> फिर मैट्रिक्स और पारंपरिक गुणन का उपयोग उस स्तर पर किया जा सकता है।
+उचित कार्यान्वयन निम्नलिखित का पालन करेगा:
-* यह विधि वास्तव में किसी भी आयाम के वर्ग आव्यूहों पर लागू की जा सकती है।<ref name="dalberto">{{cite conference |first1=Paolo |last1=D'Alberto |first2=Alexandru |last2=Nicolau |title=एटलस के प्रदर्शन को बढ़ावा देने के लिए रिकर्सन का उपयोग करना|year=2005 |conference=Sixth Int'l Symp. on High Performance Computing |url=https://www.ics.uci.edu/~paolo/Reference/paoloA.ishp-vi.pdf}}</ref> यदि आयाम सम है, तो वे वर्णित के अनुसार आधे में विभाजित हो जाते हैं। यदि आयाम विषम है, तो पहले एक पंक्ति और एक कॉलम द्वारा शून्य पैडिंग लागू की जाती है। इस तरह की पैडिंग को तुरंत और आलस्य से लागू किया जा सकता है, और परिणाम बनते ही अतिरिक्त पंक्तियों और स्तंभों को हटा दिया जाता है। उदाहरण के लिए, मान लीजिए मैट्रिक्स हैं <math>199 \times 199</math>. उन्हें विभाजित किया जा सकता है ताकि ऊपरी-बाएँ भाग हो <math>100 \times 100</math> और निचला-दायाँ है <math>99 \times 99</math>. जहां भी संचालन के लिए इसकी आवश्यकता होती है, वहां के आयाम <math>99</math> शून्य गद्देदार हैं <math>100</math> पहला। उदाहरण के लिए, ध्यान दें कि उत्पाद <math>M_2</math> इसका उपयोग केवल आउटपुट की निचली पंक्ति में किया जाता है, इसलिए इसे केवल होना आवश्यक है <math>99</math> ऊँची पंक्तियाँ; और इस प्रकार बायाँ कारक <math>A_{21} + A_{22}</math> इसे उत्पन्न करने के लिए केवल आवश्यकता होती है <math>99</math> ऊँची पंक्तियाँ; तदनुसार, उस राशि को पैड करने की कोई आवश्यकता नहीं है <math>100</math> पंक्तियाँ; इसे केवल पैड करना आवश्यक है <math>A_{22}</math> को <math>100</math> मिलान करने के लिए कॉलम <math>A_{21}</math>.
-इसके अलावा, आव्यूहों का वर्गाकार होना आवश्यक नहीं है। गैर-वर्ग आव्यूहों को समान तरीकों का उपयोग करके आधे में विभाजित किया जा सकता है, जिससे छोटे गैर-वर्ग आव्यूह प्राप्त होते हैं। यदि मैट्रिक्स पर्याप्त रूप से गैर-वर्ग हैं तो सरल तरीकों का उपयोग करके प्रारंभिक ऑपरेशन को अधिक वर्ग उत्पादों में कम करना सार्थक होगा जो अनिवार्य रूप से हैं  <math>O(n^{2})</math>,  उदाहरण के लिए:
+* अदिश की सीमा तक स्ट्रैसन एल्गोरिदम का उपयोग करना आवश्यक या वांछनीय नहीं है। पारंपरिक आव्यूह गुणन की तुलना में, एल्गोरिथ्म अधिक जोड़ता है <math>O(n^{2})</math> जोड़/घटाव में कार्यभार; इसलिए निश्चित आकार से नीचे, पारंपरिक गुणन का उपयोग करना उत्तम होगा। इस प्रकार, उदाहरण के लिए, a <math>1600 \times 1600</math> पैडेड बनाने की आवश्यकता नहीं है <math>2048 \times 2048</math>, चूँकि इसे निम्न में विभाजित किया जा सकता है <math>25 \times 25</math> फिर आव्यूह और पारंपरिक गुणन का उपयोग उस स्तर पर किया जा सकता है।
+* यह विधि वास्तव में किसी भी आयाम के वर्ग आव्यूहों पर प्रारम्भ की जा सकती है।<ref name="dalberto">{{cite conference |first1=Paolo |last1=D'Alberto |first2=Alexandru |last2=Nicolau |title=एटलस के प्रदर्शन को बढ़ावा देने के लिए रिकर्सन का उपयोग करना|year=2005 |conference=Sixth Int'l Symp. on High Performance Computing |url=https://www.ics.uci.edu/~paolo/Reference/paoloA.ishp-vi.pdf}}</ref> यदि आयाम सम है, तो वे वर्णित के अनुसार अर्ध में विभाजित हो जाते हैं। यदि आयाम विषम है, तो प्रथम पंक्ति और स्तंभ द्वारा शून्य पैडिंग प्रारम्भ की जाती है। इस प्रकार की पैडिंग को शीघ्र और आलस्य से प्रारम्भ किया जा सकता है, और परिणाम बनते ही अतिरिक्त पंक्तियों और स्तंभों को विस्थापित कर दिया जाता है। उदाहरण के लिए, मान लीजिए आव्यूह <math>199 \times 199</math> है। उन्हें विभाजित किया जा सकता है जिससे ऊपरी-बाएँ भाग <math>100 \times 100</math> है और निचला-दायाँ <math>99 \times 99</math> है। जहां भी संचालन के लिए इसकी आवश्यकता होती है, वहां के आयाम <math>99</math> शून्य पैडेड हैं प्रथम <math>100</math> हैं। उदाहरण के लिए, ध्यान दें कि उत्पाद <math>M_2</math> का उपयोग केवल आउटपुट की निचली पंक्ति में किया जाता है, इसलिए इसे केवल <math>99</math> होना आवश्यक है, ऊँची पंक्तियाँ; और इस प्रकार बायाँ कारक <math>A_{21} + A_{22}</math> इसे उत्पन्न करने के लिए केवल <math>99</math> की आवश्यकता होती है ऊँची पंक्तियाँ; तदनुसार, उस राशि को पैड करने की कोई आवश्यकता नहीं है <math>100</math> पंक्तियाँ; इसे केवल पैड करना आवश्यक है <math>A_{22}</math> को <math>100</math> मिलान करने के लिए स्तंभ<math>A_{21}</math> है।
-* आकार का एक उत्पाद <math>[2N \times N] \ast [N \times 10N]</math> 20 अलग-अलग के रूप में किया जा सकता है <math>[N \times N] \ast [N \times N]</math> संचालन, परिणाम बनाने के लिए व्यवस्थित;
+इसके अतिरिक्त, आव्यूहों का वर्गाकार होना आवश्यक नहीं है। गैर-वर्ग आव्यूहों को समान विधियों का उपयोग करके अर्ध में विभाजित किया जा सकता है, जिससे छोटे गैर-वर्ग आव्यूह प्राप्त होते हैं। यदि आव्यूह पर्याप्त रूप से गैर-वर्ग हैं तो सरल विधियों का उपयोग करके प्रारंभिक ऑपरेशन को अधिक वर्ग उत्पादों में कम करना सार्थक होगा जो अनिवार्य रूप से हैं  <math>O(n^{2})</math>,  उदाहरण के लिए:
-* आकार का एक उत्पाद <math>[N \times 10N] \ast [10N \times N]</math> 10 अलग-अलग के रूप में किया जा सकता है <math>[N \times N] \ast [N \times N]</math> संचालन, परिणाम बनाने के लिए संक्षेपित।
-ये तकनीकें कार्यान्वयन को और अधिक जटिल बना देंगी, केवल दो वर्ग की शक्ति तक पैडिंग करने की तुलना में; हालाँकि, यह एक उचित धारणा है कि पारंपरिक गुणन के बजाय स्ट्रैसेन का कार्यान्वयन करने वाला कोई भी व्यक्ति, कार्यान्वयन की सरलता की तुलना में कम्प्यूटेशनल दक्षता को अधिक प्राथमिकता देगा।
+* आकार का उत्पाद <math>[2N \times N] \ast [N \times 10N]</math> 20 भिन्न-भिन्न रूप में किया जा सकता है <math>[N \times N] \ast [N \times N]</math> संचालन, परिणाम बनाने के लिए व्यवस्थित है;
+* आकार का उत्पाद <math>[N \times 10N] \ast [10N \times N]</math> 10 भिन्न-भिन्न रूप में किया जा सकता है <math>[N \times N] \ast [N \times N]</math> संचालन, परिणाम बनाने के लिए संक्षेपित है।
-व्यवहार में, स्ट्रैसेन के एल्गोरिदम को छोटे मैट्रिक्स के लिए भी पारंपरिक गुणन की तुलना में बेहतर प्रदर्शन प्राप्त करने के लिए लागू किया जा सकता है, ऐसे मैट्रिक्स के लिए जो बिल्कुल भी वर्गाकार नहीं हैं, और उच्च प्रदर्शन वाले पारंपरिक गुणन के लिए पहले से ही आवश्यक बफ़र्स से परे कार्यक्षेत्र की आवश्यकता के बिना।<ref name="huang et al.">{{cite conference |last1=Huang |first1=Jianyu |last2=Smith |first2=Tyler M. |last3=Henry |first3=Greg M. |last4=van de Geijn |first4=Robert A. |date=13 Nov 2016 |title=स्ट्रैसेन का एल्गोरिदम पुनः लोड किया गया|url=https://www.researchgate.net/publication/315365781 |conference=SC16: The International Conference for High Performance Computing, Networking, Storage and Analysis |publisher=IEEE Press |doi=10.1109/SC.2016.58 |isbn=9781467388153 |pages=690–701 |access-date=1 Nov 2022 |conference-url=https://ieeexplore.ieee.org/xpl/conhome/7875333/proceeding}}</ref>
+ये प्रौद्योगिकी कार्यान्वयन को और अधिक समिष्ट बना देंगी, केवल दो वर्ग की शक्ति तक पैडिंग करने की तुलना में; चूँकि, यह उचित धारणा है कि पारंपरिक गुणन के अतिरिक्त स्ट्रैसेन का कार्यान्वयन करने वाला कोई भी व्यक्ति, कार्यान्वयन की सरलता की तुलना में कम्प्यूटेशनल दक्षता को अधिक प्राथमिकता देगा।
+व्यवहार में, स्ट्रैसेन के एल्गोरिदम को छोटे आव्यूह के लिए भी पारंपरिक गुणन की तुलना में उत्तम प्रदर्शन प्राप्त करने के लिए लागू किया जा सकता है, ऐसे आव्यूहके लिए जो बिल्कुल भी वर्गाकार नहीं हैं, और बफ़र्स से परे कार्यक्षेत्र की आवश्यकता के बिना जो पूर्व से ही उच्च-प्रदर्शन वाले पारंपरिक गुणन के लिए आवश्यक हैं।<ref name="huang et al.">{{cite conference |last1=Huang |first1=Jianyu |last2=Smith |first2=Tyler M. |last3=Henry |first3=Greg M. |last4=van de Geijn |first4=Robert A. |date=13 Nov 2016 |title=स्ट्रैसेन का एल्गोरिदम पुनः लोड किया गया|url=https://www.researchgate.net/publication/315365781 |conference=SC16: The International Conference for High Performance Computing, Networking, Storage and Analysis |publisher=IEEE Press |doi=10.1109/SC.2016.58 |isbn=9781467388153 |pages=690–701 |access-date=1 Nov 2022 |conference-url=https://ieeexplore.ieee.org/xpl/conhome/7875333/proceeding}}</ref>
 == यह भी देखें ==
-* [[गणितीय संक्रियाओं की कम्प्यूटेशनल जटिलता]]
+* [[गणितीय संक्रियाओं की कम्प्यूटेशनल जटिलता|गणितीय संक्रियाओं की कम्प्यूटेशनल समिष्टता]]
 * गॉस-जॉर्डन उन्मूलन
 * कॉपरस्मिथ-विनोग्राड एल्गोरिथम
-* Z-ऑर्डर (वक्र)|Z-ऑर्डर मैट्रिक्स प्रतिनिधित्व
+* Z-ऑर्डर आव्यूह प्रतिनिधित्व
-* [[करात्सुबा एल्गोरिदम]], एन-अंकीय पूर्णांकों को गुणा करने के लिए <math>O(n^{\log_2 3})</math> के बजाय अंदर <math>O(n^2)</math> समय
+* [[करात्सुबा एल्गोरिदम]], n-अंकीय पूर्णांकों को गुणा करने के लिए <math>O(n^{\log_2 3})</math> के अतिरिक्त <math>O(n^2)</math> समय
-** एक समान गुणन एल्गोरिथ्म#Complex_number_multiplication 4 के बजाय 3 वास्तविक गुणन का उपयोग करके दो जटिल संख्याओं को गुणा करता है
+** समान गुणन एल्गोरिथ्म 4 के अतिरिक्त 3 वास्तविक गुणन का उपयोग करके दो समिष्ट संख्याओं को गुणा करता है।
-* टूम-कुक गुणन|टूम-कुक एल्गोरिदम, करात्सुबा एल्गोरिदम का एक तेज़ सामान्यीकरण जो एक समय में 2 से अधिक ब्लॉकों में पुनरावर्ती विभाजन और जीत अपघटन की अनुमति देता है
+* टूम-कुक एल्गोरिदम, करात्सुबा एल्गोरिदम का तीव्र सामान्यीकरण जो एक समय में 2 से अधिक ब्लॉकों में पुनरावर्ती विभाजन और जीत अपघटन की अनुमति देता है।
 == संदर्भ ==
@@ Line 236: / Line 229: @@
 * [[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.&nbsp;735&ndash;741.
 *{{cite book |first=Donald |last=Knuth |title=The Art of Computer Programming, Seminumerical Algorithms |volume=II |edition=3rd |publisher=Addison-Wesley |year=1997 |isbn=0-201-89684-2}}
 ==बाहरी संबंध==
 *{{MathWorld|urlname=StrassenFormulas|title=Strassen's Formulas}} (also includes formulas for fast [[matrix inversion]])
 *Tyler J. Earnest, ''[https://web.archive.org/web/20100612150812/http://www.mc2.umbc.edu/docs/earnest.pdf Strassen's Algorithm on the Cell Broadband Engine]''
-{{Numerical linear algebra}}
+[[Category:Collapse templates]]
-[[Category: मैट्रिक्स गुणन एल्गोरिदम]] [[Category: फूट डालो और जीतो एल्गोरिदम]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 19/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:फूट डालो और जीतो एल्गोरिदम]]
+[[Category:मैट्रिक्स गुणन एल्गोरिदम]]

Anonymous

Search

स्ट्रैसेन एल्गोरिदम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 13:17, 1 November 2023

Contents

इतिहास

एल्गोरिथम

विनोग्राड रूप

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

श्रेणी या द्विरेखीय समिष्टता

कैश व्यवहार

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

स्ट्रैसेन एल्गोरिदम: Difference between revisions

Latest revision as of 13:17, 1 November 2023

इतिहास

एल्गोरिथम

विनोग्राड रूप

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

श्रेणी या द्विरेखीय समिष्टता

कैश व्यवहार

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories