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

Revision as of 00:46, 8 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$ , नेस्टेड लूप का उपयोग करके उपरोक्त की गणना की जा सकती है

इनपुट: मैट्रिसेस $A$ और $B$
माना $C$ उचित आकार का एक नया मैट्रिक्स बनें
के लिए i 1 से n:
- के लिए j 1 से p:
  - होने देना $sum = 0$
  - के लिए k 1 से m:
    - तय करना $sum \leftarrow sum + A ik \times B kj$
  - तय करना $C ij \leftarrow sum$
वापस करना $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]और कई पुस्तकालयों में दिखाई देता है, जैसे कि बुनियादी रैखिक बीजगणित उपप्रोग्राम^[10] यह परिमित क्षेत्रों जैसे सटीक डोमेन पर बड़े आव्यूह के लिए बहुत उपयोगी है, जहां संख्यात्मक स्थिरता कोई समस्या नहीं है।

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

अल्फाटेन्सर

2022 में, डीपमाइंड ने अल्फ़ाटेनसर पेश किया, जो एक तंत्रिका नेटवर्क है, जिसने हजारों आव्यूह गुणन कलनविधि का आविष्कार करने के लिए एकल-खिलाड़ी गेम सादृश्य का उपयोग किया, जिनमें से कुछ पहले मनुष्यों द्वारा खोजे गए थे और कुछ जो नहीं थे।^[14] संचालन गैर-कम्यूटेटिव ग्राउंड क्षेत्र (सामान्य अंकगणित) और GF(2)|परिमित क्षेत्र तक ही सीमित थे $\mathbb {Z} /2\mathbb {Z}$ (मॉड 2 अंकगणित)। सबसे अच्छा व्यावहारिक (आव्यूह गुणन टेंसर का स्पष्ट निम्न-रैंक अपघटन) कलनविधि O(n) में पाया गया^2.778).^[15] ऐसे टेंसर (और उससे आगे) के निम्न-श्रेणी के अपघटन का पता लगाना एनपी-कठिन है; 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)$ .
- जोड़ना।

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

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

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

C

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

A

और

B

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

संचार से बचाव और वितरित एल्गोरिदम

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

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

जाल के लिए एल्गोरिदम

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

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

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

यह भी देखें

गणितीय संक्रियाओं की कम्प्यूटेशनल जटिलता
आव्यूह गुणन की कम्प्यूटेशनल जटिलता
CYK एल्गोरिथम#वैलिएंट्स एल्गोरिथम|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 2: / Line 2: @@
 [[मैट्रिक्स गुणन|आव्यूह गुणन]] कई संख्यात्मक कलनविधि में एक ऐसा केंद्रीय ऑपरेशन होता है, अतः आव्यूह गुणन कलनविधि को कुशल बनाने में बहुत काम का निवेश किया गया है। इस प्रकार कम्प्यूटेशनल समस्याओं में आव्यूह गुणन के अनुप्रयोग [[वैज्ञानिक कंप्यूटिंग]] और पैटर्न रिकॉग्नाइजेसन सहित कई क्षेत्रों में संभवतः प्रतीत होने वाली असंबंधित समस्याओं के रूप में पाए जाते हैं और ग्राफ के माध्यम से पथों की गिनती होती है।<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 26: / Line 26: @@
 }}</ref><ref name="quanta">{{Cite web|last=Hartnett|first=Kevin|title=मैट्रिक्स गुणन इंच पौराणिक लक्ष्य के करीब|url=https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/|access-date=2021-04-01|website=Quanta Magazine|date=23 March 2021 |language=en}}</ref> चूंकि, यह कलनविधि बड़े स्थिरांक के कारण एक [[गैलेक्टिक एल्गोरिदम|गैलेक्टिक]] कलनविधि के रूप में होती है और इसे व्यावहारिक रूप से महसूस नहीं किया जा सकता है।
-==पुनरावृत्त कलनविधि ==
+==इटरेटिव कलनविधि ==
 आव्यूह गुणान परिभाषा यह है कि यदि {{math|''C'' {{=}} ''AB''}} एक के लिए {{math|''n'' × ''m''}} आव्यूह {{mvar|A}} और एक {{math|''m'' × ''p''}} आव्यूह {{mvar|B}}, तब {{mvar|C}} एक {{math|''n'' × ''p''}} प्रविष्टियों के साथ मैट्रिक्स के रूप में होता है
