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

क्योंकि मैट्रिक्स गुणन कई संख्यात्मक एल्गोरिदम में एक ऐसा केंद्रीय ऑपरेशन है, इसलिए मैट्रिक्स गुणन एल्गोरिदम को कुशल बनाने में बहुत काम किया गया है। कम्प्यूटेशनल समस्याओं में मैट्रिक्स गुणन के अनुप्रयोग वैज्ञानिक कंप्यूटिंग और पैटर्न पहचान सहित कई क्षेत्रों में पाए जाते हैं और ग्राफ़ (ग्राफ सिद्धांत) के माध्यम से पथों की गिनती जैसी प्रतीत होने वाली असंबंधित समस्याओं में पाए जाते हैं।समानांतर कंप्यूटिंग और वितरित कंप्यूटिंग सिस्टम सहित विभिन्न प्रकार के हार्डवेयर पर मैट्रिक्स को गुणा करने के लिए कई अलग-अलग एल्गोरिदम डिज़ाइन किए गए हैं, जहां कम्प्यूटेशनल कार्य कई प्रोसेसर (शायद एक नेटवर्क पर) में फैला हुआ है।

मैट्रिक्स गुणन की गणितीय परिभाषा को सीधे लागू करने से एक एल्गोरिदम मिलता है जिसके क्रम पर एल्गोरिदम का विश्लेषण होता है n³दो को गुणा करने के लिए फ़ील्ड (गणित) संक्रियाएँ n × n उस फ़ील्ड पर मैट्रिक्स (Θ(n³) बड़े ओ अंकन में)। 1960 के दशक में स्ट्रैसेन एल्गोरिदम के बाद से मैट्रिक्स को गुणा करने के लिए आवश्यक समय पर बेहतर एसिम्प्टोटिक सीमाएं ज्ञात हैं, लेकिन इष्टतम समय (यानी, मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता) अज्ञात बनी हुई है। As of October 2022, मैट्रिक्स गुणन एल्गोरिथ्म की समय जटिलता पर सर्वोत्तम घोषित सीमा है O(n^2.37188) समय, डुआन, वू और झोउ द्वारा दिया गया एक प्रीप्रिंट में घोषणा की गई। इससे सीमा में सुधार होता है O(n^2.3728596) समय, जोश अल्मन और वर्जीनिया वासिलिव्स्का विलियम्स द्वारा दिया गया। हालाँकि, यह एल्गोरिथ्म बड़े स्थिरांक के कारण एक गैलेक्टिक एल्गोरिदम है और इसे व्यावहारिक रूप से महसूस नहीं किया जा सकता है।

पुनरावृत्त एल्गोरिथ्म

मैट्रिक्स गुणा#परिभाषा यह है कि यदि C = AB एक के लिए n × m आव्यूह A और एक m × p आव्यूह B, तब C एक n × 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 ← sum + A_ik × B_kj
    • तय करना C_ij ← sum
• वापस करना C

यह एल्गोरिथम समय की जटिलता लेता है Θ(nmp) (स्पर्शोन्मुख संकेतन में)।एल्गोरिदम के विश्लेषण के उद्देश्य से एक सामान्य सरलीकरण यह मान लेना है कि इनपुट सभी आकार के वर्ग मैट्रिक्स हैं n × n, जिस स्थिति में चलने का समय है Θ(n³), यानी, आयाम के आकार में घन।

कैश व्यवहार

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

पुनरावृत्त मैट्रिक्स गुणन में तीन लूपों को शुद्धता या एसिम्प्टोटिक रनिंग टाइम पर प्रभाव के बिना एक दूसरे के साथ मनमाने ढंग से स्वैप किया जा सकता है। हालाँकि, संदर्भ की स्थानीयता और एल्गोरिथम के सीपीयू कैश उपयोग के कारण ऑर्डर व्यावहारिक प्रदर्शन पर काफी प्रभाव डाल सकता है;

कौन सा क्रम सबसे अच्छा है यह इस बात पर भी निर्भर करता है कि मैट्रिक्स पंक्ति- और स्तंभ-प्रमुख क्रम में संग्रहीत हैं या नहीं | पंक्ति-प्रमुख क्रम, स्तंभ-प्रमुख क्रम, या दोनों का मिश्रण।

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

