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

Revision as of 19:20, 22 July 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}}$ जहां यू = (सी - ए) (सी - डी), वी = (सी + डी) (सी - ए), डब्ल्यू = एए + (सी + डी - ए) (ए + डी - सी)। इससे आव्यूहजोड़ और घटाव की संख्या 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 में मानचित्र सम्मिलित होते हैं, (अर्थात इस मामले में सभी प्रविष्टियों का योग होता है) हैडामर्ड उत्पाद (मैट्रिसेस)।)

	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$ ).^[8]^: 13

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

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

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

स्केलर की सीमा तक स्ट्रैसन एल्गोरिदम का उपयोग करना आवश्यक या वांछनीय नहीं है। पारंपरिक आव्यूहगुणन की तुलना में, एल्गोरिथ्म काफी कुछ जोड़ता है $O(n^{2})$ जोड़/घटाव में कार्यभार; इसलिए निश्चित आकार से नीचे, पारंपरिक गुणन का उपयोग करना बेहतर होगा। इस प्रकार, उदाहरण के लिए, ए $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-ऑर्डर (वक्र)|Z-ऑर्डर आव्यूहप्रतिनिधित्व
करात्सुबा एल्गोरिदम, एन-अंकीय पूर्णांकों को गुणा करने के लिए $O(n^{\log _{2}3})$ $O(n^{\log _{2}3})$ के अतिरिक्त अंदर $O(n^{2})$ $O(n^{2})$ समय
- समान गुणन एल्गोरिथ्म#Complex_number_multiplication 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 2: / Line 2: @@
 {{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 का योग बाईं ओर पूर्ण आव्यूहगुणन के समान परिणाम देता है।<!-- 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>, दो की घात के आकार वाले आव्यूहप्राप्त करने के लिए लुप्त पंक्तियों और स्तंभों को शून्य से भरा जा सकता है - चूँकि एल्गोरिथ्म के वास्तविक कार्यान्वयन व्यवहार में ऐसा नहीं करते हैं।
-स्ट्रैसेन एल्गोरिथम विभाजन <math>A</math>, <math>B</math> और <math>C</math> समान आकार के [[ब्लॉक मैट्रिक्स]] में
+स्ट्रैसेन एल्गोरिथम विभाजन <math>A</math>, <math>B</math> और <math>C</math> समान आकार के [[ब्लॉक मैट्रिक्स|ब्लॉक]] आव्यूहमें
 :<math>
 A =
@@ Line 45: / Line 45: @@
 \end{bmatrix}.
 </math>
-यह निर्माण गुणन की संख्या को कम नहीं करता है: गणना के लिए मैट्रिक्स ब्लॉक के 8 गुणन की अभी भी आवश्यकता है <math>C_{ij}</math> मैट्रिक्स, मानक मैट्रिक्स गुणन का उपयोग करते समय समान संख्या में गुणन की आवश्यकता होती है।
+यह निर्माण गुणन की संख्या को कम नहीं करता है: गणना के लिए आव्यूहब्लॉक के 8 गुणन की अभी भी आवश्यकता है <math>C_{ij}</math> मैट्रिक्स, मानक आव्यूहगुणन का उपयोग करते समय समान संख्या में गुणन की आवश्यकता होती है।
-स्ट्रैसेन एल्गोरिथ्म इसके बजाय नए मैट्रिक्स को परिभाषित करता है:
+स्ट्रैसेन एल्गोरिथ्म इसके अतिरिक्त नए आव्यूहको परिभाषित करता है:
 : <math>
@@ Line 60: / Line 60: @@
 \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 75: @@
 \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 97: / Line 97: @@
 \end{bmatrix}
 </math>
-जहां यू = (सी - ए) (सी - डी), वी = (सी + डी) (सी - ए), डब्ल्यू = एए + (सी + डी - ए) (ए + डी - सी)। इससे मैट्रिक्स जोड़ और घटाव की संख्या 18 से घटकर 15 हो जाती है। मैट्रिक्स गुणन की संख्या अभी भी 7 है, और स्पर्शोन्मुख जटिलता समान है।{{sfnp|Knuth|1997|p=500}}
+जहां यू = (सी - ए) (सी - डी), वी = (सी + डी) (सी - ए), डब्ल्यू = एए + (सी + डी - ए) (ए + डी - सी)। इससे आव्यूहजोड़ और घटाव की संख्या 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> जोड़ या गुणन संक्रियाएँ)।
+उपरोक्त एल्गोरिदम की रूपरेखा से पता चला है कि आव्यूहके उप-ब्लॉकों के लिए पारंपरिक 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>.
+फिर सवाल यह है कि स्ट्रैसेन के एल्गोरिदम के लिए वास्तव में कितने ऑपरेशनों की आवश्यकता होती है, और इसकी तुलना मानक आव्यूहगुणन से कैसे की जाती है जो लगभग लेता है <math>2 N^3</math> (कहाँ <math>N = 2^n</math>) अंकगणितीय संक्रियाएं, अर्थात  स्पर्शोन्मुख जटिलता <math>\Theta (N^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>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> इतना बड़ा है कि एल्गोरिथ्म का उपयोग आम तौर पर व्यवहार में आने वाले मैट्रिक्स पर नहीं किया जाता है।
+स्ट्रैसेन के एल्गोरिदम की तुलना आव्यूहगुणन करने के सरल तरीके से करने की आवश्यकता है जिसके लिए उप-ब्लॉक के 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
@@ Line 193: / Line 193: @@
 |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>-वें टेंसर पावर-दिखाए गए एल्गोरिदम में पुनरावर्ती चरण द्वारा महसूस किया जाता है।)
 ===कैश व्यवहार===
@@ Line 202: / Line 202: @@
 == कार्यान्वयन संबंधी विचार ==
-उपरोक्त विवरण में कहा गया है कि मैट्रिक्स वर्गाकार हैं, और आकार दो की घात है, और यदि आवश्यक हो तो पैडिंग का उपयोग किया जाना चाहिए। यह प्रतिबंध अदिश गुणन की सीमा तक पहुंचने तक मैट्रिक्स को पुनरावर्ती रूप से आधे में विभाजित करने की अनुमति देता है। प्रतिबंध स्पष्टीकरण और जटिलता के विश्लेषण को सरल बनाता है, लेकिन वास्तव में यह आवश्यक नहीं है;<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> फिर मैट्रिक्स और पारंपरिक गुणन का उपयोग उस स्तर पर किया जा सकता है।
+* स्केलर की सीमा तक स्ट्रैसन एल्गोरिदम का उपयोग करना आवश्यक या वांछनीय नहीं है। पारंपरिक आव्यूहगुणन की तुलना में, एल्गोरिथ्म काफी कुछ जोड़ता है <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>.
+* यह विधि वास्तव में किसी भी आयाम के वर्ग आव्यूहों पर लागू की जा सकती है।<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>,  उदाहरण के लिए:
 * आकार का  उत्पाद <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>
 == यह भी देखें ==
@@ Line 223: / Line 223: @@
 * गॉस-जॉर्डन उन्मूलन
 * कॉपरस्मिथ-विनोग्राड एल्गोरिथम
-* Z-ऑर्डर (वक्र)|Z-ऑर्डर मैट्रिक्स प्रतिनिधित्व
+* Z-ऑर्डर (वक्र)|Z-ऑर्डर आव्यूहप्रतिनिधित्व
-* [[करात्सुबा एल्गोरिदम]], एन-अंकीय पूर्णांकों को गुणा करने के लिए <math>O(n^{\log_2 3})</math> के बजाय अंदर <math>O(n^2)</math> समय
+* [[करात्सुबा एल्गोरिदम]], एन-अंकीय पूर्णांकों को गुणा करने के लिए <math>O(n^{\log_2 3})</math> के अतिरिक्त अंदर <math>O(n^2)</math> समय
-** समान गुणन एल्गोरिथ्म#Complex_number_multiplication 4 के बजाय 3 वास्तविक गुणन का उपयोग करके दो जटिल संख्याओं को गुणा करता है
+** समान गुणन एल्गोरिथ्म#Complex_number_multiplication 4 के अतिरिक्त 3 वास्तविक गुणन का उपयोग करके दो जटिल संख्याओं को गुणा करता है
 * टूम-कुक गुणन|टूम-कुक एल्गोरिदम, करात्सुबा एल्गोरिदम का  तेज़ सामान्यीकरण जो  समय में 2 से अधिक ब्लॉकों में पुनरावर्ती विभाजन और जीत अपघटन की अनुमति देता है
@@ Line 232: / Line 232: @@
 * [[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]])

v t e Numerical linear algebra
Key concepts	Floating point Numerical stability
Problems	System of linear equations Matrix decompositions Matrix multiplication (algorithms) Matrix splitting Sparse problems
Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing
Software	MATLAB Basic Linear Algebra Subprograms (BLAS) LAPACK Specialized libraries General purpose software

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 19:20, 22 July 2023

Contents

इतिहास

एल्गोरिथम

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

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

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

कैश व्यवहार

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 19:20, 22 July 2023

इतिहास

एल्गोरिथम

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

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

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

कैश व्यवहार

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories