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

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

आव्यूह गुणन की गणितीय परिभाषा को सीधे प्रयुक्त करने से एक कलनविधि मिलता है, जिसके 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: आव्यूह गुणन की कम्प्यूटेशनल जटिलता

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

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

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

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

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

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

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

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

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

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

यह भी देखें

• गणितीय ऑपरेशन की कम्प्यूटेशनल जटिलता
• आव्यूह गुणन की कम्प्यूटेशनल जटिलता
• 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