@@ Line 45: / Line 45: @@
 यह कलनविधि [[एसिम्प्टोटिक नोटेशन]] में समय {{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>)}} सबसे खराब स्थिति में कैश छूट जाता है। {{As of|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 69: / Line 69: @@
 {{frame-footer}}
-आदर्शीकृत कैश मॉडल में, यह कलनविधि केवल प्रयुक्त होता है {{math|Θ({{sfrac|''n''<sup>3</sup>|''b'' {{radic|''M''}}}})}} कैश चूक गया; भाजक {{math|''b'' {{radic|''M''}}}} आधुनिक मशीनों पर परिमाण के कई आदेशों के बराबर है, ताकि कैश छूटने के बजाय वास्तविक गणना चलने के समय पर हावी हो जाए।<ref name="ocw"/>
+आदर्शीकृत कैशे  मॉडल में, यह कलनविधि केवल प्रयुक्त होता है {{math|Θ({{sfrac|''n''<sup>3</sup>|''b'' {{radic|''M''}}}})}} कैशे  चूक गया; भाजक {{math|''b'' {{radic|''M''}}}} आधुनिक मशीनों पर परिमाण के कई आदेशों के बराबर है, ताकि कैशे  छूटने के अतिरिक्त वास्तविक गणना रनिंग  समय पर प्रभावी  हो जाए।<ref name="ocw"/>
 ==[[फूट डालो और जीतो एल्गोरिथ्म|फूट डालो और जीतो कलनविधि]] ==
-पुनरावृत्त कलनविधि का एक विकल्प आव्यूह गुणन के लिए फूट डालो और जीतो कलनविधि है। यह [[ब्लॉक मैट्रिक्स|ब्लॉक]] आव्यूह पर निर्भर करता है
+इटरेटिव कलनविधि का एक विकल्प आव्यूह गुणन के लिए फूट डालो और जीतो कलनविधि है। यह [[ब्लॉक मैट्रिक्स|ब्लॉक]] आव्यूह पर निर्भर करता है
 :<math>C = \begin{pmatrix}
@@ Line 106: / Line 106: @@
 जिसमें उपमैट्रिस के युग्मों के आठ गुणन होते हैं, जिसके बाद एक अतिरिक्त चरण होता है। फूट डालो और जीतो कलनविधि अदिश गुणन का उपयोग करके छोटे गुणन [[प्रत्यावर्तन]] की गणना करता है {{math|''c''<sub>11</sub> {{=}} ''a''<sub>11</sub>''b''<sub>11</sub>}} इसके आधार मामले के रूप में।
-एक फ़ंक्शन के रूप में इस कलनविधि की जटिलता {{mvar|n}} पुनरावृत्ति द्वारा दिया जाता है<ref name="clrs"/>
+एक फ़ंक्शन के रूप में इस कलनविधि की जटिलता {{mvar|n}} इटरेशन द्वारा दिया जाता है<ref name="clrs"/>
 :<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>
+इस कलनविधि का एक प्रकार जो यादृच्छिक आकार के आव्यूह के लिए काम करता है और व्यवहार में तेज़ है<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>
-आव्यूह को विभाजित करने का मतलब अब इसे समान आकार के दो भागों में विभाजित करना है, या विषम आयामों के मामले में जितना संभव हो सके समान आकार के करीब विभाजित करना है।
+आव्यूह को विभाजित करने का अर्थ अब इसे समान आकार के दो भागों में विभाजित करना है, या विषम आयामों के मामले में जितना संभव हो सके समान आकार के करीब विभाजित करना है।
 {{framebox|blue}}
@@ Line 137: / Line 137: @@
 {{frame-footer}}
-===कैश व्यवहार===
+===कैशे  व्यवहार===
-पुनरावर्ती आव्यूह गुणन की कैश मिस दर लूप टाइलिंग पुनरावृत्त संस्करण के समान है, लेकिन उस कलनविधि के विपरीत, पुनरावर्ती कलनविधि [[कैश-विस्मृत एल्गोरिथ्म|कैश-विस्मृत]] कलनविधि है|कैश-ओब्लिवियस:<ref name="prokop"/>इष्टतम कैश प्रदर्शन प्राप्त करने के लिए कोई ट्यूनिंग पैरामीटर आवश्यक नहीं है, और यह [[ बहु क्रमादेशन ]] वातावरण में अच्छा व्यवहार करता है जहां कैश स्थान लेने वाली अन्य प्रक्रियाओं के कारण कैश आकार प्रभावी रूप से गतिशील होते हैं।<ref name="ocw"/>(सरल पुनरावृत्त कलनविधि कैश-विस्मृत भी है, लेकिन यदि आव्यूह लेआउट कलनविधि के लिए अनुकूलित नहीं है तो व्यवहार में बहुत धीमा है।)
+पुनरावर्ती आव्यूह गुणन की कैशे  मिस दर लूप टाइलिंग इटरेटिव संस्करण के समान है, लेकिन उस कलनविधि के विपरीत, पुनरावर्ती कलनविधि [[कैश-विस्मृत एल्गोरिथ्म|कैशे -विस्मृत]] कलनविधि है|कैशे -ओब्लिवियस:<ref name="prokop"/>ऑप्टीमल  कैशे  प्रदर्शन प्राप्त करने के लिए कोई ट्यूनिंग पैरामीटर आवश्यक नहीं है, और यह [[ बहु क्रमादेशन ]] वातावरण में अच्छा व्यवहार करता है जहां कैशे  स्थान लेने वाली अन्य प्रक्रियाओं के कारण कैशे  आकार प्रभावी रूप से गतिशील होते हैं।<ref name="ocw"/>(सरल इटरेटिव कलनविधि कैशे -विस्मृत भी है, लेकिन यदि आव्यूह लेआउट कलनविधि के लिए अनुकूलित नहीं है तो व्यवहार में बहुत धीमा है।)
-इस कलनविधि द्वारा किसी मशीन पर कैश मिस होने की संख्या {{mvar|M}} आदर्श कैश की पंक्तियाँ, प्रत्येक आकार की {{mvar|b}} बाइट्स, से घिरा है{{r|prokop}}{{rp|13}}
+इस कलनविधि द्वारा किसी मशीन पर कैशे  मिस होने की संख्या {{mvar|M}} आदर्श कैशे  की पंक्तियाँ, प्रत्येक आकार की {{mvar|b}} बाइट्स, से घिरा है{{r|prokop}}{{rp|13}}
 :<math>\Theta \left(m + n + p + \frac{mn + np + mp}{b} + \frac{mnp}{b\sqrt{M}} \right)</math>
@@ Line 173: / Line 173: @@
 === अल्फाटेन्सर ===
-में, [[डीपमाइंड]] ने अल्फ़ाटेनसर पेश किया, जो एक [[तंत्रिका नेटवर्क]] है, जिसने हजारों आव्यूह गुणन कलनविधि का आविष्कार करने के लिए एकल-खिलाड़ी गेम सादृश्य का उपयोग किया, जिनमें से कुछ पहले मनुष्यों द्वारा खोजे गए थे और कुछ जो नहीं थे।<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> संचालन गैर-कम्यूटेटिव ग्राउंड क्षेत्र (सामान्य अंकगणित) और GF(2)|परिमित क्षेत्र तक ही सीमित थे <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> ऐसे टेंसर (और उससे आगे) के निम्न-श्रेणी के अपघटन का पता लगाना एनपी-कठिन है; 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> संचालन गैर-कम्यूटेटिव ग्राउंड क्षेत्र (सामान्य अंकगणित) और GF(2)|परिमित क्षेत्र तक ही सीमित थे <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> ऐसे टेंसर (और उससे आगे) के निम्न-श्रेणी के अपघटन का पता लगाना एनपी-कठिन है; 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 हो गया।
 ==समानांतर और वितरित एल्गोरिदम==
@@ Line 230: / Line 230: @@
 ===संचार से बचाव और वितरित एल्गोरिदम===
-पदानुक्रमित मेमोरी वाले आधुनिक आर्किटेक्चर पर, इनपुट आव्यूह तत्वों को लोड करने और संग्रहीत करने की लागत अंकगणित की लागत पर हावी हो जाती है। एक मशीन पर यह रैम और कैश के बीच स्थानांतरित किए गए डेटा की मात्रा है, जबकि एक वितरित मेमोरी मल्टी-नोड मशीन पर यह नोड्स के बीच स्थानांतरित की गई राशि है; किसी भी स्थिति में इसे संचार बैंडविड्थ कहा जाता है। तीन नेस्टेड लूप का उपयोग करने वाला भोला कलनविधि उपयोग करता है {{math|Ω(''n''<sup>3</sup>)}} संचार बैंडविड्थ.
+पदानुक्रमित मेमोरी वाले आधुनिक आर्किटेक्चर पर, इनपुट आव्यूह तत्वों को लोड करने और संग्रहीत करने की लागत अंकगणित की लागत पर प्रभावी  हो जाती है। एक मशीन पर यह रैम और कैशे  के बीच स्थानांतरित किए गए डेटा की मात्रा है, जबकि एक वितरित मेमोरी मल्टी-नोड मशीन पर यह नोड्स के बीच स्थानांतरित की गई राशि है; किसी भी स्थिति में इसे संचार बैंडविड्थ कहा जाता है। तीन नेस्टेड लूप का उपयोग करने वाला भोला कलनविधि उपयोग करता है {{math|Ω(''n''<sup>3</sup>)}} संचार बैंडविड्थ.
-कैनन का एल्गोरिदम, जिसे 2डी कलनविधि के रूप में भी जाना जाता है, एक [[संचार से बचने वाला एल्गोरिदम|संचार से बचने वाला]] कलनविधि है जो प्रत्येक इनपुट आव्यूह को एक ब्लॉक आव्यूह में विभाजित करता है जिसके तत्व आकार के उपआव्यूह होते हैं {{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>
+कैनन का एल्गोरिदम, जिसे 2डी कलनविधि के रूप में भी जाना जाता है, एक [[संचार से बचने वाला एल्गोरिदम|संचार से बचने वाला]] कलनविधि है जो प्रत्येक इनपुट आव्यूह को एक ब्लॉक आव्यूह में विभाजित करता है जिसके तत्व आकार के उपआव्यूह होते हैं {{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>
-के साथ एक वितरित सेटिंग में {{mvar|p}} प्रोसेसर एक में व्यवस्थित {{math|{{sqrt|''p''}}}} द्वारा {{math|{{sqrt|''p''}}}} 2डी जाल, परिणाम का एक सबआव्यूह प्रत्येक प्रोसेसर को सौंपा जा सकता है, और प्रत्येक प्रोसेसर ट्रांसमिटिंग के साथ उत्पाद की गणना की जा सकती है {{math|''O''(''n''<sup>2</sup>/{{sqrt|''p''}})}} शब्द, जो कि असम्बद्ध रूप से इष्टतम है, यह मानते हुए कि प्रत्येक नोड न्यूनतम संग्रहीत करता है {{math|''O''(''n''<sup>2</sup>/''p'')}}तत्व.<ref name=irony/>इसे 3डी कलनविधि द्वारा अच्छे बनाया जा सकता है, जो प्रोसेसर को 3डी क्यूब जाल में व्यवस्थित करता है, दो इनपुट सबमैट्रिसेस के प्रत्येक उत्पाद को एक ही प्रोसेसर को निर्दिष्ट करता है। फिर प्रत्येक पंक्ति पर कमी करके परिणाम सबमैट्रिस उत्पन्न किए जाते हैं।<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>
+के साथ एक वितरित सेटिंग में {{mvar|p}} प्रोसेसर एक में व्यवस्थित {{math|{{sqrt|''p''}}}} द्वारा {{math|{{sqrt|''p''}}}} 2डी जाल, परिणाम का एक सबआव्यूह प्रत्येक प्रोसेसर को सौंपा जा सकता है, और प्रत्येक प्रोसेसर ट्रांसमिटिंग के साथ उत्पाद की गणना की जा सकती है {{math|''O''(''n''<sup>2</sup>/{{sqrt|''p''}})}} शब्द, जो कि असम्बद्ध रूप से ऑप्टीमल  है, यह मानते हुए कि प्रत्येक नोड न्यूनतम संग्रहीत करता है {{math|''O''(''n''<sup>2</sup>/''p'')}}तत्व.<ref name=irony/>इसे 3डी कलनविधि द्वारा अच्छे बनाया जा सकता है, जो प्रोसेसर को 3डी क्यूब जाल में व्यवस्थित करता है, दो इनपुट सबमैट्रिसेस के प्रत्येक उत्पाद को एक ही प्रोसेसर को निर्दिष्ट करता है। फिर प्रत्येक पंक्ति पर कमी करके परिणाम सबमैट्रिस उत्पन्न किए जाते हैं।<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>

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 00:46, 8 August 2023

Contents

इटरेटिव कलनविधि

कैशे व्यवहार

फूट डालो और जीतो कलनविधि

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

कैशे व्यवहार

उप-घन एल्गोरिदम

अल्फाटेन्सर

समानांतर और वितरित एल्गोरिदम

साझा-स्मृति समानता

संचार से बचाव और वितरित एल्गोरिदम

जाल के लिए एल्गोरिदम

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 00:46, 8 August 2023

इटरेटिव कलनविधि

कैशे व्यवहार

फूट डालो और जीतो कलनविधि

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

कैशे व्यवहार

उप-घन एल्गोरिदम

अल्फाटेन्सर

समानांतर और वितरित एल्गोरिदम

साझा-स्मृति समानता

संचार से बचाव और वितरित एल्गोरिदम

जाल के लिए एल्गोरिदम

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories