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

Revision as of 18:11, 20 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}}
-रैखिक बीजगणित में, स्ट्रैसेन एल्गोरिदम, जिसका नाम [[वोल्कर स्ट्रैस]]ेन के नाम पर रखा गया है, एक मैट्रिक्स गुणन एल्गोरिदम है। यह बेहतर एसिम्प्टोटिक जटिलता के साथ बड़े मैट्रिक्स के लिए मानक मैट्रिक्स गुणन एल्गोरिदम से तेज़ है, हालांकि छोटे मैट्रिक्स के लिए अनुभवहीन एल्गोरिदम अक्सर बेहतर होता है। स्ट्रैसन एल्गोरिदम अत्यधिक बड़े मैट्रिक्स के लिए [[मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता]] से धीमा है, लेकिन ऐसे [[गैलेक्टिक एल्गोरिदम]] व्यवहार में उपयोगी नहीं हैं, क्योंकि वे व्यावहारिक आकार के मैट्रिक्स के लिए बहुत धीमे हैं। छोटे मैट्रिक्स के लिए और भी तेज़ एल्गोरिदम मौजूद हैं।
+रैखिक बीजगणित में, स्ट्रैसेन एल्गोरिदम, जिसका नाम [[वोल्कर स्ट्रैस]]ेन के नाम पर रखा गया है,  मैट्रिक्स गुणन एल्गोरिदम है। यह बेहतर एसिम्प्टोटिक जटिलता के साथ बड़े मैट्रिक्स के लिए मानक मैट्रिक्स गुणन एल्गोरिदम से तेज़ है, हालांकि छोटे मैट्रिक्स के लिए अनुभवहीन एल्गोरिदम अक्सर बेहतर होता है। स्ट्रैसन एल्गोरिदम अत्यधिक बड़े मैट्रिक्स के लिए [[मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता]] से धीमा है, लेकिन ऐसे [[गैलेक्टिक एल्गोरिदम]] व्यवहार में उपयोगी नहीं हैं, क्योंकि वे व्यावहारिक आकार के मैट्रिक्स के लिए बहुत धीमे हैं। छोटे मैट्रिक्स के लिए और भी तेज़ एल्गोरिदम मौजूद हैं।
 स्ट्रैसन का एल्गोरिदम किसी भी रिंग (गणित) के लिए काम करता है, जैसे कि प्लस/गुणा, लेकिन सभी [[सेमीरिंग्स]] के लिए नहीं, जैसे कि मिन-प्लस मैट्रिक्स गुणन|मिन-प्लस या [[बूलियन बीजगणित]], जहां अनुभवहीन एल्गोरिदम अभी भी काम करता है, और तथाकथित [[कॉम्बिनेटरियल मैट्रिक्स गुणन]]
@@ Line 10: / Line 10: @@
 == एल्गोरिथम ==
-[[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> समान आकार के [[ब्लॉक मैट्रिक्स]] में
@@ 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 77: / Line 77: @@
 हम इस विभाजन प्रक्रिया को तब तक दोहराते रहते हैं जब तक कि उपमात्राएं संख्याओं (रिंग के तत्व) में परिवर्तित न हो जाएं <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."/>
 == विनोग्राड फॉर्म ==
 विनोग्राड द्वारा खोजे गए निम्नलिखित फॉर्म का उपयोग करके मैट्रिक्स परिवर्धन की संख्या को कम करना संभव है:
@@ Line 105: / Line 103: @@
 उपरोक्त एल्गोरिदम की रूपरेखा से पता चला है कि मैट्रिक्स के उप-ब्लॉकों के लिए पारंपरिक 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 195: / 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 201: / Line 199: @@
 :<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>
 और वास्तव में, वर्णित मैट्रिक्स को पैडिंग करने से गणना का समय बढ़ जाएगा और पहली जगह में विधि का उपयोग करके प्राप्त काफी संकीर्ण समय की बचत को आसानी से समाप्त किया जा सकता है।
-एक अच्छा कार्यान्वयन निम्नलिखित का पालन करेगा:
+अच्छा कार्यान्वयन निम्नलिखित का पालन करेगा:
-* स्केलर की सीमा तक स्ट्रैसन एल्गोरिदम का उपयोग करना आवश्यक या वांछनीय नहीं है। पारंपरिक मैट्रिक्स गुणन की तुलना में, एल्गोरिथ्म काफी कुछ जोड़ता है <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>[2N \times N] \ast [N \times 10N]</math> 20 अलग-अलग के रूप में किया जा सकता है <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> संचालन, परिणाम बनाने के लिए संक्षेपित।
+* आकार का  उत्पाद <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>
 == यह भी देखें ==
@@ Line 229: / Line 225: @@
 * Z-ऑर्डर (वक्र)|Z-ऑर्डर मैट्रिक्स प्रतिनिधित्व
 * [[करात्सुबा एल्गोरिदम]], एन-अंकीय पूर्णांकों को गुणा करने के लिए <math>O(n^{\log_2 3})</math> के बजाय अंदर <math>O(n^2)</math> समय
-** एक समान गुणन एल्गोरिथ्म#Complex_number_multiplication 4 के बजाय 3 वास्तविक गुणन का उपयोग करके दो जटिल संख्याओं को गुणा करता है
+** समान गुणन एल्गोरिथ्म#Complex_number_multiplication 4 के बजाय 3 वास्तविक गुणन का उपयोग करके दो जटिल संख्याओं को गुणा करता है
-* टूम-कुक गुणन|टूम-कुक एल्गोरिदम, करात्सुबा एल्गोरिदम का एक तेज़ सामान्यीकरण जो एक समय में 2 से अधिक ब्लॉकों में पुनरावर्ती विभाजन और जीत अपघटन की अनुमति देता है
+* टूम-कुक गुणन|टूम-कुक एल्गोरिदम, करात्सुबा एल्गोरिदम का  तेज़ सामान्यीकरण जो  समय में 2 से अधिक ब्लॉकों में पुनरावर्ती विभाजन और जीत अपघटन की अनुमति देता है
 == संदर्भ ==

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 18:11, 20 July 2023

Contents

इतिहास

एल्गोरिथम

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

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

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

कैश व्यवहार

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 18:11, 20 July 2023

इतिहास

एल्गोरिथम

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

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

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

कैश व्यवहार

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories