आव्यूह गुणन कलनविधि (एल्गोरिथ्म): Difference between revisions

Latest revision as of 09:56, 23 August 2023

आव्यूह गुणन कई संख्यात्मक कलनविधि में एक केंद्रीय संक्रिया है, जबकि कलनविधि में आव्यूह गुणन को प्रवीण बनाने में बहुत काम किया गया है। इस प्रकार अभिकलनात्मक समस्याओं में आव्यूह गुणन के अनुप्रयोग वैज्ञानिक अभिकलन और पैटर्न रिकॉग्नाइजेसन सहित कई क्षेत्रों में संभवतः प्रतीत होने वाली असंबंधित समस्याओं के रूप में पाए जाते हैं और आलेख के माध्यम से पथों की गिनती होती है।^[1] समानांतर अभिकलन और वितरित अभिकलन प्रणाली सहित विभिन्न प्रकार के हार्डवेयर पर आव्यूह को गुणा करने के लिए कई भिन्न -भिन्न कलनविधि के रूप में डिज़ाइन किया जाता है , जहां अभिकलनात्मक कार्य कई प्रोसेसर पर संभवतः एक नेटवर्क के रूप में फैला हुआ है।

आव्यूह गुणन की गणितीय परिभाषा को सीधे प्रयुक्त करने से एक कलनविधि मिलता है, जिसके $n 3$ क्रम पर कलनविधि का विश्लेषण होता है और इस प्रकार दो को गुणा करने के लिए (गणित क्षेत्र) संक्रिया $n \times n$ उस क्षेत्र पर आव्यूह ( $Θ(n 3)$ बड़े O नोटेशन के रूप में होता है। 1960 के दशक में स्ट्रैसेन कलनविधि के बाद से आव्यूह को गुणा करने के लिए आवश्यक समय पर अच्छे ऐसिम्टाटिक सीमाएं ज्ञात हैं, लेकिन इष्टतम समय अर्थात आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता अज्ञात बनी हुई है। और इस प्रकार अक्टूबर 2022 तक आव्यूह गुणन कलनविधि की समय सम्मिश्रता पर सबसे अच्छी घोषणा $O(n 2.37188)$ की गई थी, जिसे डुआन, वू और झोउ द्वारा दिया गया था^[2] एक प्रीप्रिंट में घोषणा की गई है। इससे सीमा में सुधार होता है $O(n 2.3728596)$ समय, जोश अल्मन और वर्जीनिया वासिलिव्स्का विलियम्स द्वारा दिया गया।^[3]^[4] चूंकि, यह कलनविधि बड़े स्थिरांक के कारण एक गैलेक्टिक कलनविधि के रूप में होती है और इसे व्यावहारिक रूप से अनुभव नहीं किया जा सकता है।

पुनरावृत्तीय कलनविधि

आव्यूह गुणान परिभाषा यह है कि यदि $C = AB$ एक के लिए $n \times m$ आव्यूह $A$ और एक $m \times p$ आव्यूह $B$ , तब $C$ एक $n \times p$ प्रविष्टियों के साथ आव्यूह के रूप में होता है,

c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}.

इससे, एक सरल कलनविधि का निर्माण किया जा सकता है जो सूचकांकों पर लूप करता है $i$ 1 से लेकर $n$ और $j$ 1 से लेकर $p$ , नेस्टेड लूप का उप समेशन करके उपरोक्त की गणना की जा सकती है

Input: matrices $A$ and $B$
Let $C$ be a new matrix of the appropriate size
For i 1 to n:
- Forj 1 top:
  - Let sum $sum = 0$
  - For k 1 tom:
    - Set sum $sum \leftarrow sum + A ik \times B kj$
  - Set Cij $C ij \leftarrow sum$
Return $C$

यह कलनविधि ऐसिम्टाटिक नोटेशन में समय $Θ(nmp)$ लेता है।^[1] इस प्रकार कलनविधि के विश्लेषण के उद्देश्य से एक सामान्य सरलीकरण यह मान लेता है कि इनपुट सभी आकार $n \times n$ के वर्ग आव्यूह होते है, जिस स्थिति में रनिंग समय $Θ(n 3)$ , के रूप में अर्थात आयाम के आकार में घन होता है।^[5]

कैशे व्यवहार

पंक्ति और स्तंभ-प्रमुख क्रम का चित्रण

पुनरावृत्तीय आव्यूह गुणन में तीन लूपों को शुद्धता या ऐसिम्टाटिक रनिंग टाइम पर प्रभाव के बिना एक दूसरे के साथ यादृच्छिक प्रकार से स्वैप किया जाता है। चूंकि, मेमोरी एक्सेस पैटर्न और कलनविधि के सीपीयू कैशे उप समेशन के कारण व्यावहारिक ऑर्डर प्रदर्शन पर बहुत प्रभाव डालता है;^[1] और इस प्रकार कौन सा क्रम सबसे अच्छा है यह इस बात पर भी निर्भर करता है कि क्या आव्यूह पंक्ति और स्तंभ प्रमुख का क्रम संग्रहीत हैं या दोनों के मिश्रण में संग्रहीत हैं।

विशेष रूप से, पूरी तरह से संबंधित कैश के आदर्श स्थिति में जिसमें $M$ बाइट्स और $b$ बाइट्स प्रति कैशे लाइन के रूप में सम्मलित होता है। (यदि M/b कैशे लाइनें), उपरोक्त कलनविधि इसके लिए सब-इष्टतम है $A$ और $B$ पंक्ति-प्रमुख क्रम में संग्रहीत होते है जब $n > M / b$ , आंतरिक लूप का प्रत्येक पुनरावृत्ति एक पंक्ति के माध्यम से एक साथ स्वीप होते है। इस प्रकार $A$ का एक कॉलम $B$ के किसी तत्व तक पहुंचने पर कैशे मिस $B$ .हो जाता है इसका अर्थ यह है कि कलनविधि $Θ(n 3)$ के रूप में प्रयुक्त होता है और सबसे खराब स्थिति में कैशे छूट जाता है। वर्ष 2010 तक, प्रोसेसर की तुलना में मेमोरी की गति ऐसी होती है कि वास्तविक गणना के अतिरिक्त कैशे मिस हो जाता है, जो बड़े आकार के आव्यूह के लिए रनिंग समय पर प्रभावी हो जाता है।^[6]

पंक्ति-प्रमुख लेआउट में $A$ और $B$ के लिए पुनरावृत्तीय कलनविधि का इष्टतम संस्करण एक लूप टाइलिंग संस्करण है, जहां आव्यूह को आकार $\sqrt M$ द्वारा $\sqrt M$ के वर्गाकार टाइलों में विभाजित किया गया है,:^[6]^[7]

इनपुट: मैट्रिसेस $A$ और $B$
होने देना $C$ उचित आकार का एक नया मैट्रिक्स बनें
टाइल का आकार चुनें $T = Θ(\sqrt M)$
के लिए I 1 से n के चरणों में T:
- के लिए J 1 से p के चरणों में T:
  - के लिए K 1 से m के चरणों में T:
    - गुणा करो $A I : I + T, K : K + T$ और $B K : K + T, J : J + T$ में $C I : I + T, J : J + T$ , वह है:
    - के लिए i से I को min(I + T, n):
      - के लिए $j$ से $J$ को $min(J + T, p)$ :
        होने देना $sum = 0$
        
        के लिए $k$ से $K$ को $min(K + T, m)$ :
        तय करना $sum \leftarrow sum + A ik \times B kj$
        
        तय करना $C ij \leftarrow C ij + sum$
वापस करना $C$

आदर्शीकृत कैशे मॉडल में, यह कलनविधि केवल $Θ(n 3 / b \sqrt M)$ कैशे को प्रयुक्त करता है, जो आधुनिक मशीनों पर परिमाण के कई आदेशों तक भाजक $b \sqrt M$ मात्रा को मिस करता है,, जिससे कि कैशे मिस होने के अतिरिक्त वास्तविक गणना रनिंग समय पर प्रभावी हो जाते है।^[6]

डिवाइड और क्न्क्वेर कलनविधि

पुनरावृत्तीय कलनविधि का एक विकल्प आव्यूह गुणन के लिए डिवाइड और क्न्क्वेर कलनविधि है। यह ब्लॉक आव्यूह पर निर्भर करता है

C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}},

जो सभी वर्ग आव्यूहों के लिए काम करता है जिनके आयाम की दो घात हैं, अर्थात आकार $2 n \times 2 n$ के रूप में है और कुछ के लिए $n$ . आव्यूह गुणन के रूप में होता है,

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}}={\begin{pmatrix}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{pmatrix}}

जिसमें उपमैट्रिस के युग्मों के आठ गुणन होते हैं, जिसके बाद एक अतिरिक्त चरण होता है। इस प्रकार डिवाइड और क्न्क्वेर कलनविधि अदिश गुणन का उप समेशन करके छोटे गुणन प्रत्यावर्तन की गणना करता है $c 11 = a 11 b 11$ इसके आधार स्थिति के रूप में है।

फलन के रूप में इस कलनविधि की सम्मिश्रता $n$ पुनरावृत्ति द्वारा दिया जाता है^[5]

T(1)=\Theta (1);

T(n)=8T(n/2)+\Theta (n^{2}),

आकार के आव्यूह पर आठ रिकर्सिव कॉलों के लिए लेखांकन $n /2$ और $Θ(n 2)$ परिणामी आव्यूहों के चार युग्मों का तत्व-वार समेशन होता है। मास्टर प्रमेय का अनुप्र समेशन कलनविधि का विश्लेषण डिवाइड और क्न्क्वेर पुनरावृत्ति के लिए मास्टर प्रमेय इस पुनरावृत्ति को समाधान के लिए $Θ(n 3)$ पुनरावृत्तीय कलनविधि के समान दिखाता है,^[5]

गैर-वर्ग आव्यूह

इस कलनविधि का एक प्रकार जो यादृच्छिक आकार के आव्यूह के लिए काम करता है और व्यवहार में फ़ास्ट होता है^[6]आव्यूह को चार उपमैट्रिस में विभाजित करता है।^[8] इस प्रकार आव्यूह को विभाजित करने का अर्थ अब इसे समान आकार के दो भागों में विभाजित करना है या विषम आयामों की स्थिती में जितना संभव हो सके समान आकार के निकट विभाजित करता है।

इनपुट: मैट्रिसेस $A$ आकार का $n \times m$ , $B$ आकार का $m \times p$ .
आधार मामला: यदि $max(n, m, p)$ कुछ सीमा से नीचे है, पुनरावृत्त एल्गोरिदम के लूप का खुलना संस्करण का उपयोग करें।
पुनरावर्ती मामले:

अगर $max(n, m, p) = n$ , विभाजित करना $A$ क्षैतिज रूप से:

C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}

अन्यथा, यदि $max(n, m, p) = p$ , विभाजित करना $B$ लंबवत:

C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}

अन्यथा, $max(n, m, p) = m$ . विभाजित करना $A$ लंबवत और $B$ क्षैतिज रूप से:

C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2}

कैशे व्यवहार

रिकर्सिव आव्यूह गुणन की कैशे मिस दर लूप टाइलिंग पुनरावृत्तीय संस्करण के समान है, लेकिन उस कलनविधि के विपरीत, रिकर्सिव कलनविधि कैशे -विस्मृत कलनविधि है|कैशे -ओब्लिवियस:^[8]इष्टतम कैशे प्रदर्शन प्राप्त करने के लिए कोई ट्यूनिंग पैरामीटर आवश्यक नहीं है, और यह बहु क्रमादेशन वातावरण में अच्छा व्यवहार करता है जहां कैशे स्थान लेने वाली अन्य प्रक्रियाओं के कारण कैशे आकार प्रभावी रूप से गतिशील होते हैं।^[6](सरल पुनरावृत्तीय कलनविधि कैशे -विस्मृत भी है, लेकिन यदि आव्यूह लेआउट कलनविधि के लिए अनुकूलित नहीं है तो व्यवहार में बहुत धीमा है।)

इस कलनविधि द्वारा किसी मशीन पर कैशे मिस होने की संख्या $M$ आदर्श कैशे की पंक्तियाँ, प्रत्येक आकार की $b$ बाइट्स, से घिरा है^[8]^: 13

\Theta \left(m+n+p+{\frac {mn+np+mp}{b}}+{\frac {mnp}{b{\sqrt {M}}}}\right)

उप-घन कलन विधि

घातांक के अनुमानों में सुधार

ω

आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता के लिए समय के साथ

O(n^{\omega })

.

ऐसे कलनविधि उपस्थित हैं जो सीधे चलने वाले कलनविधि की तुलना में अच्छे चलने का समय प्रदान करते हैं। सबसे पहले खोजी गई स्ट्रैसेन कलनविधि थी, जिसे 1969 में वोल्कर स्ट्रैसन द्वारा तैयार किया गया था और इसे अधिकांशतः फास्ट आव्यूह गुणन के रूप में जाना जाता है। यह दो $2 \times 2$ -आव्यूह को गुणा करने की विधि पर आधारित है, जिसमें कई अतिरिक्त जोड़ और घटाव संचालन की कीमत पर केवल 7 गुणन सामान्य 8 के अतिरिक्त की आवश्यकता होती है। इसे रिकर्सिव रूप से प्रयुक्त करने से गुणात्मक लागत वाला एक कलनविधि प्राप्त होता है $O(n^{\log _{2}7})\approx O(n^{2.807})$ . स्ट्रैसेन का कलनविधि अधिक सम्मिश्र है और अनुभवहीन कलनविधि की तुलना में संख्यात्मक स्थिरता कम हो गई है,^[9] लेकिन ऐसे स्थितियों में यह $n > 100$ फ़ास्ट है^[1] यह कई पुस्तकालयों में दिखाई देता है, जैसे कि BLAS (बुनियादी रैखिक बीजगणित सबप्रोग्राम )^[10] यह परिमित क्षेत्र जैसे सटीक डोमेन पर बड़े आव्यूह के लिए बहुत उप समेशन ी है, जहां संख्यात्मक स्थिरता समस्या नहीं है।

सैद्धांतिक कंप्यूटर विज्ञान में यह एक खुला प्रश्न है कि समय सम्मिश्रता के संदर्भ में स्ट्रैसेन के कलनविधि को कितनी अच्छी तरह सुधारा जा सकता है। आव्यूह गुणन घातांक, सामान्यतः $\omega$ द्वारा निरूपित किया जाता है वह सबसे छोटी वास्तविक संख्या है जिसके लिए कोई भी $n\times n$ किसी क्षेत्र पर $n^{\omega +o(1)}$ क्षेत्र संक्रिया का उप समेशन करके एक साथ गुणा किया जा सकता है इस प्रकार x $\omega$ पर उपस्थित सर्वश्रेष्ठ बाउंड जोश अल्मन और वर्जीनिया वासिलिव्स्का विलियम्स द्वारा $\omega <2.3728596$ है।^[3] यह कलन विधि , अनुसंधान की इस पंक्ति में अन्य सभी वर्तमान कलनविधि की तरह कॉपरस्मिथ-विनोग्राड कलनविधि का एक सामान्यीकरण है, जो 1990 में डॉन कॉपरस्मिथ और शमूएल विनोग्राड द्वारा दिया गया था।^[11] इन कलनविधि का वैचारिक विचार स्ट्रैसेन के कलनविधि के समान है और दो $k \times k$ आव्यूह को $k 3$ से कम गुणन के साथ गुणा करने का एक तरीका तैयार किया गया है और इस प्रोद् समेशन िकीय को पुनरावर्ती के रूप से प्रयुक्त किया जाता है। चूंकि, बिग o नोटेशन द्वारा छिपा हुआ निरंतर गुणांक इतना बड़ा है कि ये कलनविधि केवल उन आव्यूह के लिए उपयुक्त हैं जो वर्तमान कंप्यूटरों पर संभालने के लिए बहुत बड़े हैं।^[12]^[13]

फ़्रीवाल्ड्स का कलनविधि एक सरल मोंटे कार्लो कलनविधि है, जो आव्यूह $A$ , $B$ और $C$ , दिए जाने पर $Θ(n 2)$ समय में सत्यापित करता है यदि $AB = C$ है

अल्फा टेन्सर

2022 में, डीपमाइंड ने अल्फ़ाटेनसर न्यूरल नेटवर्क प्रस्तुत किया है, जिसने हजारों आव्यूह गुणन कलनविधि का आविष्कार करने के लिए एकल-प्लेयर गेम सादृश्य का उप समेशन किया, जिनमें से कुछ पहले मनुष्यों द्वारा खोजे गए थे और कुछ जो नहीं थे।^[14] संचालन गैर-कम्यूटेटिव ग्राउंड क्षेत्र सामान्य अंकगणित और $\mathbb {Z} /2\mathbb {Z}$ परिमित क्षेत्र मॉड 2 अंकगणित तक ही सीमित थे,। इस प्रकार सबसे अच्छा व्यावहारिक आव्यूह गुणन टेंसर का स्पष्ट निम्न-रैंक अपघटन कलनविधि O(n^2.778) के रूप में पाया गया था ^[15] ऐसे टेंसर और उससे आगे के निम्न-श्रेणी के अपघटन का पता लगाना NP कठिन है; इस प्रकार 3x3 आव्यूह के लिए भी इष्टतम गुणन आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता क्रमविनिमेय क्षेत्र में भी गुणन की संख्या को न्यूनतम करना।^[15] इस प्रकार 4x4 आव्यूह पर, अल्फ़ाटेन्सर ने अप्रत्याशित रूप से 47 गुणन चरणों के साथ एक समाधान खोजा था, जो 1969 के स्ट्रैसेन के कलनविधि के साथ आवश्यक 49 से अधिक सुधार हुआ था, चूंकि मॉड 2 अंकगणित तक सीमित था। इसी तरह, अल्फ़ाटेन्सर ने स्ट्रैसेन के 98 चरणों के अतिरिक्त 96 के साथ 5x5 आव्यूह को हल किया गया था । आश्चर्यजनक खोज के आधार पर कि इस तरह के सुधार उपस्थित हैं, अन्य शोधकर्ता तुरंत एक समान स्वतंत्र 4x4 कलनविधि ढूंढने में सक्षम थे और भिन्न से डीपमाइंड के 96-चरण 5x5 कलनविधि को मॉड 2 अंकगणित में 95 चरणों तक और 97 तक छोटा कर दिया था।^[16] सामान्य अंकगणित में.^[17] कुछ कलनविधि पहले कभी नहीं खोजे गए थे, उदाहरण (4, 5, 5) सामान्य और मॉड 2 अंकगणित में 80 से सुधरकर 76 हो गया था।

समानांतर और वितरित कलन विधि

साझा-मेमोरी समानता

डिवाइड और क्न्क्वेर कलनविधि डिवाइड पहले से स्केच किया गया है और इस प्रकार साझा-मेमोरी मल्टीप्रोसेसर के लिए दो विधी के रूप में समानांतर कलनविधि के रूप में हो सकता है। ये इस तथ्य पर आधारित होता हैं कि आठ रिकर्सिव आव्यूह गुणन में इस प्रकार है

{\begin{pmatrix}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{pmatrix}}

चार समेशन की तरह, एक-दूसरे से स्वतंत्र रूप से निष्पादित किया जाता है, चूंकि कलनविधि को समेशन करने से पहले गुणन को जोड़ने की आवश्यकता होती है। इस प्रकार समस्या की पूर्ण समानता का उप समेशन करते हुए कलनविधि प्राप्त होता है जिसे फोर्क-जॉइन मॉडल पीसूडोकोड में व्यक्त किया जा सकता है:^[18]

प्रक्रिया $multiply(C, A, B)$ :

आधार मामला: यदि $n = 1$ , तय करना $c 11 \leftarrow a 11 \times b 11$ (या एक छोटे ब्लॉक मैट्रिक्स को गुणा करें)।
अन्यथा, एक नए मैट्रिक्स के लिए स्थान आवंटित करें T आकार का n × n, तब:
- विभाजन $A$ में $A 11$ , $A 12$ , $A 21$ , $A 22$ .
- विभाजन $B$ में $B 11$ , $B 12$ , $B 21$ , $B 22$ .
- विभाजन $C$ में $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- विभाजन $T$ में $T 11$ , $T 12$ , $T 21$ , $T 22$ .
- समानांतर निष्पादन:
  - काँटा $multiply(C 11, A 11, B 11)$ .
  - काँटा $multiply(C 12, A 11, B 12)$ .
  - काँटा $multiply(C 21, A 21, B 11)$ .
  - काँटा $multiply(C 22, A 21, B 12)$ .
  - काँटा $multiply(T 11, A 12, B 21)$ .
  - काँटा $multiply(T 12, A 12, B 22)$ .
  - काँटा $multiply(T 21, A 22, B 21)$ .
  - काँटा $multiply(T 22, A 22, B 22)$ .
- जुड़ें (समानांतर कांटे के पूरा होने तक प्रतीक्षा करें)।
- $add(C, T)$ .
- आवंटन रद्द करें $T$ .

प्रक्रिया $add(C, T)$ जोड़ता है $T$ में $C$ , तत्व अनुसार:

आधार मामला: यदि $n = 1$ , तय करना $c 11 \leftarrow c 11 + t 11$ (या एक छोटा लूप बनाएं, शायद अनियंत्रित)।
अन्यथा:
- विभाजन $C$ में $C 11$ , $C 12$ , $C 21$ , $C 22$ .
- विभाजन $T$ में $T 11$ , $T 12$ , $T 21$ , $T 22$ .
- समानांतर में:
  - काँटा $add(C 11, T 11)$ .
  - काँटा $add(C 12, T 12)$ .
  - काँटा $add(C 21, T 21)$ .
  - काँटा $add(C 22, T 22)$ .
- जोड़ना।

यहां, फोर्क एक कीवर्ड है जो संकेत देता है कि गणना को शेष फलन कॉल के साथ समानांतर में चलाया जा सकता है, जबकि जॉइन पहले से फोर्क की गई सभी गणनाओं के पूरा होने की प्रतीक्षा करता है। विभाजन केवल सूचक हेरफेर द्वारा अपना लक्ष्य प्राप्त करता है।

इस कलनविधि में $Θ(log 2 n)$ चरण एक महत्वपूर्ण पथ लंबाई है, जिसका अर्थ है कि अनंत संख्या में प्रोसेसर वाली एक आदर्श मशीन पर इतना समय लगता है; इसलिए, किसी भी वास्तविक कंप्यूटर पर इसकी अधिकतम संभव गति $Θ(n 3 /log 2 n)$ है, अस्थायी आव्यूह $T$ से डेटा ले जाने में निहित संचार लागत के कारण कलनविधि व्यावहारिक नहीं है, लेकिन एक अधिक व्यावहारिक संस्करण अस्थायी आव्यूह का उप समेशन किए बिना $Θ(n 2)$ स्पीडअप प्राप्त करता है।^[18]

ब्लॉक आव्यूह गुणन. 2D कलनविधि में, प्रत्येक प्रोसेसर एक सबआव्यूह के लिए उत्तरदायी होता है

C

. 3D कलनविधि में, सबआव्यूह की प्रत्येक जोड़ी

A

और

B

जिसे गुणा किया जाता है उसे एक प्रोसेसर को सौंपा जाता है।

संचार अवॉयड और डिस्ट्रिब्यूटेड कलन विधि

आधुनिक आर्किटेक्चर में हाइरार्की मेमोरी के साथ इनपुट आव्यूह तत्वों को लोड करने और संग्रहीत करने की लागत अंकगणित की लागत पर प्रभाव डालती है और इस प्रकार एक ही मशीन पर यह रैम और कैशे के बीच स्थानांतरित किए गए डेटा की मात्रा के रूप में होती है, जबकि एक डिस्ट्रिब्यूटेड मेमोरी मल्टी-नोड मशीन पर यह नोड्स के बीच स्थानांतरित की गई राशि के रूप में होती है और किसी भी स्थिति में इसे संचार बैंडविड्थ कहा जाता है। तीन नेस्टेड लूप का उप समेशन करने वाला अनुभवहीन कलनविधि $Ω(n 3)$ संचार बैंडविड्थ.का उप समेशन करता है

कैनन का कलन विधि , जिसे 2D कलनविधि के रूप में भी जाना जाता है, एक संचार से अवॉयड कलनविधि जो प्रत्येक इनपुट आव्यूह को एक ब्लॉक आव्यूह में विभाजित करता है जिसके तत्व के आकार $\sqrt M /3$ द्वारा $\sqrt M /3$ के रूप में सबआव्यूह होते हैं जहाँ $M$ फ़ास्ट ी से मेमोरी का आकार है।^[19] इसके बाद अनुभवहीन कलनविधि का उप समेशन ब्लॉक मैट्रिसेस पर किया जाता है, जो पूरी तरह से फ़ास्ट मेमोरी में सबमैट्रिसेस के गुणन की गणना करता है। इससे संचार बैंडविड्थ को $O (n 3 / \sqrt M)$ तक कम कर देता है, जो असिम्प्टोटिकालीय रूप से इष्टतम है $Ω(n 3)$ है।^[20]^[21]

वितरित सेटिंग में, $\sqrt p$ 2D मेशेस द्वारा $\sqrt p$ में व्यवस्थित P प्रोसेसरों में परिणाम का एक सबआव्यूह प्रत्येक प्रोसेसर को सौंपा जाता है और प्रत्येक $O (n 2 / \sqrt p)$ शब्द प्रोसेसर ट्रांसमिटिंग के साथ गुणन की गणना की जा सकती है जो कि असम्बद्ध रूप से इष्टतम है, यह मानते हुए कि प्रत्येक नोड न्यूनतम $O (n 2 / p)$ तत्वसंग्रहीत करता है.^[21]इसे 3D कलनविधि द्वारा अच्छे से बनाया जा सकता है, जो प्रोसेसर को 3D क्यूब मेशेस में व्यवस्थित करता है और इस प्रकार दो इनपुट सबमैट्रिसेस के प्रत्येक गुणन को एक ही प्रोसेसर को निर्दिष्ट करता है। फिर प्रत्येक पंक्ति पर कमी करके परिणाम सबमैट्रिस के रूप में उत्पन्न किए जाते हैं।^[22] यह कलनविधि प्रति प्रोसेसर $O (n 2 / p 2/3)$ शब्दों को संचारित करता है जो कि असम्बद्ध रूप से इष्टतम है।^[21]चूंकि, इसके लिए प्रत्येक इनपुट आव्यूह तत्व $p 1/3$ बार दोहराने की आवश्यकता होती है और इसलिए इनपुट को संग्रहीत करने के लिए आवश्यकता से अधिक $p 1/3$ मेमोरी की आवश्यकता होती है। इस कलनविधि के रनटाइम को कम करने के लिए स्ट्रैसेन के साथ जोड़ा जा सकता है।^[22] 2.5D कलनविधि मेमोरी उप समेशन और संचार बैंडविड्थ के बीच एक निरंतर ट्रेडऑफ़ प्रदान करता है।^[23] मैप रेडूस जैसे आधुनिक वितरित अभिकलन वातावरण पर, विशेष गुणन कलनविधि विकसित किए गए हैं।^[24]

मेशेस कलन विधि

क्रॉस-वायर्ड मेशेस पर दो n×n आव्यूह के लिए आव्यूह गुणन 2n-1 चरणों में पूरा होता है।

मेशेस नेटवर्किंग पर गुणन के लिए विभिन्न प्रकार के कलनविधि हैं। 2D कैनन के कलनविधि का उप समेशन करके एक मानक द्वि-आयामी मेशेस पर दो n×n के गुणन के लिए कोई 3n-2 चरणों में गुणन को पूरा कर सकता है, चूंकि बार-बार की गणना के लिए यह संख्या आधी हो जाती है।^[25] इस प्रकार मानक सरणी अक्षम है क्योंकि दो आव्यूह से डेटा एक साथ नहीं आता है और इसे शून्य के साथ पैडेड होना चाहिए।

परिणाम दो-परत क्रॉस-वायर्ड मेशेस पर और भी फ़ास्ट ़ है, जहां केवल 2n-1 चरणों की आवश्यकता होती है।^[26] इस प्रकार बार-बार गणना करने पर प्रदर्शन में और सुधार होता है जिससे 100% दक्षता प्राप्त होती है।^[27] और क्रॉस-वायर्ड मेशेस सरणी को गैर-प्लानर (अर्थात बहुपरत) प्रसंस्करण संरचना के एक विशेष स्थिति के रूप में देखा जा सकता है।^[28]

यह भी देखें

गणितीय संक्रिया की अभिकलनात्मक सम्मिश्रता
आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता
CYK कलनविधि § वैलिएंट्स कलनविधि
आव्यूह श्रृंखला गुणन
स्पार्स आव्यूह -सदिश गुणन
चार रूसियों की विधि

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 Skiena, Steven (2008). "Sorting and Searching". एल्गोरिथम डिज़ाइन मैनुअल. Springer. pp. 45–46, 401–3. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
↑ Duan, Ran; Wu, Hongxun; Zhou, Renfei (2022), Faster Matrix Multiplication via Asymmetric Hashing, arXiv:2210.10173
↑ ^3.0 ^3.1 Alman, Josh; Williams, Virginia Vassilevska (2020), "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv:2010.05846
↑ Hartnett, Kevin (23 March 2021). "मैट्रिक्स गुणन इंच पौराणिक लक्ष्य के करीब". Quanta Magazine (in English). Retrieved 2021-04-01.
↑ ^5.0 ^5.1 ^5.2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 75–79. ISBN 0-262-03384-4.
↑ ^6.0 ^6.1 ^6.2 ^6.3 ^6.4 Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 Performance Engineering of Software Systems, Lecture 8". MIT OpenCourseWare. Massachusetts Institute of Technology. Retrieved 27 January 2015.
↑ Lam, Monica S.; Rothberg, Edward E.; Wolf, Michael E. (1991). अवरुद्ध एल्गोरिदम का कैश प्रदर्शन और अनुकूलन. ASPLOS91: 4th Int'l Conference on Architecture Support for Programming Languages & Operating Systems. doi:10.1145/106972.106981. ISBN 978-0-89791-380-5.
↑ ^8.0 ^8.1 ^8.2 Prokop, Harald (1999). कैश-ओब्लिवियस एल्गोरिदम (PDF) (Master's). MIT. hdl:1721.1/80568.
↑ Miller, Webb (1975), "Computational complexity and numerical stability", SIAM News, 4 (2): 97–107, CiteSeerX 10.1.1.148.9947, doi:10.1137/0204009
↑ Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. p. 108. ISBN 978-0-521-88068-8.
↑ Coppersmith, Don; Winograd, Shmuel (1990), "Matrix multiplication via arithmetic progressions" (PDF), Journal of Symbolic Computation, 9 (3): 251, doi:10.1016/S0747-7171(08)80013-2
↑ Iliopoulos, Costas S. (1989), "Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix" (PDF), SIAM Journal on Computing, 18 (4): 658–669, CiteSeerX 10.1.1.531.9309, doi:10.1137/0218045, MR 1004789, archived from the original (PDF) on 2014-03-05, retrieved 2015-01-16, The Coppersmith–Winograd algorithm is not practical, due to the very large hidden constant in the upper bound on the number of multiplications required.
↑ Robinson, Sara (November 2005), "Toward an Optimal Algorithm for Matrix Multiplication" (PDF), SIAM News, 38 (9), Even if someone manages to prove one of the conjectures—thereby demonstrating that $ω = 2$ —the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. [...] the input matrices must be astronomically large for the difference in time to be apparent.
↑ "AlphaTensor के साथ नवीन एल्गोरिदम की खोज". www.deepmind.com (in English). Retrieved 2022-11-01.
↑ ^15.0 ^15.1 Fawzi, Alhussein; Balog, Matej; Huang, Aja; Hubert, Thomas; Romera-Paredes, Bernardino; Barekatain, Mohammadamin; Novikov, Alexander; R. Ruiz, Francisco J.; Schrittwieser, Julian; Swirszcz, Grzegorz; Silver, David; Hassabis, Demis; Kohli, Pushmeet (October 2022). "सुदृढीकरण सीखने के साथ तेज़ मैट्रिक्स गुणन एल्गोरिदम की खोज करना". Nature. 610 (7930): 47–53. Bibcode:2022Natur.610...47F. doi:10.1038/s41586-022-05172-4. ISSN 1476-4687. PMC 9534758. PMID 36198780.
↑ Kauers, Manuel; Moosbauer, Jakob (2022-12-02). "मैट्रिक्स गुणन के लिए फ़्लिप ग्राफ़". arXiv:2212.01175 [cs.SC].
↑ Brubaker, Ben (23 November 2022). "एआई मैट्रिक्स गुणन में नई संभावनाओं को प्रकट करता है". Quanta Magazine (in English). Retrieved 26 November 2022.
↑ ^18.0 ^18.1 Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). Massachusetts Institute of Technology. pp. 54–57. hdl:1721.1/47519.
↑ Cannon, Lynn Elliot (14 July 1969). कलमन फ़िल्टर एल्गोरिथम को लागू करने के लिए एक सेलुलर कंप्यूटर (Ph.D.). Montana State University.
↑ Hong, J. W.; Kung, H. T. (1981). "I/O complexity: The red-blue pebble game" (PDF). STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing: 326–333. doi:10.1145/800076.802486. S2CID 8410593. Archived (PDF) from the original on December 15, 2019.
↑ ^21.0 ^21.1 ^21.2 Irony, Dror; Toledo, Sivan; Tiskin, Alexander (September 2004). "वितरित-मेमोरी मैट्रिक्स गुणन के लिए संचार निचली सीमाएं". J. Parallel Distrib. Comput. 64 (9): 1017–26. CiteSeerX 10.1.1.20.7034. doi:10.1016/j.jpdc.2004.03.021.
↑ ^22.0 ^22.1 Agarwal, R.C.; Balle, S. M.; Gustavson, F. G.; Joshi, M.; Palkar, P. (September 1995). "समानांतर मैट्रिक्स गुणन के लिए एक त्रि-आयामी दृष्टिकोण". IBM J. Res. Dev. 39 (5): 575–582. CiteSeerX 10.1.1.44.3404. doi:10.1147/rd.395.0575.
↑ Solomonik, Edgar; Demmel, James (2011). "Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms" (PDF). Proceedings of the 17th International Conference on Parallel Processing. Vol. Part II. pp. 90–109. doi:10.1007/978-3-642-23397-5_10. ISBN 978-3-642-23397-5.
↑ Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "MapReduce का उपयोग करके आयाम स्वतंत्र मैट्रिक्स स्क्वायर" (PDF). arXiv:1304.1467. Bibcode:2013arXiv1304.1467B. Retrieved 12 July 2014.
↑ Bae, S.E.; Shinn, T.-W.; Takaoka, T. (2014). "जाल सरणी पर मैट्रिक्स गुणन के लिए एक तेज़ समानांतर एल्गोरिदम". Procedia Computer Science. 29: 2230–40. doi:10.1016/j.procs.2014.05.208.
↑ Kak, S (1988). "मैट्रिक्स गुणन के लिए एक दो-परत जाल सरणी". Parallel Computing. 6 (3): 383–5. CiteSeerX 10.1.1.88.8527. doi:10.1016/0167-8191(88)90078-6.
↑ Kak, S. (2014). "क्रॉस-वायर्ड जाल सरणी पर मैट्रिक्स गुणन की दक्षता". arXiv:1411.3273 [cs.DC].
↑ Kak, S (1988). "बहुस्तरीय सरणी कंप्यूटिंग". Information Sciences. 45 (3): 347–365. CiteSeerX 10.1.1.90.4753. doi:10.1016/0020-0255(88)90010-2.

अग्रिम पठन

Buttari, Alfredo; Langou, Julien; Kurzak, Jakub; Dongarra, Jack (2009). "A class of parallel tiled linear algebra algorithms for multicore architectures". Parallel Computing. 35: 38–53. arXiv:0709.1272. doi:10.1016/j.parco.2008.10.002. S2CID 955.
Goto, Kazushige; van de Geijn, Robert A. (2008). "Anatomy of high-performance matrix multiplication". ACM Transactions on Mathematical Software. 34 (3): 1–25. CiteSeerX 10.1.1.140.3583. doi:10.1145/1356052.1356053. S2CID 9359223.
Van Zee, Field G.; van de Geijn, Robert A. (2015). "BLIS: A Framework for Rapidly Instantiating BLAS Functionality". ACM Transactions on Mathematical Software. 41 (3): 1–33. doi:10.1145/2764454. S2CID 1242360.
How To Optimize GEMM

[skiena-1] 1.0 ^1.1 ^1.2 ^1.3 Skiena, Steven (2008). "Sorting and Searching". एल्गोरिथम डिज़ाइन मैनुअल. Springer. pp. 45–46, 401–3. doi:10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[dwz22-2] Duan, Ran; Wu, Hongxun; Zhou, Renfei (2022), Faster Matrix Multiplication via Asymmetric Hashing, arXiv:2210.10173

[aw20-3] 3.0 ^3.1 Alman, Josh; Williams, Virginia Vassilevska (2020), "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv:2010.05846

[quanta-4] Hartnett, Kevin (23 March 2021). "मैट्रिक्स गुणन इंच पौराणिक लक्ष्य के करीब". Quanta Magazine (in English). Retrieved 2021-04-01.

[clrs-5] 5.0 ^5.1 ^5.2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 75–79. ISBN 0-262-03384-4.

[ocw-6] 6.0 ^6.1 ^6.2 ^6.3 ^6.4 Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 Performance Engineering of Software Systems, Lecture 8". MIT OpenCourseWare. Massachusetts Institute of Technology. Retrieved 27 January 2015.

[7] Lam, Monica S.; Rothberg, Edward E.; Wolf, Michael E. (1991). अवरुद्ध एल्गोरिदम का कैश प्रदर्शन और अनुकूलन. ASPLOS91: 4th Int'l Conference on Architecture Support for Programming Languages & Operating Systems. doi:10.1145/106972.106981. ISBN 978-0-89791-380-5.

[prokop-8] 8.0 ^8.1 ^8.2 Prokop, Harald (1999). कैश-ओब्लिवियस एल्गोरिदम (PDF) (Master's). MIT. hdl:1721.1/80568.

[9] Miller, Webb (1975), "Computational complexity and numerical stability", SIAM News, 4 (2): 97–107, CiteSeerX 10.1.1.148.9947, doi:10.1137/0204009

[10] Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. p. 108. ISBN 978-0-521-88068-8.

[coppersmith-11] Coppersmith, Don; Winograd, Shmuel (1990), "Matrix multiplication via arithmetic progressions" (PDF), Journal of Symbolic Computation, 9 (3): 251, doi:10.1016/S0747-7171(08)80013-2

[12] Iliopoulos, Costas S. (1989), "Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix" (PDF), SIAM Journal on Computing, 18 (4): 658–669, CiteSeerX 10.1.1.531.9309, doi:10.1137/0218045, MR 1004789, archived from the original (PDF) on 2014-03-05, retrieved 2015-01-16, The Coppersmith–Winograd algorithm is not practical, due to the very large hidden constant in the upper bound on the number of multiplications required.

[robinson-13] Robinson, Sara (November 2005), "Toward an Optimal Algorithm for Matrix Multiplication" (PDF), SIAM News, 38 (9), Even if someone manages to prove one of the conjectures—thereby demonstrating that $ω = 2$ —the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. [...] the input matrices must be astronomically large for the difference in time to be apparent.

[14] "AlphaTensor के साथ नवीन एल्गोरिदम की खोज". www.deepmind.com (in English). Retrieved 2022-11-01.

[alphatensor-15] 15.0 ^15.1 Fawzi, Alhussein; Balog, Matej; Huang, Aja; Hubert, Thomas; Romera-Paredes, Bernardino; Barekatain, Mohammadamin; Novikov, Alexander; R. Ruiz, Francisco J.; Schrittwieser, Julian; Swirszcz, Grzegorz; Silver, David; Hassabis, Demis; Kohli, Pushmeet (October 2022). "सुदृढीकरण सीखने के साथ तेज़ मैट्रिक्स गुणन एल्गोरिदम की खोज करना". Nature. 610 (7930): 47–53. Bibcode:2022Natur.610...47F. doi:10.1038/s41586-022-05172-4. ISSN 1476-4687. PMC 9534758. PMID 36198780.

[16] Kauers, Manuel; Moosbauer, Jakob (2022-12-02). "मैट्रिक्स गुणन के लिए फ़्लिप ग्राफ़". arXiv:2212.01175 [cs.SC].

[17] Brubaker, Ben (23 November 2022). "एआई मैट्रिक्स गुणन में नई संभावनाओं को प्रकट करता है". Quanta Magazine (in English). Retrieved 26 November 2022.

[cilk-18] 18.0 ^18.1 Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). Massachusetts Institute of Technology. pp. 54–57. hdl:1721.1/47519.

[19] Cannon, Lynn Elliot (14 July 1969). कलमन फ़िल्टर एल्गोरिथम को लागू करने के लिए एक सेलुलर कंप्यूटर (Ph.D.). Montana State University.

[20] Hong, J. W.; Kung, H. T. (1981). "I/O complexity: The red-blue pebble game" (PDF). STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing: 326–333. doi:10.1145/800076.802486. S2CID 8410593. Archived (PDF) from the original on December 15, 2019.

[irony-21] 21.0 ^21.1 ^21.2 Irony, Dror; Toledo, Sivan; Tiskin, Alexander (September 2004). "वितरित-मेमोरी मैट्रिक्स गुणन के लिए संचार निचली सीमाएं". J. Parallel Distrib. Comput. 64 (9): 1017–26. CiteSeerX 10.1.1.20.7034. doi:10.1016/j.jpdc.2004.03.021.

[Agarwal-22] 22.0 ^22.1 Agarwal, R.C.; Balle, S. M.; Gustavson, F. G.; Joshi, M.; Palkar, P. (September 1995). "समानांतर मैट्रिक्स गुणन के लिए एक त्रि-आयामी दृष्टिकोण". IBM J. Res. Dev. 39 (5): 575–582. CiteSeerX 10.1.1.44.3404. doi:10.1147/rd.395.0575.

[23] Solomonik, Edgar; Demmel, James (2011). "Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms" (PDF). Proceedings of the 17th International Conference on Parallel Processing. Vol. Part II. pp. 90–109. doi:10.1007/978-3-642-23397-5_10. ISBN 978-3-642-23397-5.

[24] Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "MapReduce का उपयोग करके आयाम स्वतंत्र मैट्रिक्स स्क्वायर" (PDF). arXiv:1304.1467. Bibcode:2013arXiv1304.1467B. Retrieved 12 July 2014.

[25] Bae, S.E.; Shinn, T.-W.; Takaoka, T. (2014). "जाल सरणी पर मैट्रिक्स गुणन के लिए एक तेज़ समानांतर एल्गोरिदम". Procedia Computer Science. 29: 2230–40. doi:10.1016/j.procs.2014.05.208.

[26] Kak, S (1988). "मैट्रिक्स गुणन के लिए एक दो-परत जाल सरणी". Parallel Computing. 6 (3): 383–5. CiteSeerX 10.1.1.88.8527. doi:10.1016/0167-8191(88)90078-6.

[27] Kak, S. (2014). "क्रॉस-वायर्ड जाल सरणी पर मैट्रिक्स गुणन की दक्षता". arXiv:1411.3273 [cs.DC].

[28] Kak, S (1988). "बहुस्तरीय सरणी कंप्यूटिंग". Information Sciences. 45 (3): 347–365. CiteSeerX 10.1.1.90.4753. doi:10.1016/0020-0255(88)90010-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

@@ Line 1: / Line 1: @@
 {{short description|Algorithm to multiply matrices}}
-[[मैट्रिक्स गुणन|आव्यूह गुणन]] कई संख्यात्मक कलनविधि में एक ऐसा केंद्रीय संक्रिया है, कलनविधि में आव्यूह गुणन को प्रवीण बनाने में बहुत काम किया गया है। इस प्रकार अभिकलनात्मक समस्याओं में आव्यूह गुणन के अनुप्रयोग [[वैज्ञानिक कंप्यूटिंग|वैज्ञानिक अभिकलन]] और पैटर्न रिकॉग्नाइजेसन सहित कई क्षेत्रों में संभवतः प्रतीत होने वाली असंबंधित समस्याओं के रूप में पाए जाते हैं और ग्राफ के माध्यम से पथों की गिनती होती है।<ref name="skiena"/> [[समानांतर कंप्यूटिंग|समानांतर अभिकलन]] और वितरित अभिकलन प्रणाली सहित विभिन्न प्रकार के हार्डवेयर पर आव्यूह को गुणा करने के लिए कई भिन्न -भिन्न कलनविधि के रूप में डिज़ाइन किए गए हैं, जहां अभिकलनात्मक कार्य कई प्रोसेसर पर संभवतः एक नेटवर्क के ऊपर फैला हुआ है।
+[[मैट्रिक्स गुणन|आव्यूह गुणन]] कई संख्यात्मक कलनविधि में एक केंद्रीय संक्रिया है, जबकि कलनविधि में आव्यूह गुणन को प्रवीण बनाने में बहुत काम किया गया है। इस प्रकार अभिकलनात्मक समस्याओं में आव्यूह गुणन के अनुप्रयोग [[वैज्ञानिक कंप्यूटिंग|वैज्ञानिक अभिकलन]] और पैटर्न रिकॉग्नाइजेसन सहित कई क्षेत्रों में संभवतः प्रतीत होने वाली असंबंधित समस्याओं के रूप में पाए जाते हैं और आलेख के माध्यम से पथों की गिनती होती है।<ref name="skiena"/> [[समानांतर कंप्यूटिंग|समानांतर अभिकलन]] और वितरित अभिकलन प्रणाली सहित विभिन्न प्रकार के हार्डवेयर पर आव्यूह को गुणा करने के लिए कई भिन्न -भिन्न कलनविधि के रूप में डिज़ाइन किया जाता है , जहां अभिकलनात्मक कार्य कई प्रोसेसर पर संभवतः एक नेटवर्क के रूप में फैला हुआ है।
-आव्यूह गुणन की गणितीय परिभाषा को सीधे प्रयुक्त करने से एक कलनविधि मिलता है, जिसके {{math|''n''<sup>3</sup>}} क्रम पर [[एल्गोरिदम का विश्लेषण|कलनविधि का विश्लेषण]] होता है और इस प्रकार दो को गुणा करने के लिए [[फ़ील्ड (गणित)|(गणित क्षेत्र)]] संक्रिया {{math|''n'' × ''n''}} उस क्षेत्र पर आव्यूह ({{math|Θ(''n''<sup>3</sup>)}} बड़े O अंकन में होता है। 1960 के दशक में स्ट्रैसेन कलनविधि के बाद से आव्यूह को गुणा करने के लिए आवश्यक समय पर अच्छे स्पर्शोन्मुख सीमाएं ज्ञात हैं, लेकिन ऑप्टीमल समय अर्थात [[मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता|आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता]] अज्ञात बनी हुई है। और इस प्रकार अक्टूबर 2022 तक आव्यूह गुणन कलनविधि की समय सम्मिश्रता पर सबसे अच्छी घोषणा {{math|O(''n''<sup>2.37188</sup>)}} की गई थी, जिसे डुआन, वू और झोउ द्वारा दिया गया था<ref name="dwz22">
+आव्यूह गुणन की गणितीय परिभाषा को सीधे प्रयुक्त करने से एक कलनविधि मिलता है, जिसके {{math|''n''<sup>3</sup>}} क्रम पर [[एल्गोरिदम का विश्लेषण|कलनविधि का विश्लेषण]] होता है और इस प्रकार दो को गुणा करने के लिए [[फ़ील्ड (गणित)|(गणित क्षेत्र)]] संक्रिया {{math|''n'' × ''n''}} उस क्षेत्र पर आव्यूह ({{math|Θ(''n''<sup>3</sup>)}} बड़े O नोटेशन के रूप में होता है। 1960 के दशक में स्ट्रैसेन कलनविधि के बाद से आव्यूह को गुणा करने के लिए आवश्यक समय पर अच्छे ऐसिम्टाटिक सीमाएं ज्ञात हैं, लेकिन इष्टतम समय अर्थात [[मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता|आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता]] अज्ञात बनी हुई है। और इस प्रकार अक्टूबर 2022 तक आव्यूह गुणन कलनविधि की समय सम्मिश्रता पर सबसे अच्छी घोषणा {{math|O(''n''<sup>2.37188</sup>)}} की गई थी, जिसे डुआन, वू और झोउ द्वारा दिया गया था<ref name="dwz22">
 {{Citation
   | last1=Duan
@@ Line 30: / Line 30: @@
 :<math>c_{ij} = \sum_{k=1}^m a_{ik} b_{kj}.</math>
-इससे, एक सरल कलनविधि का निर्माण किया जा सकता है जो सूचकांकों पर लूप करता है {{mvar|i}} 1 से लेकर {{mvar|n}} और {{mvar|j}} 1 से लेकर {{mvar|p}}, नेस्टेड लूप का उपयोग करके उपरोक्त की गणना की जा सकती है
+इससे, एक सरल कलनविधि का निर्माण किया जा सकता है जो सूचकांकों पर लूप करता है {{mvar|i}} 1 से लेकर {{mvar|n}} और {{mvar|j}} 1 से लेकर {{mvar|p}}, नेस्टेड लूप का उप समेशन करके उपरोक्त की गणना की जा सकती है
 {{framebox|blue}}
@@ Line 44: / Line 44: @@
 {{frame-footer}}
-यह कलनविधि [[एसिम्प्टोटिक नोटेशन|स्पर्शोन्मुख नोटेशन]] में समय {{math|Θ(''nmp'')}} लेता है।<ref name="skiena"/> इस प्रकार कलनविधि के विश्लेषण के उद्देश्य से एक सामान्य सरलीकरण यह मान लेता है कि इनपुट सभी आकार {{math|''n'' × ''n''}} के वर्ग आव्यूह होते है, जिस स्थिति में रनिंग समय {{math|Θ(''n''<sup>3</sup>)}}, के रूप में अर्थात आयाम के आकार में घन होता है।<ref name="clrs">{{Introduction to Algorithms|3|pages=75–79}}</ref>
+यह कलनविधि [[एसिम्प्टोटिक नोटेशन|ऐसिम्टाटिक नोटेशन]] में समय {{math|Θ(''nmp'')}} लेता है।<ref name="skiena"/> इस प्रकार कलनविधि के विश्लेषण के उद्देश्य से एक सामान्य सरलीकरण यह मान लेता है कि इनपुट सभी आकार {{math|''n'' × ''n''}} के वर्ग आव्यूह होते है, जिस स्थिति में रनिंग समय {{math|Θ(''n''<sup>3</sup>)}}, के रूप में अर्थात आयाम के आकार में घन होता है।<ref name="clrs">{{Introduction to Algorithms|3|pages=75–79}}</ref>
 ===कैशे व्यवहार===
-[[File:Row_and_column_major_order.svg|thumb|upright|पंक्ति और स्तंभ-प्रमुख क्रम का चित्रण]]पुनरावृत्तीय आव्यूह गुणन में तीन लूपों को शुद्धता या स्पर्शोन्मुख रनिंग टाइम पर प्रभाव के बिना एक दूसरे के साथ यादृच्छिक प्रकार से स्वैप किया जाता है। चूंकि, मेमोरी एक्सेस पैटर्न और कलनविधि के [[सीपीयू कैश|सीपीयू कैशे]] उपयोग के कारण व्यावहारिक ऑर्डर प्रदर्शन पर बहुत प्रभाव डालता है;<ref name="skiena">{{cite book |first=Steven |last=Skiena |author-link=Steven Skiena |title=एल्गोरिथम डिज़ाइन मैनुअल|url=https://archive.org/details/algorithmdesignm00skie_772 |url-access=limited |publisher=Springer |year=2008 |pages=[https://archive.org/details/algorithmdesignm00skie_772/page/n56 45]–46, 401–3 |doi=10.1007/978-1-84800-070-4_4|chapter=Sorting and Searching |isbn=978-1-84800-069-8 }}</ref> और इस प्रकार कौन सा क्रम सबसे अच्छा है यह इस बात पर भी निर्भर करता है कि क्या आव्यूह पंक्ति और स्तंभ प्रमुख का क्रम संग्रहीत हैं या दोनों के मिश्रण में संग्रहीत हैं।
+[[File:Row_and_column_major_order.svg|thumb|upright|पंक्ति और स्तंभ-प्रमुख क्रम का चित्रण]]पुनरावृत्तीय आव्यूह गुणन में तीन लूपों को शुद्धता या ऐसिम्टाटिक रनिंग टाइम पर प्रभाव के बिना एक दूसरे के साथ यादृच्छिक प्रकार से स्वैप किया जाता है। चूंकि, मेमोरी एक्सेस पैटर्न और कलनविधि के [[सीपीयू कैश|सीपीयू कैशे]] उप समेशन के कारण व्यावहारिक ऑर्डर प्रदर्शन पर बहुत प्रभाव डालता है;<ref name="skiena">{{cite book |first=Steven |last=Skiena |author-link=Steven Skiena |title=एल्गोरिथम डिज़ाइन मैनुअल|url=https://archive.org/details/algorithmdesignm00skie_772 |url-access=limited |publisher=Springer |year=2008 |pages=[https://archive.org/details/algorithmdesignm00skie_772/page/n56 45]–46, 401–3 |doi=10.1007/978-1-84800-070-4_4|chapter=Sorting and Searching |isbn=978-1-84800-069-8 }}</ref> और इस प्रकार कौन सा क्रम सबसे अच्छा है यह इस बात पर भी निर्भर करता है कि क्या आव्यूह पंक्ति और स्तंभ प्रमुख का क्रम संग्रहीत हैं या दोनों के मिश्रण में संग्रहीत हैं।
-विशेष रूप से, पूरी तरह से संबंधित कैश के आदर्श स्थिति में जिसमें {{mvar|M}} बाइट्स और {{mvar|b}} बाइट्स प्रति कैशे लाइन के रूप में सम्मलित होता है। (यदि {{sfrac|''M''|''b''}} कैशे लाइनें), उपरोक्त कलनविधि इसके लिए सब-ऑप्टीमल है {{mvar|A}} और {{mvar|B}} पंक्ति-प्रमुख क्रम में संग्रहीत होते है जब {{math|''n'' > {{sfrac|''M''|''b''}}}}, आंतरिक लूप का प्रत्येक पुनरावृत्ति एक पंक्ति के माध्यम से एक साथ स्वीप होते है। इस प्रकार {{mvar|A}} का एक कॉलम {{mvar|B}} के किसी तत्व तक पहुंचने पर कैशे मिस {{mvar|B}}.हो जाता है इसका अर्थ यह है कि कलनविधि {{math|Θ(''n''<sup>3</sup>)}} के रूप में प्रयुक्त होता है और सबसे खराब स्थिति में कैशे छूट जाता है। वर्ष 2010 तक, प्रोसेसर की तुलना में मेमोरी की गति ऐसी होती है कि वास्तविक गणना के अतिरिक्त कैशे मिस हो जाता है, जो बड़े आकार के आव्यूह के लिए रनिंग समय पर प्रभावी हो जाता है।<ref name="ocw">{{cite web|url=http://aka-ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/|title=6.172 Performance Engineering of Software Systems, Lecture 8|last1=Amarasinghe|first1=Saman|last2=Leiserson|first2=Charles|year=2010|website=MIT OpenCourseWare|publisher=Massachusetts Institute of Technology|access-date=27 January 2015}}</ref>
+विशेष रूप से, पूरी तरह से संबंधित कैश के आदर्श स्थिति में जिसमें {{mvar|M}} बाइट्स और {{mvar|b}} बाइट्स प्रति कैशे लाइन के रूप में सम्मलित होता है। (यदि {{sfrac|''M''|''b''}} कैशे लाइनें), उपरोक्त कलनविधि इसके लिए सब-इष्टतम है {{mvar|A}} और {{mvar|B}} पंक्ति-प्रमुख क्रम में संग्रहीत होते है जब {{math|''n'' > {{sfrac|''M''|''b''}}}}, आंतरिक लूप का प्रत्येक पुनरावृत्ति एक पंक्ति के माध्यम से एक साथ स्वीप होते है। इस प्रकार {{mvar|A}} का एक कॉलम {{mvar|B}} के किसी तत्व तक पहुंचने पर कैशे मिस {{mvar|B}}.हो जाता है इसका अर्थ यह है कि कलनविधि {{math|Θ(''n''<sup>3</sup>)}} के रूप में प्रयुक्त होता है और सबसे खराब स्थिति में कैशे छूट जाता है। वर्ष 2010 तक, प्रोसेसर की तुलना में मेमोरी की गति ऐसी होती है कि वास्तविक गणना के अतिरिक्त कैशे मिस हो जाता है, जो बड़े आकार के आव्यूह के लिए रनिंग समय पर प्रभावी हो जाता है।<ref name="ocw">{{cite web|url=http://aka-ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/|title=6.172 Performance Engineering of Software Systems, Lecture 8|last1=Amarasinghe|first1=Saman|last2=Leiserson|first2=Charles|year=2010|website=MIT OpenCourseWare|publisher=Massachusetts Institute of Technology|access-date=27 January 2015}}</ref>
-पंक्ति-प्रमुख लेआउट में {{mvar|A}} और {{mvar|B}} के लिए पुनरावृत्तीय कलनविधि का ऑप्टीमल संस्करण एक [[लूप टाइलिंग]] संस्करण है, जहां आव्यूह को आकार {{math|{{radic|''M''}}}} द्वारा {{math|{{radic|''M''}}}} के वर्गाकार टाइलों में विभाजित किया गया है,:<ref name="ocw"/><ref>{{cite conference |first1=Monica S. |last1=Lam |first2=Edward E. |last2=Rothberg |first3=Michael E. |last3=Wolf |title=अवरुद्ध एल्गोरिदम का कैश प्रदर्शन और अनुकूलन|conference=ASPLOS91: 4th Int'l Conference on Architecture Support for Programming Languages & Operating Systems |isbn=978-0-89791-380-5 |year=1991 |doi=10.1145/106972.106981}}</ref>
+पंक्ति-प्रमुख लेआउट में {{mvar|A}} और {{mvar|B}} के लिए पुनरावृत्तीय कलनविधि का इष्टतम संस्करण एक [[लूप टाइलिंग]] संस्करण है, जहां आव्यूह को आकार {{math|{{radic|''M''}}}} द्वारा {{math|{{radic|''M''}}}} के वर्गाकार टाइलों में विभाजित किया गया है,:<ref name="ocw"/><ref>{{cite conference |first1=Monica S. |last1=Lam |first2=Edward E. |last2=Rothberg |first3=Michael E. |last3=Wolf |title=अवरुद्ध एल्गोरिदम का कैश प्रदर्शन और अनुकूलन|conference=ASPLOS91: 4th Int'l Conference on Architecture Support for Programming Languages & Operating Systems |isbn=978-0-89791-380-5 |year=1991 |doi=10.1145/106972.106981}}</ref>
 {{framebox|blue}}
@@ Line 102: / Line 102: @@
 \end{pmatrix}
 </math>
-जिसमें उपमैट्रिस के युग्मों के आठ गुणन होते हैं, जिसके बाद एक अतिरिक्त चरण होता है। इस प्रकार डिवाइड और क्न्क्वेर कलनविधि अदिश गुणन का उपयोग करके छोटे गुणन [[प्रत्यावर्तन]] की गणना करता है {{math|''c''<sub>11</sub> {{=}} ''a''<sub>11</sub>''b''<sub>11</sub>}} इसके आधार स्थिति के रूप में है।
+जिसमें उपमैट्रिस के युग्मों के आठ गुणन होते हैं, जिसके बाद एक अतिरिक्त चरण होता है। इस प्रकार डिवाइड और क्न्क्वेर कलनविधि अदिश गुणन का उप समेशन करके छोटे गुणन [[प्रत्यावर्तन]] की गणना करता है {{math|''c''<sub>11</sub> {{=}} ''a''<sub>11</sub>''b''<sub>11</sub>}} इसके आधार स्थिति के रूप में है।
 फलन के रूप में इस कलनविधि की सम्मिश्रता {{mvar|n}} पुनरावृत्ति द्वारा दिया जाता है<ref name="clrs"/>
@@ Line 108: / Line 108: @@
 :<math>T(1) = \Theta(1);</math>
 :<math>T(n) = 8T(n/2) + \Theta(n^2),</math>
-आकार के आव्यूह पर आठ रिकर्सिव कॉलों के लिए लेखांकन {{math|''n''/2}} और {{math|Θ(''n''<sup>2</sup>)}} परिणामी आव्यूहों के चार युग्मों का तत्व-वार योग होता है। मास्टर प्रमेय का अनुप्रयोग कलनविधि का विश्लेषण डिवाइड और क्न्क्वेर पुनरावृत्ति के लिए मास्टर प्रमेय इस पुनरावृत्ति को समाधान के लिए {{math|Θ(''n''<sup>3</sup>)}} पुनरावृत्तीय कलनविधि के समान दिखाता है,<ref name="clrs"/>
+आकार के आव्यूह पर आठ रिकर्सिव कॉलों के लिए लेखांकन {{math|''n''/2}} और {{math|Θ(''n''<sup>2</sup>)}} परिणामी आव्यूहों के चार युग्मों का तत्व-वार समेशन होता है। मास्टर प्रमेय का अनुप्र समेशन कलनविधि का विश्लेषण डिवाइड और क्न्क्वेर पुनरावृत्ति के लिए मास्टर प्रमेय इस पुनरावृत्ति को समाधान के लिए {{math|Θ(''n''<sup>3</sup>)}} पुनरावृत्तीय कलनविधि के समान दिखाता है,<ref name="clrs"/>
 ===गैर-वर्ग आव्यूह===
 इस कलनविधि का एक प्रकार जो यादृच्छिक आकार के आव्यूह के लिए काम करता है और व्यवहार में फ़ास्ट होता है<ref name="ocw"/>आव्यूह को चार उपमैट्रिस में विभाजित करता है।<ref name="prokop">{{cite thesis |type=Master's |first=Harald |last=Prokop |author-link=Harald Prokop |title=कैश-ओब्लिवियस एल्गोरिदम|publisher=MIT |year=1999 |url=http://supertech.csail.mit.edu/papers/Prokop99.pdf |hdl=1721.1/80568}}</ref> इस प्रकार आव्यूह को विभाजित करने का अर्थ अब इसे समान आकार के दो भागों में विभाजित करना है या विषम आयामों की स्थिती में जितना संभव हो सके समान आकार के निकट विभाजित करता है।
@@ Line 132: / Line 132: @@
 ===कैशे व्यवहार===
-रिकर्सिव आव्यूह गुणन की कैशे मिस दर लूप टाइलिंग पुनरावृत्तीय संस्करण के समान है, लेकिन उस कलनविधि के विपरीत, रिकर्सिव कलनविधि [[कैश-विस्मृत एल्गोरिथ्म|कैशे -विस्मृत]] कलनविधि है|कैशे -ओब्लिवियस:<ref name="prokop"/>ऑप्टीमल कैशे प्रदर्शन प्राप्त करने के लिए कोई ट्यूनिंग पैरामीटर आवश्यक नहीं है, और यह [[ बहु क्रमादेशन |बहु क्रमादेशन]] वातावरण में अच्छा व्यवहार करता है जहां कैशे स्थान लेने वाली अन्य प्रक्रियाओं के कारण कैशे आकार प्रभावी रूप से गतिशील होते हैं।<ref name="ocw"/>(सरल पुनरावृत्तीय कलनविधि कैशे -विस्मृत भी है, लेकिन यदि आव्यूह लेआउट कलनविधि के लिए अनुकूलित नहीं है तो व्यवहार में बहुत धीमा है।)
+रिकर्सिव आव्यूह गुणन की कैशे मिस दर लूप टाइलिंग पुनरावृत्तीय संस्करण के समान है, लेकिन उस कलनविधि के विपरीत, रिकर्सिव कलनविधि [[कैश-विस्मृत एल्गोरिथ्म|कैशे -विस्मृत]] कलनविधि है|कैशे -ओब्लिवियस:<ref name="prokop"/>इष्टतम कैशे प्रदर्शन प्राप्त करने के लिए कोई ट्यूनिंग पैरामीटर आवश्यक नहीं है, और यह [[ बहु क्रमादेशन |बहु क्रमादेशन]] वातावरण में अच्छा व्यवहार करता है जहां कैशे स्थान लेने वाली अन्य प्रक्रियाओं के कारण कैशे आकार प्रभावी रूप से गतिशील होते हैं।<ref name="ocw"/>(सरल पुनरावृत्तीय कलनविधि कैशे -विस्मृत भी है, लेकिन यदि आव्यूह लेआउट कलनविधि के लिए अनुकूलित नहीं है तो व्यवहार में बहुत धीमा है।)
 इस कलनविधि द्वारा किसी मशीन पर कैशे मिस होने की संख्या {{mvar|M}} आदर्श कैशे की पंक्तियाँ, प्रत्येक आकार की {{mvar|b}} बाइट्स, से घिरा है{{r|prokop}}{{rp|13}}
@@ Line 142: / Line 142: @@
 {{further|आव्यूह गुणन की कम्प्यूटेशनल जटिलता}}
-[[File:MatrixMultComplexity svg.svg|thumb|400px|right|घातांक के अनुमानों में सुधार {{math|ω}}आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता के लिए समय के साथ <math>O(n^\omega)</math>.]]ऐसे कलनविधि उपस्थित हैं जो सीधे चलने वाले कलनविधि की तुलना में अच्छे चलने का समय प्रदान करते हैं। सबसे पहले खोजी गई स्ट्रैसेन कलनविधि थी, जिसे 1969 में [[वोल्कर स्ट्रैस]]न द्वारा तैयार किया गया था और इसे अधिकांशतः फास्ट आव्यूह गुणन के रूप में जाना जाता है। यह दो {{math|2 × 2}}-आव्यूह को गुणा करने की विधि पर आधारित है, जिसमें कई अतिरिक्त जोड़ और घटाव संचालन की कीमत पर केवल 7 गुणन सामान्य 8 के अतिरिक्त की आवश्यकता होती है। इसे रिकर्सिव रूप से प्रयुक्त करने से गुणात्मक लागत वाला एक कलनविधि प्राप्त होता है <math>O( n^{\log_{2}7}) \approx O(n^{2.807})</math>. स्ट्रैसेन का कलनविधि अधिक सम्मिश्र है और अनुभवहीन कलनविधि की तुलना में [[संख्यात्मक स्थिरता]] कम हो गई है,<ref>{{Citation | last1=Miller | first1=Webb | title=Computational complexity and numerical stability | citeseerx = 10.1.1.148.9947 | year=1975 | journal=SIAM News | volume=4 | issue=2 | pages=97–107 | doi=10.1137/0204009}}</ref> लेकिन ऐसे स्थितियों में यह {{math|''n'' > 100}} फ़ास्ट है<ref name="skiena"/> यह कई पुस्तकालयों में दिखाई देता है, जैसे कि BLAS ([[बुनियादी रैखिक बीजगणित उपप्रोग्राम|बुनियादी रैखिक बीजगणित सबप्रोग्राम]] )<ref>{{cite book |last1=Press |first1=William H. |last2=Flannery |first2=Brian P. |last3=Teukolsky |first3=Saul A. |author3-link=Saul Teukolsky |last4=Vetterling |first4=William T. |title=Numerical Recipes: The Art of Scientific Computing |publisher=[[Cambridge University Press]] |edition=3rd |isbn=978-0-521-88068-8 |year=2007 |page=[https://archive.org/details/numericalrecipes00pres_033/page/n131 108]|title-link=Numerical Recipes }}</ref> यह [[परिमित क्षेत्र]] जैसे सटीक डोमेन पर बड़े आव्यूह के लिए बहुत उपयोगी है, जहां संख्यात्मक स्थिरता समस्या नहीं है।
+[[File:MatrixMultComplexity svg.svg|thumb|400px|right|घातांक के अनुमानों में सुधार {{math|ω}}आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता के लिए समय के साथ <math>O(n^\omega)</math>.]]ऐसे कलनविधि उपस्थित हैं जो सीधे चलने वाले कलनविधि की तुलना में अच्छे चलने का समय प्रदान करते हैं। सबसे पहले खोजी गई स्ट्रैसेन कलनविधि थी, जिसे 1969 में [[वोल्कर स्ट्रैस]]न द्वारा तैयार किया गया था और इसे अधिकांशतः फास्ट आव्यूह गुणन के रूप में जाना जाता है। यह दो {{math|2 × 2}}-आव्यूह को गुणा करने की विधि पर आधारित है, जिसमें कई अतिरिक्त जोड़ और घटाव संचालन की कीमत पर केवल 7 गुणन सामान्य 8 के अतिरिक्त की आवश्यकता होती है। इसे रिकर्सिव रूप से प्रयुक्त करने से गुणात्मक लागत वाला एक कलनविधि प्राप्त होता है <math>O( n^{\log_{2}7}) \approx O(n^{2.807})</math>. स्ट्रैसेन का कलनविधि अधिक सम्मिश्र है और अनुभवहीन कलनविधि की तुलना में [[संख्यात्मक स्थिरता]] कम हो गई है,<ref>{{Citation | last1=Miller | first1=Webb | title=Computational complexity and numerical stability | citeseerx = 10.1.1.148.9947 | year=1975 | journal=SIAM News | volume=4 | issue=2 | pages=97–107 | doi=10.1137/0204009}}</ref> लेकिन ऐसे स्थितियों में यह {{math|''n'' > 100}} फ़ास्ट है<ref name="skiena"/> यह कई पुस्तकालयों में दिखाई देता है, जैसे कि BLAS ([[बुनियादी रैखिक बीजगणित उपप्रोग्राम|बुनियादी रैखिक बीजगणित सबप्रोग्राम]] )<ref>{{cite book |last1=Press |first1=William H. |last2=Flannery |first2=Brian P. |last3=Teukolsky |first3=Saul A. |author3-link=Saul Teukolsky |last4=Vetterling |first4=William T. |title=Numerical Recipes: The Art of Scientific Computing |publisher=[[Cambridge University Press]] |edition=3rd |isbn=978-0-521-88068-8 |year=2007 |page=[https://archive.org/details/numericalrecipes00pres_033/page/n131 108]|title-link=Numerical Recipes }}</ref> यह [[परिमित क्षेत्र]] जैसे सटीक डोमेन पर बड़े आव्यूह के लिए बहुत उप समेशन ी है, जहां संख्यात्मक स्थिरता समस्या नहीं है।
-[[सैद्धांतिक कंप्यूटर विज्ञान]] में यह एक खुला प्रश्न है कि समय सम्मिश्रता के संदर्भ में स्ट्रैसेन के कलनविधि को कितनी अच्छी तरह सुधारा जा सकता है। आव्यूह गुणन घातांक, सामान्यतः <math>\omega</math> द्वारा निरूपित किया जाता है वह सबसे छोटी वास्तविक संख्या है जिसके लिए कोई भी <math>n\times n</math> किसी क्षेत्र पर <math>n^{\omega + o(1)}</math> क्षेत्र संक्रिया का उपयोग करके एक साथ गुणा किया जा सकता है इस प्रकार x <math>\omega</math> पर उपस्थित सर्वश्रेष्ठ बाउंड जोश अल्मन और वर्जीनिया वासिलिव्स्का विलियम्स द्वारा <math>\omega < 2.3728596</math> है।<ref name="aw20" /> यह कलन विधि , अनुसंधान की इस पंक्ति में अन्य सभी वर्तमान कलनविधि की तरह कॉपरस्मिथ-विनोग्राड कलनविधि का एक सामान्यीकरण है, जो 1990 में [[डॉन कॉपरस्मिथ]] और [[शमूएल विनोग्राड]] द्वारा दिया गया था।<ref name="coppersmith">{{Citation|doi=10.1016/S0747-7171(08)80013-2 |title=Matrix multiplication via arithmetic progressions |url=http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf |year=1990 |last1=Coppersmith |first1=Don |last2=Winograd |first2=Shmuel |journal=Journal of Symbolic Computation |volume=9|issue=3|pages=251|doi-access=free }}</ref> इन कलनविधि का वैचारिक विचार स्ट्रैसेन के कलनविधि के समान है और दो {{math|''k'' × ''k''}} आव्यूह को {{math|''k''<sup>3</sup>}} से कम गुणन के साथ गुणा करने का एक तरीका तैयार किया गया है और इस प्रोद्योगिकीय को पुनरावर्ती के रूप से प्रयुक्त किया जाता है। चूंकि, बिग o नोटेशन द्वारा छिपा हुआ निरंतर गुणांक इतना बड़ा है कि ये कलनविधि केवल उन आव्यूह के लिए उपयुक्त हैं जो वर्तमान कंप्यूटरों पर संभालने के लिए बहुत बड़े हैं।<ref>{{citation
+[[सैद्धांतिक कंप्यूटर विज्ञान]] में यह एक खुला प्रश्न है कि समय सम्मिश्रता के संदर्भ में स्ट्रैसेन के कलनविधि को कितनी अच्छी तरह सुधारा जा सकता है। आव्यूह गुणन घातांक, सामान्यतः <math>\omega</math> द्वारा निरूपित किया जाता है वह सबसे छोटी वास्तविक संख्या है जिसके लिए कोई भी <math>n\times n</math> किसी क्षेत्र पर <math>n^{\omega + o(1)}</math> क्षेत्र संक्रिया का उप समेशन करके एक साथ गुणा किया जा सकता है इस प्रकार x <math>\omega</math> पर उपस्थित सर्वश्रेष्ठ बाउंड जोश अल्मन और वर्जीनिया वासिलिव्स्का विलियम्स द्वारा <math>\omega < 2.3728596</math> है।<ref name="aw20" /> यह कलन विधि , अनुसंधान की इस पंक्ति में अन्य सभी वर्तमान कलनविधि की तरह कॉपरस्मिथ-विनोग्राड कलनविधि का एक सामान्यीकरण है, जो 1990 में [[डॉन कॉपरस्मिथ]] और [[शमूएल विनोग्राड]] द्वारा दिया गया था।<ref name="coppersmith">{{Citation|doi=10.1016/S0747-7171(08)80013-2 |title=Matrix multiplication via arithmetic progressions |url=http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf |year=1990 |last1=Coppersmith |first1=Don |last2=Winograd |first2=Shmuel |journal=Journal of Symbolic Computation |volume=9|issue=3|pages=251|doi-access=free }}</ref> इन कलनविधि का वैचारिक विचार स्ट्रैसेन के कलनविधि के समान है और दो {{math|''k'' × ''k''}} आव्यूह को {{math|''k''<sup>3</sup>}} से कम गुणन के साथ गुणा करने का एक तरीका तैयार किया गया है और इस प्रोद् समेशन िकीय को पुनरावर्ती के रूप से प्रयुक्त किया जाता है। चूंकि, बिग o नोटेशन द्वारा छिपा हुआ निरंतर गुणांक इतना बड़ा है कि ये कलनविधि केवल उन आव्यूह के लिए उपयुक्त हैं जो वर्तमान कंप्यूटरों पर संभालने के लिए बहुत बड़े हैं।<ref>{{citation
   | last = Iliopoulos
   | first = Costas S.
@@ Line 168: / Line 168: @@
 === अल्फा टेन्सर ===
-में, [[डीपमाइंड]] ने अल्फ़ाटेनसर [[तंत्रिका नेटवर्क|न्यूरल नेटवर्क]] प्रस्तुत किया है, जिसने हजारों आव्यूह गुणन कलनविधि का आविष्कार करने के लिए एकल-प्लेयर गेम सादृश्य का उपयोग किया, जिनमें से कुछ पहले मनुष्यों द्वारा खोजे गए थे और कुछ जो नहीं थे।<ref>{{Cite web |title=AlphaTensor के साथ नवीन एल्गोरिदम की खोज|url=https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor |access-date=2022-11-01 |website=www.deepmind.com |language=en}}</ref> संचालन गैर-कम्यूटेटिव ग्राउंड क्षेत्र सामान्य अंकगणित और <math>\mathbb Z/2\mathbb Z</math> परिमित क्षेत्र मॉड 2 अंकगणित तक ही सीमित थे,। इस प्रकार सबसे अच्छा व्यावहारिक आव्यूह गुणन टेंसर का स्पष्ट निम्न-रैंक अपघटन कलनविधि O(n<sup>2.778</sup>) के रूप में पाया गया था <ref name="alphatensor">{{Cite journal |last1=Fawzi |first1=Alhussein |last2=Balog |first2=Matej |last3=Huang |first3=Aja |last4=Hubert |first4=Thomas |last5=Romera-Paredes |first5=Bernardino |last6=Barekatain |first6=Mohammadamin |last7=Novikov |first7=Alexander |last8=R. Ruiz |first8=Francisco J. |last9=Schrittwieser |first9=Julian |last10=Swirszcz |first10=Grzegorz |last11=Silver |first11=David |last12=Hassabis |first12=Demis |last13=Kohli |first13=Pushmeet |date=October 2022 |title=सुदृढीकरण सीखने के साथ तेज़ मैट्रिक्स गुणन एल्गोरिदम की खोज करना|journal=Nature |volume=610 |issue=7930 |pages=47–53 |doi=10.1038/s41586-022-05172-4 |pmid=36198780 |pmc=9534758 |bibcode=2022Natur.610...47F |issn=1476-4687}}</ref> ऐसे टेंसर और उससे आगे के निम्न-श्रेणी के अपघटन का पता लगाना NP कठिन है; इस प्रकार 3x3 आव्यूह के लिए भी ऑप्टीमल गुणन आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता क्रमविनिमेय क्षेत्र में भी गुणन की संख्या को न्यूनतम करना।<ref name="alphatensor"/> इस प्रकार 4x4 आव्यूह पर, अल्फ़ाटेन्सर ने अप्रत्याशित रूप से 47 गुणन चरणों के साथ एक समाधान खोजा था, जो 1969 के स्ट्रैसेन के कलनविधि के साथ आवश्यक 49 से अधिक सुधार हुआ था, चूंकि मॉड 2 अंकगणित तक सीमित था। इसी तरह, अल्फ़ाटेन्सर ने स्ट्रैसेन के 98 चरणों के अतिरिक्त 96 के साथ 5x5 आव्यूह को हल किया गया था । आश्चर्यजनक खोज के आधार पर कि इस तरह के सुधार उपस्थित हैं, अन्य शोधकर्ता तुरंत एक समान स्वतंत्र 4x4 कलनविधि ढूंढने में सक्षम थे और भिन्न से डीपमाइंड के 96-चरण 5x5 कलनविधि को मॉड 2 अंकगणित में 95 चरणों तक और 97 तक छोटा कर दिया था।<ref>{{Cite arXiv |last1=Kauers |first1=Manuel |last2=Moosbauer |first2=Jakob |date=2022-12-02 |title=मैट्रिक्स गुणन के लिए फ़्लिप ग्राफ़|class=cs.SC |eprint=2212.01175 }}</ref> सामान्य अंकगणित में.<ref>{{cite news |last1=Brubaker |first1=Ben |title=एआई मैट्रिक्स गुणन में नई संभावनाओं को प्रकट करता है|url=https://www.quantamagazine.org/ai-reveals-new-possibilities-in-matrix-multiplication-20221123/ |access-date=26 November 2022 |work=Quanta Magazine |date=23 November 2022 |language=en}}</ref> कुछ कलनविधि पहले कभी नहीं खोजे गए थे, उदाहरण (4, 5, 5) सामान्य और मॉड 2 अंकगणित में 80 से सुधरकर 76 हो गया था।
+में, [[डीपमाइंड]] ने अल्फ़ाटेनसर [[तंत्रिका नेटवर्क|न्यूरल नेटवर्क]] प्रस्तुत किया है, जिसने हजारों आव्यूह गुणन कलनविधि का आविष्कार करने के लिए एकल-प्लेयर गेम सादृश्य का उप समेशन किया, जिनमें से कुछ पहले मनुष्यों द्वारा खोजे गए थे और कुछ जो नहीं थे।<ref>{{Cite web |title=AlphaTensor के साथ नवीन एल्गोरिदम की खोज|url=https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor |access-date=2022-11-01 |website=www.deepmind.com |language=en}}</ref> संचालन गैर-कम्यूटेटिव ग्राउंड क्षेत्र सामान्य अंकगणित और <math>\mathbb Z/2\mathbb Z</math> परिमित क्षेत्र मॉड 2 अंकगणित तक ही सीमित थे,। इस प्रकार सबसे अच्छा व्यावहारिक आव्यूह गुणन टेंसर का स्पष्ट निम्न-रैंक अपघटन कलनविधि O(n<sup>2.778</sup>) के रूप में पाया गया था <ref name="alphatensor">{{Cite journal |last1=Fawzi |first1=Alhussein |last2=Balog |first2=Matej |last3=Huang |first3=Aja |last4=Hubert |first4=Thomas |last5=Romera-Paredes |first5=Bernardino |last6=Barekatain |first6=Mohammadamin |last7=Novikov |first7=Alexander |last8=R. Ruiz |first8=Francisco J. |last9=Schrittwieser |first9=Julian |last10=Swirszcz |first10=Grzegorz |last11=Silver |first11=David |last12=Hassabis |first12=Demis |last13=Kohli |first13=Pushmeet |date=October 2022 |title=सुदृढीकरण सीखने के साथ तेज़ मैट्रिक्स गुणन एल्गोरिदम की खोज करना|journal=Nature |volume=610 |issue=7930 |pages=47–53 |doi=10.1038/s41586-022-05172-4 |pmid=36198780 |pmc=9534758 |bibcode=2022Natur.610...47F |issn=1476-4687}}</ref> ऐसे टेंसर और उससे आगे के निम्न-श्रेणी के अपघटन का पता लगाना NP कठिन है; इस प्रकार 3x3 आव्यूह के लिए भी इष्टतम गुणन आव्यूह गुणन की अभिकलनात्मक सम्मिश्रता क्रमविनिमेय क्षेत्र में भी गुणन की संख्या को न्यूनतम करना।<ref name="alphatensor"/> इस प्रकार 4x4 आव्यूह पर, अल्फ़ाटेन्सर ने अप्रत्याशित रूप से 47 गुणन चरणों के साथ एक समाधान खोजा था, जो 1969 के स्ट्रैसेन के कलनविधि के साथ आवश्यक 49 से अधिक सुधार हुआ था, चूंकि मॉड 2 अंकगणित तक सीमित था। इसी तरह, अल्फ़ाटेन्सर ने स्ट्रैसेन के 98 चरणों के अतिरिक्त 96 के साथ 5x5 आव्यूह को हल किया गया था । आश्चर्यजनक खोज के आधार पर कि इस तरह के सुधार उपस्थित हैं, अन्य शोधकर्ता तुरंत एक समान स्वतंत्र 4x4 कलनविधि ढूंढने में सक्षम थे और भिन्न से डीपमाइंड के 96-चरण 5x5 कलनविधि को मॉड 2 अंकगणित में 95 चरणों तक और 97 तक छोटा कर दिया था।<ref>{{Cite arXiv |last1=Kauers |first1=Manuel |last2=Moosbauer |first2=Jakob |date=2022-12-02 |title=मैट्रिक्स गुणन के लिए फ़्लिप ग्राफ़|class=cs.SC |eprint=2212.01175 }}</ref> सामान्य अंकगणित में.<ref>{{cite news |last1=Brubaker |first1=Ben |title=एआई मैट्रिक्स गुणन में नई संभावनाओं को प्रकट करता है|url=https://www.quantamagazine.org/ai-reveals-new-possibilities-in-matrix-multiplication-20221123/ |access-date=26 November 2022 |work=Quanta Magazine |date=23 November 2022 |language=en}}</ref> कुछ कलनविधि पहले कभी नहीं खोजे गए थे, उदाहरण (4, 5, 5) सामान्य और मॉड 2 अंकगणित में 80 से सुधरकर 76 हो गया था।
 ==समानांतर और वितरित कलन विधि==
 ===साझा-मेमोरी समानता===
-#डिवाइड और क्न्क्वेर कलनविधि डिवाइड और क्न्क्वेर कलनविधि पहले स्केच किया गया [[साझा-मेमोरी मल्टीप्रोसेसर]] के लिए दो विधीयो से [[समानांतर एल्गोरिदम|समानांतर]] कलनविधि हो सकता है। ये इस तथ्य पर आधारित हैं कि आठ रिकर्सिव आव्यूह गुणन में इस प्रकार है
+#डिवाइड और क्न्क्वेर कलनविधि डिवाइड पहले से स्केच किया गया है और इस प्रकार [[साझा-मेमोरी मल्टीप्रोसेसर]] के लिए दो विधी के रूप में समानांतर कलनविधि के रूप में हो सकता है। ये इस तथ्य पर आधारित होता हैं कि आठ रिकर्सिव आव्यूह गुणन में इस प्रकार है
 :<math>\begin{pmatrix}
@@ Line 180: / Line 180: @@
 \end{pmatrix}
 </math>
-चार योगों की तरह, एक-दूसरे से स्वतंत्र रूप से निष्पादित किया जा सकता है, चूंकि कलनविधि को योग करने से पहले गुणन को जोड़ने की आवश्यकता होती है। इस प्रकार समस्या की पूर्ण समानता का उपयोग करते हुए कलनविधि प्राप्त होता है जिसे फोर्क-जॉइन मॉडल [[ छद्मकोड |पीसूडोकोड]] में व्यक्त किया जा सकता है:<ref name="cilk"/>
+चार समेशन की तरह, एक-दूसरे से स्वतंत्र रूप से निष्पादित किया जाता है, चूंकि कलनविधि को समेशन करने से पहले गुणन को जोड़ने की आवश्यकता होती है। इस प्रकार समस्या की पूर्ण समानता का उप समेशन करते हुए कलनविधि प्राप्त होता है जिसे फोर्क-जॉइन मॉडल [[ छद्मकोड |पीसूडोकोड]] में व्यक्त किया जा सकता है:<ref name="cilk"/>
 {{framebox|blue}}
@@ Line 220: / Line 220: @@
 यहां, फोर्क एक कीवर्ड है जो संकेत देता है कि गणना को शेष फलन कॉल के साथ समानांतर में चलाया जा सकता है, जबकि जॉइन पहले से फोर्क की गई सभी गणनाओं के पूरा होने की प्रतीक्षा करता है। विभाजन केवल सूचक हेरफेर द्वारा अपना लक्ष्य प्राप्त करता है।
-इस कलनविधि में {{math|Θ(log<sup>2</sup> ''n'')}} चरण एक महत्वपूर्ण पथ लंबाई है, जिसका अर्थ है कि अनंत संख्या में प्रोसेसर वाली एक आदर्श मशीन पर इतना समय लगता है; इसलिए, किसी भी वास्तविक कंप्यूटर पर इसकी अधिकतम संभव गति {{math|Θ(''n''<sup>3</sup>/log<sup>2</sup> ''n'')}} है, अस्थायी आव्यूह {{mvar|T}} से डेटा ले जाने में निहित संचार लागत के कारण कलनविधि व्यावहारिक नहीं है, लेकिन एक अधिक व्यावहारिक संस्करण अस्थायी आव्यूह का उपयोग किए बिना {{math|Θ(''n''<sup>2</sup>)}} स्पीडअप प्राप्त करता है।<ref name="cilk">{{cite thesis |type=Ph.D. |last=Randall |first=Keith H. |title=Cilk: Efficient Multithreaded Computing |publisher=Massachusetts Institute of Technology |year=1998 |pages=54–57 |url=http://supertech.csail.mit.edu/papers/randall-phdthesis.pdf |hdl=1721.1/47519}}</ref>
+इस कलनविधि में {{math|Θ(log<sup>2</sup> ''n'')}} चरण एक महत्वपूर्ण पथ लंबाई है, जिसका अर्थ है कि अनंत संख्या में प्रोसेसर वाली एक आदर्श मशीन पर इतना समय लगता है; इसलिए, किसी भी वास्तविक कंप्यूटर पर इसकी अधिकतम संभव गति {{math|Θ(''n''<sup>3</sup>/log<sup>2</sup> ''n'')}} है, अस्थायी आव्यूह {{mvar|T}} से डेटा ले जाने में निहित संचार लागत के कारण कलनविधि व्यावहारिक नहीं है, लेकिन एक अधिक व्यावहारिक संस्करण अस्थायी आव्यूह का उप समेशन किए बिना {{math|Θ(''n''<sup>2</sup>)}} स्पीडअप प्राप्त करता है।<ref name="cilk">{{cite thesis |type=Ph.D. |last=Randall |first=Keith H. |title=Cilk: Efficient Multithreaded Computing |publisher=Massachusetts Institute of Technology |year=1998 |pages=54–57 |url=http://supertech.csail.mit.edu/papers/randall-phdthesis.pdf |hdl=1721.1/47519}}</ref>
 [[File:Block matrix multiplication.svg|thumb|ब्लॉक आव्यूह गुणन. 2D कलनविधि में, प्रत्येक प्रोसेसर एक सबआव्यूह के लिए उत्तरदायी होता है {{mvar|C}}. 3D कलनविधि में, सबआव्यूह की प्रत्येक जोड़ी {{mvar|A}} और {{mvar|B}} जिसे गुणा किया जाता है उसे एक प्रोसेसर को सौंपा जाता है।]]
 ===संचार अवॉयड और डिस्ट्रिब्यूटेड कलन विधि===
-आधुनिक आर्किटेक्चर में हाइरार्की मेमोरी के साथ इनपुट आव्यूह तत्वों को लोड करने और संग्रहीत करने की लागत अंकगणित की लागत पर प्रभाव डालती है और इस प्रकार एक ही मशीन पर यह रैम और कैशे के बीच स्थानांतरित किए गए डेटा की मात्रा के रूप में होती है, जबकि एक डिस्ट्रिब्यूटेड मेमोरी मल्टी-नोड मशीन पर यह नोड्स के बीच स्थानांतरित की गई राशि के रूप में होती है और किसी भी स्थिति में इसे संचार बैंडविड्थ कहा जाता है। तीन नेस्टेड लूप का उपयोग करने वाला अनुभवहीन कलनविधि {{math|Ω(''n''<sup>3</sup>)}} संचार बैंडविड्थ.का उपयोग करता है
+आधुनिक आर्किटेक्चर में हाइरार्की मेमोरी के साथ इनपुट आव्यूह तत्वों को लोड करने और संग्रहीत करने की लागत अंकगणित की लागत पर प्रभाव डालती है और इस प्रकार एक ही मशीन पर यह रैम और कैशे के बीच स्थानांतरित किए गए डेटा की मात्रा के रूप में होती है, जबकि एक डिस्ट्रिब्यूटेड मेमोरी मल्टी-नोड मशीन पर यह नोड्स के बीच स्थानांतरित की गई राशि के रूप में होती है और किसी भी स्थिति में इसे संचार बैंडविड्थ कहा जाता है। तीन नेस्टेड लूप का उप समेशन करने वाला अनुभवहीन कलनविधि {{math|Ω(''n''<sup>3</sup>)}} संचार बैंडविड्थ.का उप समेशन करता है
-कैनन का कलन विधि , जिसे 2D कलनविधि के रूप में भी जाना जाता है, एक [[संचार से बचने वाला एल्गोरिदम|संचार से अवॉयड]] कलनविधि जो प्रत्येक इनपुट आव्यूह को एक ब्लॉक आव्यूह में विभाजित करता है जिसके तत्व के आकार {{math|{{sqrt|''M''/3}}}} द्वारा {{math|{{sqrt|''M''/3}}}} के रूप में सबआव्यूह होते हैं जहाँ {{math|''M''}} फ़ास्ट ी से मेमोरी का आकार है।<ref>{{cite thesis |first=Lynn Elliot |last=Cannon |title=कलमन फ़िल्टर एल्गोरिथम को लागू करने के लिए एक सेलुलर कंप्यूटर|date=14 July 1969 |type=Ph.D. |publisher=Montana State University |url=https://dl.acm.org/doi/abs/10.5555/905686 }}</ref> इसके बाद अनुभवहीन कलनविधि का उपयोग ब्लॉक मैट्रिसेस पर किया जाता है, जो पूरी तरह से फ़ास्ट मेमोरी में सबमैट्रिसेस के गुणन की गणना करता है। इससे संचार बैंडविड्थ को {{math|''O''(''n''<sup>3</sup>/{{sqrt|''M''}})}} तक कम कर देता है, जो असिम्प्टोटिकालीय रूप से ऑप्टीमल है {{math|Ω(''n''<sup>3</sup>)}} है।<ref>{{cite journal|last1=Hong|first1=J. W.|first2=H. T. |last2=Kung|title=I/O complexity: The red-blue pebble game|journal=STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing|year=1981|pages=326–333|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a104739.pdf|archive-url=https://web.archive.org/web/20191215182754/https://apps.dtic.mil/dtic/tr/fulltext/u2/a104739.pdf|url-status=live|archive-date=December 15, 2019 |doi=10.1145/800076.802486|s2cid=8410593 }}</ref><ref name=irony>{{cite journal|last1=Irony|first1=Dror|first2=Sivan |last2=Toledo |first3=Alexander |last3=Tiskin |title=वितरित-मेमोरी मैट्रिक्स गुणन के लिए संचार निचली सीमाएं|journal=J. Parallel Distrib. Comput.|date=September 2004|volume=64|issue=9|pages=1017–26|doi=10.1016/j.jpdc.2004.03.021|citeseerx=10.1.1.20.7034}}</ref>
+कैनन का कलन विधि , जिसे 2D कलनविधि के रूप में भी जाना जाता है, एक [[संचार से बचने वाला एल्गोरिदम|संचार से अवॉयड]] कलनविधि जो प्रत्येक इनपुट आव्यूह को एक ब्लॉक आव्यूह में विभाजित करता है जिसके तत्व के आकार {{math|{{sqrt|''M''/3}}}} द्वारा {{math|{{sqrt|''M''/3}}}} के रूप में सबआव्यूह होते हैं जहाँ {{math|''M''}} फ़ास्ट ी से मेमोरी का आकार है।<ref>{{cite thesis |first=Lynn Elliot |last=Cannon |title=कलमन फ़िल्टर एल्गोरिथम को लागू करने के लिए एक सेलुलर कंप्यूटर|date=14 July 1969 |type=Ph.D. |publisher=Montana State University |url=https://dl.acm.org/doi/abs/10.5555/905686 }}</ref> इसके बाद अनुभवहीन कलनविधि का उप समेशन ब्लॉक मैट्रिसेस पर किया जाता है, जो पूरी तरह से फ़ास्ट मेमोरी में सबमैट्रिसेस के गुणन की गणना करता है। इससे संचार बैंडविड्थ को {{math|''O''(''n''<sup>3</sup>/{{sqrt|''M''}})}} तक कम कर देता है, जो असिम्प्टोटिकालीय रूप से इष्टतम है {{math|Ω(''n''<sup>3</sup>)}} है।<ref>{{cite journal|last1=Hong|first1=J. W.|first2=H. T. |last2=Kung|title=I/O complexity: The red-blue pebble game|journal=STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing|year=1981|pages=326–333|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a104739.pdf|archive-url=https://web.archive.org/web/20191215182754/https://apps.dtic.mil/dtic/tr/fulltext/u2/a104739.pdf|url-status=live|archive-date=December 15, 2019 |doi=10.1145/800076.802486|s2cid=8410593 }}</ref><ref name=irony>{{cite journal|last1=Irony|first1=Dror|first2=Sivan |last2=Toledo |first3=Alexander |last3=Tiskin |title=वितरित-मेमोरी मैट्रिक्स गुणन के लिए संचार निचली सीमाएं|journal=J. Parallel Distrib. Comput.|date=September 2004|volume=64|issue=9|pages=1017–26|doi=10.1016/j.jpdc.2004.03.021|citeseerx=10.1.1.20.7034}}</ref>
-वितरित सेटिंग में, {{math|{{sqrt|''p''}}}} 2D मेशेस द्वारा {{math|{{sqrt|''p''}}}} में व्यवस्थित P प्रोसेसरों में परिणाम का एक सबआव्यूह प्रत्येक प्रोसेसर को सौंपा जाता है और प्रत्येक {{math|''O''(''n''<sup>2</sup>/{{sqrt|''p''}})}} शब्द प्रोसेसर ट्रांसमिटिंग के साथ गुणन की गणना की जा सकती है जो कि असम्बद्ध रूप से ऑप्टीमल है, यह मानते हुए कि प्रत्येक नोड न्यूनतम {{math|''O''(''n''<sup>2</sup>/''p'')}} तत्वसंग्रहीत करता है.<ref name="irony" />इसे 3D कलनविधि द्वारा अच्छे से बनाया जा सकता है, जो प्रोसेसर को 3D क्यूब मेशेस में व्यवस्थित करता है और इस प्रकार दो इनपुट सबमैट्रिसेस के प्रत्येक गुणन को एक ही प्रोसेसर को निर्दिष्ट करता है। फिर प्रत्येक पंक्ति पर कमी करके परिणाम सबमैट्रिस के रूप में उत्पन्न किए जाते हैं।<ref name="Agarwal">{{cite journal|last1=Agarwal|first1=R.C.|first2=S. M. |last2=Balle |first3=F. G. |last3=Gustavson |first4=M. |last4=Joshi |first5=P. |last5=Palkar |title=समानांतर मैट्रिक्स गुणन के लिए एक त्रि-आयामी दृष्टिकोण|journal=IBM J. Res. Dev.|date=September 1995|volume=39|issue=5|pages=575–582|doi=10.1147/rd.395.0575|citeseerx=10.1.1.44.3404}}</ref> यह कलनविधि प्रति प्रोसेसर {{math|''O''(''n''<sup>2</sup>/''p''<sup>2/3</sup>)}} शब्दों को संचारित करता है जो कि असम्बद्ध रूप से ऑप्टीमल है।<ref name="irony" />चूंकि, इसके लिए प्रत्येक इनपुट आव्यूह तत्व {{math|''p''<sup>1/3</sup>}} बार दोहराने की आवश्यकता होती है और इसलिए इनपुट को संग्रहीत करने के लिए आवश्यकता से अधिक {{math|''p''<sup>1/3</sup>}} मेमोरी की आवश्यकता होती है। इस कलनविधि के रनटाइम को कम करने के लिए स्ट्रैसेन के साथ जोड़ा जा सकता है।<ref name="Agarwal" /> 2.5D कलनविधि मेमोरी उपयोग और संचार बैंडविड्थ के बीच एक निरंतर ट्रेडऑफ़ प्रदान करता है।<ref>{{cite conference|last1=Solomonik|first1=Edgar|first2=James |last2=Demmel|title=Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms|book-title=Proceedings of the 17th International Conference on Parallel Processing|year=2011|volume=Part II|pages=90–109 |doi=10.1007/978-3-642-23397-5_10 |isbn=978-3-642-23397-5 |url=https://solomonik.cs.illinois.edu/talks/europar-sep-2011.pdf}}</ref> [[MapReduce|मैप रेडूस]] जैसे आधुनिक वितरित अभिकलन वातावरण पर, विशेष गुणन कलनविधि विकसित किए गए हैं।<ref>{{cite web |last1=Bosagh Zadeh|first1=Reza|last2=Carlsson|first2=Gunnar|title=MapReduce का उपयोग करके आयाम स्वतंत्र मैट्रिक्स स्क्वायर|year=2013|arxiv=1304.1467|bibcode=2013arXiv1304.1467B|url=https://stanford.edu/~rezab/papers/dimsum.pdf|access-date=12 July 2014}}</ref>
+वितरित सेटिंग में, {{math|{{sqrt|''p''}}}} 2D मेशेस द्वारा {{math|{{sqrt|''p''}}}} में व्यवस्थित P प्रोसेसरों में परिणाम का एक सबआव्यूह प्रत्येक प्रोसेसर को सौंपा जाता है और प्रत्येक {{math|''O''(''n''<sup>2</sup>/{{sqrt|''p''}})}} शब्द प्रोसेसर ट्रांसमिटिंग के साथ गुणन की गणना की जा सकती है जो कि असम्बद्ध रूप से इष्टतम है, यह मानते हुए कि प्रत्येक नोड न्यूनतम {{math|''O''(''n''<sup>2</sup>/''p'')}} तत्वसंग्रहीत करता है.<ref name="irony" />इसे 3D कलनविधि द्वारा अच्छे से बनाया जा सकता है, जो प्रोसेसर को 3D क्यूब मेशेस में व्यवस्थित करता है और इस प्रकार दो इनपुट सबमैट्रिसेस के प्रत्येक गुणन को एक ही प्रोसेसर को निर्दिष्ट करता है। फिर प्रत्येक पंक्ति पर कमी करके परिणाम सबमैट्रिस के रूप में उत्पन्न किए जाते हैं।<ref name="Agarwal">{{cite journal|last1=Agarwal|first1=R.C.|first2=S. M. |last2=Balle |first3=F. G. |last3=Gustavson |first4=M. |last4=Joshi |first5=P. |last5=Palkar |title=समानांतर मैट्रिक्स गुणन के लिए एक त्रि-आयामी दृष्टिकोण|journal=IBM J. Res. Dev.|date=September 1995|volume=39|issue=5|pages=575–582|doi=10.1147/rd.395.0575|citeseerx=10.1.1.44.3404}}</ref> यह कलनविधि प्रति प्रोसेसर {{math|''O''(''n''<sup>2</sup>/''p''<sup>2/3</sup>)}} शब्दों को संचारित करता है जो कि असम्बद्ध रूप से इष्टतम है।<ref name="irony" />चूंकि, इसके लिए प्रत्येक इनपुट आव्यूह तत्व {{math|''p''<sup>1/3</sup>}} बार दोहराने की आवश्यकता होती है और इसलिए इनपुट को संग्रहीत करने के लिए आवश्यकता से अधिक {{math|''p''<sup>1/3</sup>}} मेमोरी की आवश्यकता होती है। इस कलनविधि के रनटाइम को कम करने के लिए स्ट्रैसेन के साथ जोड़ा जा सकता है।<ref name="Agarwal" /> 2.5D कलनविधि मेमोरी उप समेशन और संचार बैंडविड्थ के बीच एक निरंतर ट्रेडऑफ़ प्रदान करता है।<ref>{{cite conference|last1=Solomonik|first1=Edgar|first2=James |last2=Demmel|title=Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms|book-title=Proceedings of the 17th International Conference on Parallel Processing|year=2011|volume=Part II|pages=90–109 |doi=10.1007/978-3-642-23397-5_10 |isbn=978-3-642-23397-5 |url=https://solomonik.cs.illinois.edu/talks/europar-sep-2011.pdf}}</ref> [[MapReduce|मैप रेडूस]] जैसे आधुनिक वितरित अभिकलन वातावरण पर, विशेष गुणन कलनविधि विकसित किए गए हैं।<ref>{{cite web |last1=Bosagh Zadeh|first1=Reza|last2=Carlsson|first2=Gunnar|title=MapReduce का उपयोग करके आयाम स्वतंत्र मैट्रिक्स स्क्वायर|year=2013|arxiv=1304.1467|bibcode=2013arXiv1304.1467B|url=https://stanford.edu/~rezab/papers/dimsum.pdf|access-date=12 July 2014}}</ref>
 ===मेशेस कलन विधि ===
-[[File:Matrix multiplication on a cross-wire two-dimensional array.png|thumb|240px|क्रॉस-वायर्ड मेशेस पर दो n×n आव्यूह के लिए आव्यूह गुणन 2n-1 चरणों में पूरा होता है।]][[ जाल नेटवर्किंग | मेशेस नेटवर्किंग]] पर गुणन के लिए विभिन्न प्रकार के कलनविधि हैं। 2D कैनन के कलनविधि का उपयोग करके एक मानक द्वि-आयामी मेशेस पर दो n×n के गुणन के लिए कोई 3n-2 चरणों में गुणन को पूरा कर सकता है, चूंकि बार-बार की गणना के लिए यह संख्या आधी हो जाती है।<ref>{{cite journal | last1 = Bae | first1 = S.E. | last2 = Shinn | first2 = T.-W. | last3 = Takaoka | first3 = T. | year = 2014 | title = जाल सरणी पर मैट्रिक्स गुणन के लिए एक तेज़ समानांतर एल्गोरिदम| url = https://www.sciencedirect.com/science/article/pii/S1877050914003858/pdf  | journal = Procedia Computer Science | volume = 29 | pages = 2230–40 | doi = 10.1016/j.procs.2014.05.208 | doi-access = free }}</ref> इस प्रकार मानक सरणी अक्षम है क्योंकि दो आव्यूह से डेटा एक साथ नहीं आता है और इसे शून्य के साथ पैडेड होना चाहिए।
+[[File:Matrix multiplication on a cross-wire two-dimensional array.png|thumb|240px|क्रॉस-वायर्ड मेशेस पर दो n×n आव्यूह के लिए आव्यूह गुणन 2n-1 चरणों में पूरा होता है।]][[ जाल नेटवर्किंग | मेशेस नेटवर्किंग]] पर गुणन के लिए विभिन्न प्रकार के कलनविधि हैं। 2D कैनन के कलनविधि का उप समेशन करके एक मानक द्वि-आयामी मेशेस पर दो n×n के गुणन के लिए कोई 3n-2 चरणों में गुणन को पूरा कर सकता है, चूंकि बार-बार की गणना के लिए यह संख्या आधी हो जाती है।<ref>{{cite journal | last1 = Bae | first1 = S.E. | last2 = Shinn | first2 = T.-W. | last3 = Takaoka | first3 = T. | year = 2014 | title = जाल सरणी पर मैट्रिक्स गुणन के लिए एक तेज़ समानांतर एल्गोरिदम| url = https://www.sciencedirect.com/science/article/pii/S1877050914003858/pdf  | journal = Procedia Computer Science | volume = 29 | pages = 2230–40 | doi = 10.1016/j.procs.2014.05.208 | doi-access = free }}</ref> इस प्रकार मानक सरणी अक्षम है क्योंकि दो आव्यूह से डेटा एक साथ नहीं आता है और इसे शून्य के साथ पैडेड होना चाहिए।
 परिणाम दो-परत क्रॉस-वायर्ड मेशेस पर और भी फ़ास्ट ़ है, जहां केवल 2n-1 चरणों की आवश्यकता होती है।<ref>{{cite journal | last1 = Kak | first1 = S | year = 1988 | title = मैट्रिक्स गुणन के लिए एक दो-परत जाल सरणी| journal = Parallel Computing | volume = 6 | issue = 3| pages = 383–5 | doi = 10.1016/0167-8191(88)90078-6 | citeseerx = 10.1.1.88.8527 }}</ref> इस प्रकार बार-बार गणना करने पर प्रदर्शन में और सुधार होता है जिससे 100% दक्षता प्राप्त होती है।<ref>{{cite arXiv |last=Kak |first=S. |date=2014 |title=क्रॉस-वायर्ड जाल सरणी पर मैट्रिक्स गुणन की दक्षता|class=cs.DC |eprint=1411.3273}}</ref> और क्रॉस-वायर्ड मेशेस सरणी को गैर-प्लानर (अर्थात बहुपरत) प्रसंस्करण संरचना के एक विशेष स्थिति के रूप में देखा जा सकता है।<ref>{{cite journal | last1 = Kak | first1 = S | year = 1988 | title = बहुस्तरीय सरणी कंप्यूटिंग| journal = Information Sciences | volume = 45 | issue = 3| pages = 347–365 | doi = 10.1016/0020-0255(88)90010-2 | citeseerx = 10.1.1.90.4753 }}</ref>
@@ Line 255: / Line 255: @@
 {{Numerical linear algebra}}
-[[Category: संख्यात्मक रैखिक बीजगणित]] [[Category: मैट्रिक्स सिद्धांत]] [[Category: मैट्रिक्स गुणन एल्गोरिदम| मैट्रिक्स गुणन एल्गोरिदम]] [[Category: स्यूडोकोड उदाहरण सहित लेख]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:Collapse templates]]
 [[Category:Created On 25/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:मैट्रिक्स गुणन एल्गोरिदम| मैट्रिक्स गुणन एल्गोरिदम]]
+[[Category:मैट्रिक्स सिद्धांत]]
+[[Category:संख्यात्मक रैखिक बीजगणित]]
+[[Category:स्यूडोकोड उदाहरण सहित लेख]]

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

Latest revision as of 09:56, 23 August 2023

Contents

पुनरावृत्तीय कलनविधि

कैशे व्यवहार

डिवाइड और क्न्क्वेर कलनविधि

गैर-वर्ग आव्यूह

कैशे व्यवहार

उप-घन कलन विधि

अल्फा टेन्सर

समानांतर और वितरित कलन विधि

साझा-मेमोरी समानता

संचार अवॉयड और डिस्ट्रिब्यूटेड कलन विधि

मेशेस कलन विधि

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

आव्यूह गुणन कलनविधि (एल्गोरिथ्म): Difference between revisions

Latest revision as of 09:56, 23 August 2023

पुनरावृत्तीय कलनविधि

कैशे व्यवहार

डिवाइड और क्न्क्वेर कलनविधि

गैर-वर्ग आव्यूह

कैशे व्यवहार

उप-घन कलन विधि

अल्फा टेन्सर

समानांतर और वितरित कलन विधि

साझा-मेमोरी समानता

संचार अवॉयड और डिस्ट्रिब्यूटेड कलन विधि

मेशेस कलन विधि

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories