💻 computer science

55 Additions Suffice for 3x3 Matrix Multiplication at Rank 23

यह शोध पत्र $3\times3$ मैट्रिक्स गुणन के लिए एक नया रैंक-23 एल्गोरिदम प्रस्तुत करता है जो आवश्यक जोड़ की संख्या को घटाकर 55 (कुल 78 स्केलर संचालन) कर देता है, जिससे पेर्मिनोव के टेंसर और एक अनुकूलित रैखिक सर्किट पर आधारित एक निर्माण के माध्यम से किसी भी साहचर्य रिंग (associative ring) पर वैधता बनाए रखते हुए पिछले अत्याधुनिक स्तर के 56 जोड़ों में सुधार किया गया है।

मूल लेखक: Samurdhi Karunaratne, Anushka Idamekorala

प्रकाशित 2026-08-03

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Samurdhi Karunaratne, Anushka Idamekorala

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

लेकिन, इसमें एक पेंच है। हालांकि आप महंगे गुणाओं को बचा सकते हैं, लेकिन अक्सर आपको सामग्री तैयार करने के लिए अधिक "जोड़" (additions/मिक्सिंग बाउल्स) करने पड़ते हैं। इसे इस तरह समझें: केवल एक कटोरे में आटा डालने के बजाय, आपको सामग्री को मिलाने के लिए एक बहुत ही विशिष्ट नृत्य की तरह कुछ चीजें काटनी, चलाना और फोल्ड करनी पड़ सकती हैं। लक्ष्य एक ऐसा आदर्श नृत्य क्रम (dance routine) खोजना है जो कम से कम चरणों का उपयोग करता हो। यह शोध पत्र इस बारे में है कि एक टीम ने एक विशिष्ट प्रकार के केक के लिए एक नया, थोड़ा अधिक कुशल नृत्य खोजा है: एक 3x3 मैट्रिक्स। उन्होंने कुल "भारी उठाने" (multiplications) की संख्या नहीं बदली, बल्कि वे "मिक्सिंग स्टेप्स" (additions) को कम करने में सफल रहे, जिससे काम में एक छोटा लेकिन महत्वपूर्ण हिस्सा कम हो गया।

नया रिकॉर्ड-तोड़ने वाला नृत्य

लॉजिकल एआई (Logical AI) के समूर्धि करुणा راتने और अनुष्का इदामेकोराला द्वारा लिखा गया यह शोध पत्र, संख्याओं के दो 3x3 ग्रिड को गुणा करने के लिए एक नया रिकॉर्ड घोषित करता है। उन्होंने इसे केवल 55 जोड़ (additions) और 23 गुणा (multiplications) का उपयोग करके करने का तरीका खोज निकाला है।

यह समझने के लिए कि यह बड़ी बात क्यों है, पिछले सर्वश्रेष्ठ रेसिपी की कल्पना करें। वर्तमान चैंपियन, सन (Sun) नामक एक शोधकर्ता द्वारा बनाया गया था, जिसमें 56 जोड़ की आवश्यकता थी। इस पेपर के लेखक नहीं चाहते थे कि वे पूरी तरह से एक नई मैट्रिक्स गुणन विधि का आविष्कार करें; इसके बजाय, उन्होंने एक मौजूदा, सार्वजनिक रेसिपी (जो परमिनोव द्वारा बनाई गई थी और जिसमें 58 जोड़ थे, और इसके शुरुआती संस्करणों में 59 जोड़ थे) ली और उन्होंने "तैयारी" के चरणों को अनुकूलित (optimize) किया। उन्होंने महसूस किया कि कैसे सामग्रियों को प्री-मिक्स (pre-mix) करने के तरीके को बदलकर, वे कुल जोड़ चरणों को घटाकर 55 कर सकते हैं।

यहाँ उनका नया "रसोई" कार्यप्रणाली दी गई है, जिसे तीन सरल चरणों में विभाजित किया गया है:

बाईं ओर की सामग्री तैयार करना: मिलाने से पहले, वे पहले ग्रिड की संख्याओं को लेते हैं (मान लीजिए कि इसे "Left" ग्रिड कहते हैं) और 23 विशेष मिश्रण बनाने के लिए 13 सरल जोड़ या घटाव के चरण करते हैं।
दाईं ओर की सामग्री तैयार करना: वे दूसरे ग्रिड के लिए भी ऐसा ही करते हैं (जिसे "Right" ग्रिड कहा जाता है), और इसके 23 विशेष मिश्रण बनाने के लिए 14 चरणों का उपयोग करते हैं।
बड़ा मिश्रण और अंतिम असेंबली: वे Left और Right ग्रिड के मिलान वाले मिश्रणों को गुणा करते हैं (कुल 23 गुणा)। फिर, वे अंतिम 3x3 परिणाम को असेंबल करने के लिए उन 23 परिणामों में 28 और जोड़ चरण करते हैं।

जब आप तैयारी के काम (13 + 14) और अंतिम असेंबली (28) को जोड़ते हैं, तो आपको ठीक 55 जोड़ मिलते हैं। यह पिछले सर्वश्रेष्ठ से एक कम है, जो इसे इस विशिष्ट प्रकार की गणना के लिए ज्ञात सबसे कुशल विधि बनाता है।

यह क्यों मायने रखता है (और क्यों नहीं)

आप सोच सकते हैं, "क्या यह इसे करने का सबसे अच्छा संभव तरीका है?" लेखक बहुत सावधानी से कहते हैं: नहीं, जरूरी नहीं कि ऐसा हो। उन्होंने यह सिद्ध किया है कि इस विशिष्ट व्यवस्था के लिए, जो उन्होंने चुनी है, 55 सबसे अच्छा है। उन्होंने एक कठोर गणितीय खोज का उपयोग किया ताकि यह साबित किया जा सके कि वे इस विशिष्ट रेसिपी के लिए इससे कम चरणों के साथ काम नहीं चला सकते। हालांकि, वे स्वीकार करते हैं कि एक पूरी तरह से अलग रेसिपी (सामग्रियों की एक अलग व्यवस्था) हो सकती है जो और भी तेज़ हो। उन्होंने इसे अभी तक नहीं खोजा है, और वे यह दावा नहीं कर रहे हैं कि उन्होंने मैट्रिक्स गुणन के पूरे रहस्य को हमेशा के लिए हल कर दिया है।

वे यह भी स्पष्ट करते हैं कि यह केवल एक भाग्यशाली अनुमान या गलत हो सकने वाला कंप्यूटर सिमुलेशन नहीं है। उन्होंने सत्य का एक "प्रमाणपत्र" (certificate) प्रदान किया है। उन्होंने पूरी चरण-दर-चरण रेसिपी (जिसे "स्ट्रेट-लाइन प्रोग्राम" कहा जाता है) लिखी और प्रत्येक एक से अधिक 729 गणितीय नियमों को जांचने के लिए कई स्वतंत्र कंप्यूटर प्रोग्रामों (Python और Node.js में लिखे गए) के माध्यम से इसे चलाया। प्रत्येक जांच सफल रही। इसका मतलब है कि गणित ठोस है और यह रेसिपी किसी भी प्रकार की संख्या प्रणाली के लिए पूरी तरह से काम करती है, यहाँ तक कि उन अजीब प्रणालियों के लिए भी जहाँ गुणा का क्रम मायने रखता है।

पर्दे के पीछे का AI

इस कहानी में एक दिलचस्प मोड़ यह है कि रेसिपी कैसे खोजी गई। लेखक खुलासा करते हैं कि एक मानव शोधकर्ता ने एक AI सिस्टम (विशेष रूप से, OpenAI के GPT-5.6 Sol का उपयोग करने वाला एक एजेंट) के मार्गदर्शन में इस रेसिपी को खोजने में मदद की। मानव ने लक्ष्य निर्धारित किया: "एक तरीका खोजें जिससे 56-एडिशन के रिकॉर्ड को तोड़ा जा सके।" AI ने मौजूदा रेसिपी के परिदृश्य का पता लगाया, परमिनोव के पुराने 58-एडिशन वाले संस्करण को पाया, और महसूस किया कि तैयारी के चरणों में थोड़ा बदलाव करके, वह तीन अतिरिक्त मूव्स कम कर सकता है। AI ने अपने काम की दोबारा जांच की, कोड लिखा, और गणित को सत्यापित किया। यह मानव और मशीन के मिलकर काम करने का एक आदर्श उदाहरण है: मानव ने दिशा और "क्यों" प्रदान किया, जबकि AI ने लाखों संभावनाओं में से "कैसे" खोजने के लिए भारी काम संभाला।

अंत में, यह शोध पत्र एक छोटी लेकिन सटीक जीत है। यह दिखाता है कि मैट्रिक्स गुणन जैसे पुराने क्षेत्र में भी, अभी भी सूक्ष्म, छिपी हुई दक्षताएँ मौजूद हैं, जिन्हें खोजने के लिए यदि आप बारीकी से देखें तो पाया जा सकता है। यह एक परिचित जंगल के माध्यम से एक नए, थोड़े छोटे रास्ते को खोजने जैसा है। आप अभी भी उसी स्थान पर पहुँचते हैं, लेकिन आप बस एक कम कदम के साथ वहाँ पहुँच जाते हैं।

तकनीकी सारांश: 23 रैंक के लिए 3 × 3 मैट्रिक्स गुणन हेतु 55 जोड़ पर्याप्त हैं

समस्या विवरण
यह शोध पत्र एक निश्चित मल्टीप्लिकेटिव रैंक 23 के दिए जाने पर, एक साहचर्य रिंग (associative ring) पर दो अनिश्चित $3 \times 3$ मैट्रिसेस को गुणा करने के लिए आवश्यक योगात्मक जटिलता (जोड़ और घटाव की संख्या) को न्यूनतम करने की समस्या को संबोधित करता है। जहाँ स्ट्रैसन (Strassen) के एल्गोरिदम ने यह स्थापित किया कि द्विपद उत्पादों (bilinear products) को कम करके मैट्रिक्स गुणन को त्वरित किया जा सकता है, वहीं सामान्य $3 \times 3$ मैट्रिसेस के लिए मल्टीप्लिकेटिव रैंक लाडरमैन (Laderman) की 1976 की खोज के बाद से 23 पर स्थिर रही है। हालिया शोध इन रैंक-23 योजनाओं को साकार करने के लिए आवश्यक स्केलर जोड़ (scalar additions) की संख्या को कम करने पर केंद्रित रहा है। इस कार्य से पूर्व, सन (Sun) द्वारा प्राप्त 56 जोड़, अत्याधुनिक स्थिति (state of the art) थी।

कार्यप्रणाली
लेखक एक पूर्व-मौजूदा टेंसर फैक्टराइजेशन के रैखिक चरणों (linear stages) को अनुकूलित करके एक नया एल्गोरिदम निर्मित करते हैं। कार्यप्रणाली इस प्रकार है:

आधार टेंसर (Base Tensor): निर्माण में परमिनोव (Perminov) के सार्वजनिक रूप से जारी फैक्टराइजेशन, cr58_cn122 का उपयोग किया गया है, जिसमें मूल रूप से 58 जोड़ (बाएं इनपुट के लिए 14, दाएं इनपुट के लिए 15, और आउटपुट पुनर्निर्माण के लिए 29) की आवश्यकता थी।
फैक्टर मैप्स का सटीक संश्लेषण (Exact Synthesis of Factor Maps): लेखक 9 इनपुट मैट्रिक्स प्रविष्टियों को 23 द्विपद रूपों (bilinear forms) में बदलने वाले तीन रैखिक मानचित्रों ( $U, V, W$ $U, V, W$ ) को अनुकूलित करने के लिए बाइनरी जोड़/घटाव स्ट्रेट-लाइन प्रोग्राम (SLP) मॉडल के भीतर एक व्यापक निर्भरता खोज (exhaustive dependency search) करते हैं।
- वे पहचानते हैं कि टेंसर के निश्चित ओरिएंटेशन (orientation) के लिए, आवश्यक आउटपुट दिशाओं को उत्पन्न करने के लिए आवश्यक न्यूनतम गेट्स की संख्या, विशिष्ट गैर-आधार दिशाओं ( $d(F)$ ) पर आधारित सैद्धांतिक निचली सीमा से अधिक है।
- विशेष रूप से, वे सिद्ध करते हैं कि बाएं फैक्टर ( $U$ ) के लिए लागत 13 है (12 के फ्लोर से एक अधिक); दाएं फैक्टर ( $V$ ) के लिए लागत 14 है (13 के फ्लोर से एक अधिक); और आउटपुट फैक्टर ( $W$ ) के लिए लागत 14 है (13 के फ्लोर से एक अधिक)।
ट्रांसपोज़िशन सिद्धांत (Transposition Principle): आउटपुट पुनर्निर्माण सर्किट (जो 23 उत्पादों को वापस 9 मैट्रिक्स प्रविष्टियों में मैप करता है) प्राप्त करने के लिए, लेखक $W$ के अनुकूलित 14-जोड़ वाले सर्किट को ट्रांसपोज़ करते हैं। रैखिक-सर्किट ट्रांसपोज़िशन सिद्धांत का उपयोग करते हुए, एक सर्किट जिसमें $L$ गेट्स, $n$ इनपुट और $m$ आउटपुट हैं, वह ट्रांसपोज़ के लिए एक सर्किट में परिवर्तित हो जाता है जिसमें $L + m - n$ गेट्स होते हैं। $W$ सर्किट ( $L=14, n=9, m=23$ ) पर इसे लागू करने से 28-गेट वाला आउटपुट सर्किट प्राप्त होता है।
सत्यापन (Verification): पूर्णांकों $\mathbb{Z}$ पर सभी 729 ब्रेंट पहचानों (Brent identities) की जाँच करके एल्गोरिदम की शुद्धता को सत्यापित किया जाता है। लेखक चार स्वतंत्र सत्यापन विधियाँ प्रदान करते हैं, जिनमें पायथन (Python) और नोड.जेएस (Node.js) कार्यान्वयन शामिल हैं, जो यह सुनिश्चित करते हैं कि परिणाम किसी भी साहचर्य रिंग (commutative या नहीं) पर मान्य है क्योंकि कोएफिशिएंट अल्फाबेट $\{-1, 0, 1\}$ तक सीमित है।

प्रमुख योगदान

नया ऊपरी स्तर (New Upper Bound): यह शोध पत्र 23 स्केलर गुणन और 55 जोड़/घटाव का उपयोग करके $3 \times 3$ मैट्रिक्स गुणन का एक कार्यान्वयन प्रस्तुत करता है, जो पिछले रिकॉर्ड 56 में सुधार करता है।
इष्टतमता प्रमाण (Optimality Certificate): लेखक विशिष्ट टेंसर ओरिएंटेशन के लिए एक प्रमाणित इष्टतम रैखिक सर्किट प्रदान करते हैं। वे प्रदर्शित करते हैं कि विशिष्ट टेंसर cr5_cn122 के लिए, मानक तीन-चरण द्विपद SLP मॉडल में रैखिक चरण की लागतों का योग 55 से कम नहीं हो सकता।
सटीक डेटा रिलीज: शोध पत्र पूर्ण स्ट्रेट-लाइन प्रोग्राम, टेंसर फैक्टर्स, और एक "फ्रोजन सर्टिफिकेट" (frozen certificate) शामिल करता है जो बाइट-दर-बाइट पुनरुत्पादन और स्वतंत्र सत्यापन की अनुमति देता है।

परिणाम
परिणामी सर्किट की संरचना इस प्रकार है:

बायां प्रीप्रोसेसिंग (A): 13 जोड़ (9 इनपुट को 23 रूपों में मैप करना)।
दायां प्रीप्रोसेसिंग (B): 14 जोड़ (9 इनपुट को 23 रूपों में मैप करना)।
द्विपद परत (Bilinear Layer): 23 गुणन।
आउटपुट पुनर्निर्माण: 28 जोड़ (23 उत्पादों को 9 आउटपुट में मैप करना)।
कुल रैखिक कार्य: 55 जोड़।

शोध पत्र पुष्टि करता है कि यह एल्गोरिदम किसी भी साहचर्य रिंग पर लागू होता है क्योंकि कोएफिशिएंट $\{-1, 0, 1\}$ में हैं और द्विपद उत्पादों का क्रम संरक्षित है।

महत्व और दावे
लेखक स्पष्ट रूप से कहते हैं कि वे यह दावा नहीं करते कि 55 सभी संभावित रैंक-23 अपघटन (decompositions) में से वैश्विक न्यूनतम है, न ही यह कि यह उन सर्किट मॉडलों में इष्टतम है जो जोड़/घटाव के अलावा अन्य प्रिमिटिव ऑपरेशन्स की अनुमति देते हैं। हालांकि, एक निश्चित टेंसर ओरिएंटेशन और मानक तीन-चरण द्विपद स्ट्रेट-लाइन प्रोग्राम के विशिष्ट मॉडल के भीतर, 55 वर्तमान में ज्ञात सबसे कम जोड़ गणना है।

इस कार्य का महत्व निम्नलिखित में निहित है:

क्रमिक सुधार: यह एक जोड़ को कम करके ऊपरी स्तर (upper bound) को कम करता है, जो निश्चित मल्टीप्लिकेटिव रैंक के लिए योगात्मक जटिलता को अनुकूलित करने की प्रवृत्ति को जारी रखता है।
कठोर सत्यापन: परिणाम सटीक पूर्णांक अंकगणित और कई स्वतंत्र कार्यान्वयन द्वारा समर्थित है, जो संख्यात्मक या यादृच्छिक परीक्षणों पर निर्भरता से बचता है।
AI-सहायता प्राप्त खोज: शोध पत्र खुलासा करता है कि खोज को खोज, संश्लेषण और सत्यापन के लिए AI एजेंटों (OpenAI GPT-5.6 Sol और Codex) का उपयोग करते हुए एक मानव-निर्देशित जांच द्वारा संचालित किया गया था। मानव शोधकर्ता ने उद्देश्यों और स्वीकृति मानदंडों को परिभाषित किया, जबकि AI एजेंटों ने सर्किट खोज और सर्टिफिकेट का निष्पादन किया। लेखक इस बात पर जोर देते हैं कि गणितीय वैधता पूरी तरह से 729 सटीक पहचानों और मुद्रित स्ट्रेट-लाइन प्रोग्राम पर टिकी है, न कि AI की भागीदारी पर।

नया रिकॉर्ड-तोड़ने वाला नृत्य

यह क्यों मायने रखता है (और क्यों नहीं)

पर्दे के पीछे का AI

तकनीकी सारांश: 23 रैंक के लिए 3 × 3 मैट्रिक्स गुणन हेतु 55 जोड़ पर्याप्त हैं

इसी तरह के और पेपर