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

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

आव्यूह गुणन की गणितीय परिभाषा को सीधे प्रयुक्त करने से एक कलनविधि मिलता है, जिसके 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³) के रूप में प्रयुक्त होता है और सबसे खराब स्थिति में कैशे छूट जाता है। वर्ष 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