• इनपुट: मैट्रिसेस A और B
• होने देना C उचित आकार का एक नया मैट्रिक्स बनें
• टाइल का आकार चुनें T = Θ(√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 ← sum + A_ik × B_kj
          • तय करना C_ij ← C_ij + sum
• वापस करना C

आदर्शीकृत कैश मॉडल में, यह एल्गोरिदम केवल लागू होता है Θ(n³/b √M) कैश चूक गया; भाजक b √M आधुनिक मशीनों पर परिमाण के कई आदेशों के बराबर है, ताकि कैश छूटने के बजाय वास्तविक गणना चलने के समय पर हावी हो जाए।

फूट डालो और जीतो एल्गोरिथ्म

पुनरावृत्त एल्गोरिथ्म का एक विकल्प मैट्रिक्स गुणन के लिए फूट डालो और जीतो एल्गोरिथ्म है। यह ब्लॉक मैट्रिक्स पर निर्भर करता है

$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ⁿ × 2ⁿ कुछ के लिए 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₁₁ = a₁₁b₁₁ इसके आधार मामले के रूप में।

एक फ़ंक्शन के रूप में इस एल्गोरिदम की जटिलता n पुनरावृत्ति द्वारा दिया जाता है

$T(1)=\Theta (1);$

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

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

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

इस एल्गोरिदम का एक प्रकार जो मनमाने आकार के मैट्रिक्स के लिए काम करता है और व्यवहार में तेज़ हैमैट्रिक्स को चार उपमैट्रिस के बजाय दो में विभाजित करता है, इस प्रकार। मैट्रिक्स को विभाजित करने का मतलब अब इसे समान आकार के दो भागों में विभाजित करना है, या विषम आयामों के मामले में जितना संभव हो सके समान आकार के करीब विभाजित करना है।

• इनपुट: मैट्रिसेस A आकार का n × m, B आकार का m × 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}$

कैश व्यवहार

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

इस एल्गोरिथम द्वारा किसी मशीन पर कैश मिस होने की संख्या M आदर्श कैश की पंक्तियाँ, प्रत्येक आकार की b बाइट्स, से घिरा है

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

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

Further information: Computational complexity of matrix multiplication

घातांक के अनुमानों में सुधार ωमैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता के लिए समय के साथ $O(n^{\omega })$.

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

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

अल्फाटेन्सर

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

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

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

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

${\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}}$

चार योगों की तरह, एक-दूसरे से स्वतंत्र रूप से निष्पादित किया जा सकता है (हालांकि एल्गोरिदम को योग करने से पहले गुणाओं को जोड़ने की आवश्यकता होती है)। समस्या की पूर्ण समानता का उपयोग करते हुए, एक एल्गोरिथ्म प्राप्त होता है जिसे फोर्क-जॉइन मॉडल | फोर्क-जॉइन स्टाइल छद्मकोड में व्यक्त किया जा सकता है:

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

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

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

• आधार मामला: यदि n = 1, तय करना c₁₁ ← c₁₁ + t₁₁ (या एक छोटा लूप बनाएं, शायद अनियंत्रित)।
• अन्यथा:
  • विभाजन C में C₁₁, C₁₂, C₂₁, C₂₂.
  • विभाजन T में T₁₁, T₁₂, T₂₁, T₂₂.
  • समानांतर में:
    • काँटा add(C₁₁, T₁₁).
    • काँटा add(C₁₂, T₁₂).
    • काँटा add(C₂₁, T₂₁).
    • काँटा add(C₂₂, T₂₂).
  • जोड़ना।

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

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

ब्लॉक मैट्रिक्स गुणन. 2डी एल्गोरिदम में, प्रत्येक प्रोसेसर एक सबमैट्रिक्स के लिए जिम्मेदार होता है C. 3डी एल्गोरिथम में, सबमैट्रिसेस की प्रत्येक जोड़ी A और B जिसे गुणा किया जाता है उसे एक प्रोसेसर को सौंपा जाता है।

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

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

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

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

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

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

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

यह भी देखें

• गणितीय संक्रियाओं की कम्प्यूटेशनल जटिलता
• मैट्रिक्स गुणन की कम्प्यूटेशनल जटिलता
• CYK एल्गोरिथम#वैलिएंट्स एल्गोरिथम|CYK एल्गोरिथम § वैलिएंट्स एल्गोरिथम
• मैट्रिक्स श्रृंखला गुणन
• विरल मैट्रिक्स-वेक्टर गुणन
• चार रूसियों की विधि

अग्रिम पठन

• 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