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

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

आव्यूह गुणन की गणितीय परिभाषा को सीधे प्रयुक्त करने से एक कलनविधि मिलता है, जिसके n³ क्रम पर कलनविधि का विश्लेषण होता है और इस प्रकार दो को गुणा करने के लिए (गणित क्षेत्र) ऑपरेशन n × n उस क्षेत्र पर आव्यूह (Θ(n³) बड़े O अंकन में होता है। 1960 के दशक में स्ट्रैसेन कलनविधि के बाद से आव्यूह को गुणा करने के लिए आवश्यक समय पर अच्छे एसिम्प्टोटिक सीमाएं ज्ञात हैं, लेकिन इष्टतम समय अर्थात आव्यूह गुणन की कम्प्यूटेशनल जटिलता अज्ञात बनी हुई है। और इस प्रकार अक्टूबर 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