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

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

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

• Input: matrices Aand B
• LetCbe a new matrix of the appropriate size
• For i 1 to n:
  • Forj 1 top:
    • Let sum sum = 0
    • For k 1 tom:
      • Set sumsum ← sum + A_ik × B_kj
    • Set Cij C_ij ← sum
• Return 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 फ़ास्ट है यह कई पुस्तकालयों में दिखाई देता है, जैसे कि BLAS (बुनियादी रैखिक बीजगणित सबप्रोग्राम ) यह परिमित क्षेत्र जैसे सटीक डोमेन पर बड़े आव्यूह के लिए बहुत उप समेशन ी है, जहां संख्यात्मक स्थिरता समस्या नहीं है।

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

फ़्रीवाल्ड्स का कलनविधि एक सरल मोंटे कार्लो कलनविधि है, जो आव्यूह 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₂₂).
  • जोड़ना।

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

इस कलनविधि में Θ(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