४८ गैर-जटिल गुणा का उपयोग करके ४×४ मैट्रिक्स गुणा करने के लिए एक गैर-क्रमविनिमेय एल्गोरिदम

मूल जानकारी

• पत्र ID: २५०६.१३२४२
• शीर्षक: ४८ गैर-जटिल गुणा का उपयोग करके ४×४ मैट्रिक्स गुणा करने के लिए एक गैर-क्रमविनिमेय एल्गोरिदम
• लेखक: जीन-गिलाउम डुमास, क्लेमेंट परनेट, अलेक्जेंड्रे सेडोग्लाविक
• संस्थान: यूनिव. ग्रेनोबल आल्प्स (डुमास और परनेट), यूनिव. लिले (सेडोग्लाविक)
• वर्गीकरण: cs.SC (प्रतीकात्मक गणना)
• प्रकाशन तिथि: २७ नवंबर, २०२५ (arXiv प्रीप्रिंट)
• पत्र लिंक: https://arxiv.org/abs/2506.13242

सारांश

इस पत्र में ४८ अदिश गुणा का उपयोग करके ४×४ मैट्रिक्स गुणा की गणना के लिए एक गैर-क्रमविनिमेय एल्गोरिदम प्रस्तुत किया गया है, जो केवल परिमेय संख्या गुणांक का उपयोग करता है, जटिल संख्याओं की आवश्यकता नहीं है। यह AlphaEvolve११ द्वारा प्रस्तावित जटिल डोमेन एल्गोरिदम का सुधार है, जिसे समदैशिकता (isotropy) द्वारा परिमेय संख्या डोमेन में प्रक्षेपित किया गया है। लेख एक सीधी रेखा कार्यक्रम (straight-line program) कार्यान्वयन भी प्रदान करता है, और एक वैकल्पिक आधार संस्करण देता है, जो २ के व्युत्क्रम युक्त किसी भी वलय पर $७n^{२+\frac{\log_२ ३}{२}} + o(n^{२+\frac{\log_२ ३}{२}})$ की गणना जटिलता प्राप्त करता है।

शोध पृष्ठभूमि और प्रेरणा

समस्या पृष्ठभूमि

१. मुख्य समस्या: छोटे आयाम मैट्रिक्स गुणा के लिए इष्टतम गैर-क्रमविनिमेय एल्गोरिदम खोजना, विशेष रूप से आवश्यक अदिश गुणा की संख्या को कम करना। मैट्रिक्स गुणा कंप्यूटर विज्ञान और संख्यात्मक गणना में एक मूलभूत संक्रिया है, जिसकी दक्षता कई अनुप्रयोगों के प्रदर्शन को सीधे प्रभावित करती है।

२. महत्व:

• मैट्रिक्स गुणा की समय जटिलता रैखिक बीजगणित गणना, मशीन शिक्षण, वैज्ञानिक गणना आदि क्षेत्रों की दक्षता को सीधे प्रभावित करती है
• Strassen एल्गोरिदम (१९६९) ने पहली बार जटिलता को $O(n^३)$ से $O(n^{२.८१})$ तक घटाया, जिससे तीव्र मैट्रिक्स गुणा शोध शुरू हुआ
• छोटे आयाम मैट्रिक्स गुणा एल्गोरिदम को पुनरावर्ती रूप से बड़े मैट्रिक्स पर लागू किया जा सकता है, जिसका व्यावहारिक अनुप्रयोग मूल्य है

३. मौजूदा विधियों की सीमाएं:

• Strassen एल्गोरिदम को ४×४ मैट्रिक्स पर ४९ गुणा (दो स्तर पुनरावर्तन) की आवश्यकता होती है
• Fawzi आदि ५ ने विशेषता २ के डोमेन पर ४७ गुणा प्राप्त किया
• AlphaEvolve११ ने बड़े भाषा मॉडल और विकासात्मक कोडिंग प्रॉक्सी का उपयोग करके ४८ गुणा का एल्गोरिदम पाया, लेकिन जटिल संख्या गुणांक की आवश्यकता है
• जटिल संख्या गुणांक कुछ वलयों (जैसे पूर्णांक वलय, परिमित क्षेत्र) पर एल्गोरिदम के अनुप्रयोग को सीमित करता है

४. शोध प्रेरणा:

• जटिल संख्या आवश्यकता को समाप्त करना, एल्गोरिदम को व्यापक बीजगणितीय संरचनाओं पर लागू करना
• टेंसर विघटन सिद्धांत में समरूपता (समदैशिकता समूह क्रिया) का उपयोग करके एल्गोरिदम को व्यवस्थित रूप से रूपांतरित करना
• व्यावहारिक सीधी रेखा कार्यक्रम कार्यान्वयन प्रदान करना, स्थिरांक पदों को अनुकूलित करना

मुख्य योगदान

१. मुख्य सैद्धांतिक योगदान: AlphaEvolve एल्गोरिदम के समदैशिकता कक्षा (isotropy orbit) में परिमेय बिंदुओं के अस्तित्व को सिद्ध किया, ४८ गुणा के साथ पूर्णतः परिमेय गुणांक एल्गोरिदम प्रस्तुत किया

२. पद्धतिगत योगदान: टेंसर विघटन के समदैशिकता समूह सिद्धांत को व्यवस्थित रूप से लागू किया, समदैशिकता रूपांतरण (समीकरण २४) द्वारा जटिल डोमेन एल्गोरिदम को परिमेय संख्या डोमेन में प्रक्षेपित किया

३. व्यावहारिकता योगदान:

• पूर्ण सीधी रेखा कार्यक्रम कार्यान्वयन (सूची १-४) प्रदान किया, कुल ३४१ संक्रियाएं
• सैद्धांतिक जटिलता सीमा $११.६५६२५n^{२.७९२} - १०.६५६२५n^२$
• वैकल्पिक आधार संस्करण प्रदान किया, केवल ६ संक्रियाओं (१+२+३) की आवश्यकता, जटिलता $७n^{२.७९२}$

४. सार्वभौमिकता: एल्गोरिदम २ के व्युत्क्रम युक्त किसी भी वलय पर लागू होता है, अनुप्रयोग सीमा का विस्तार करता है

५. मुक्तस्रोत कार्यान्वयन: सभी मैट्रिक्स और कोड PLinOpt लाइब्रेरी में सार्वजनिक रूप से उपलब्ध हैं

विधि विवरण

कार्य परिभाषा

इनपुट: दो ४×४ मैट्रिक्स $A = (a_{ij})$ और $B = (b_{ij})$, तत्व $\frac{१}{२}$ युक्त वलय $R$ से
आउटपुट: गुणनफल मैट्रिक्स $C = A \cdot B = (c_{ij})$
प्रतिबंध: अदिश गुणा की संख्या को न्यूनतम करना, केवल परिमेय संख्या गुणांक का उपयोग करना (जटिल संख्याओं से बचना)

सैद्धांतिक ढांचा: टेंसर विघटन निरूपण

१. द्विरेखीय प्रतिचित्रण का टेंसर निरूपण

मैट्रिक्स गुणा को द्विरेखीय प्रतिचित्रण के रूप में दर्शाया जा सकता है: $\beta_{mm}: R^{m \times k} \times R^{k \times n} \rightarrow R^{m \times n}, \quad (A, B) \mapsto A \cdot B$

यह प्रतिचित्रण टेंसर अंतरिक्ष $(R^{m \times k})^* \otimes (R^{k \times n})^* \otimes R^{m \times n}$ में टेंसर विघटन के रूप में कूटबद्ध है: $T = \sum_{i=१}^r M_i \otimes N_i \otimes O_i$

जहां:

• $r$ टेंसर रैंक है, जो आवश्यक अदिश गुणा की संख्या के अनुरूप है
• प्रत्येक $(M_i, N_i, O_i)$ रैंक एक टेंसर है
• त्रिरेखीय निरूपण $\text{Trace}(O_i^T \cdot M_i \cdot N_i)$ है

२. Strassen एल्गोरिदम का टेंसर निरूपण

Strassen का २×२ मैट्रिक्स गुणा एल्गोरिदम (७ गुणा) टेंसर रैंक ७ के विघटन के अनुरूप है, प्रकार $X^२Y^२Z^२ + ६XYZ$।

३. समदैशिकता समूह क्रिया (Isotropy Group Action)

प्रमेय २.१: मैट्रिक्स गुणा टेंसर का समदैशिकता समूह है: $\text{psl}_{\pm}(R^m) \times \text{psl}_{\pm}(R^k) \times \text{psl}_{\pm}(R^n) \rtimes S_३$

परिभाषा २.२: समदैशिकता $g = (U \times V \times W)$ का रैंक एक टेंसर $A \otimes B \otimes C$ पर प्रभाव है: $(U^{-T} \cdot A \cdot V^T) \otimes (V^{-T} \cdot B \cdot W^T) \otimes (W^{-T} \cdot C \cdot U^T)$

यह टेंसर रैंक को अपरिवर्तित रखता है, लेकिन गुणांक बदलता है।

मुख्य एल्गोरिदम निर्माण

महत्वपूर्ण समदैशिकता रूपांतरण

इस पत्र का मुख्य नवाचार विशिष्ट समदैशिकता रूपांतरण (समीकरण २४) को खोजना है: $\begin{bmatrix} I & ० & ० & I \\ ० & १ & I & ० \\ ० & -I & -१ & ० \\ -१ & ० & ० & १ \end{bmatrix} \otimes \begin{bmatrix} I & ० & ० & १ \\ ० & -I & -I & ० \\ ० & -I & I & ० \\ -I & ० & ० & १ \end{bmatrix} \otimes \begin{bmatrix} १ & ० & ० & ० \\ ० & १ & ० & ० \\ ० & ० & १ & ० \\ ० & ० & ० & १ \end{bmatrix}$

जहां $I$ काल्पनिक इकाई है।

परिमेय गुणांक टेंसर विघटन

उपरोक्त समदैशिकता लागू करने के बाद, ४८ रैंक एक टेंसर का विघटन (समीकरण २५-७२) प्राप्त होता है, प्रत्येक का रूप: $m_i = \left(\sum_{j,k} \alpha_{jk}^{(i)} a_{jk}\right) \otimes \left(\sum_{j,k} \beta_{jk}^{(i)} b_{jk}\right) \otimes \left(\sum_{j,k} \gamma_{jk}^{(i)} c_{jk}\right)$

मुख्य विशेषताएं:

• सभी गुणांक $\alpha, \beta, \gamma \in \{-१, -\frac{१}{२}, ०, \frac{१}{२}, १\}$ (परिमेय संख्याएं)
• टेंसर प्रकार $१६X^२Y^२Z^२ + ३२XYZ$ (१६ रैंक २×२×२, ३२ रैंक १×१×१)
• हर में केवल २, ४, ८ की घातें शामिल हैं

उदाहरण: पहला गुणा पद

$m_१ = \frac{१}{४}\left(\sum_{i,j} (-१)^{i+j+१} a_{ij}\right) \otimes (b_{३१} + b_{४१}) \otimes \left(\sum c_{पद}\right)$

LRP मैट्रिक्स निरूपण

एल्गोरिदम को तीन मैट्रिक्स $(L, R, P)$ द्वारा संक्षिप्त रूप से निरूपित किया जा सकता है:

• $L \in R^{४८ \times १६}$: $A$ के तत्वों से ४८ बाएं संकारकों तक रैखिक रूपांतरण
• $R \in R^{४८ \times १६}$: $B$ के तत्वों से ४८ दाएं संकारकों तक रैखिक रूपांतरण
• $P \in R^{१६ \times ४८}$: ४८ गुणनफलों से $C$ के तत्वों तक रैखिक रूपांतरण

गणना प्रवाह: $\text{vec}(C) = P \cdot (L \cdot \text{vec}(A) \odot R \cdot \text{vec}(B))$

जहां $\odot$ तत्व-वार गुणा (Hadamard गुणा) को दर्शाता है।

तकनीकी नवाचार बिंदु

१. व्यवस्थित समरूपता उपयोग: परीक्षण खोज के बजाय, स्थिर उपसमूह $(C_२ \times D_४) \rtimes C_२$ और सैद्धांतिक निर्देशित अनुमान का उपयोग करके समदैशिकता रूपांतरण पाया गया

२. जटिल से परिमेय तक प्रक्षेपण: यह सिद्ध किया गया कि उच्च-आयामी जटिल अंतरिक्ष में पाए गए एल्गोरिदम को परिमेय उप-अंतरिक्ष में प्रक्षेपित किया जा सकता है, यह एक गैर-तुच्छ परिणाम है

३. सीधी रेखा कार्यक्रम अनुकूलन:

• PLinOpt उपकरण का उपयोग करके स्वचालित रूप से अनुकूलित सीधी रेखा कार्यक्रम उत्पन्न किया गया
• कर्नेल विघटन (kernel decomposition) द्वारा संक्रियाओं की संख्या कम की गई
• भले ही $R$ मैट्रिक्स गुणांक सरल हैं, इष्टतम SLP को गैर-तुच्छ गुणा की आवश्यकता हो सकती है

४. वैकल्पिक आधार विधि: आधार परिवर्तन (change of basis) द्वारा और सरलीकरण करके, संक्रियाओं को ३३६ तक कम किया गया (मूल ३४१ की तुलना में)

प्रयोगात्मक सेटअप

कार्यान्वयन उपकरण

• PLinOpt लाइब्रेरी: C++ रूटीन संग्रह, रैखिक और द्विरेखीय कार्यक्रम अनुकूलन संभालता है
• कोड आकार: लगभग ८.०९ kSLOC (हजार स्रोत कोड रेखाएं)
• मुक्तस्रोत: सभी मैट्रिक्स और कोड GitHub पर सार्वजनिक

डेटा फ़ाइलें

एल्गोरिदम के विभिन्न निरूपण संग्रहीत हैं:

• ४x४x४_४८_परिमेय_L.sms, _R.sms, _P.sms: मानक LRP निरूपण
• ४x४x४_४८_परिमेय-ALT_*.sms: वैकल्पिक आधार निरूपण
• ४x४x४_४८_परिमेय-CoB_*.sms: आधार परिवर्तन मैट्रिक्स

मूल्यांकन मीट्रिक

१. टेंसर रैंक: आवश्यक अदिश गुणा की संख्या (४८) २. कुल संक्रियाएं: योग और शिफ्ट संक्रियाओं की कुल संख्या ३. अनंतस्पर्शी जटिलता: $O(n^{\log_४ ३}) \approx O(n^{२.७९२})$ ४. स्थिरांक पद: प्रमुख स्थिरांक और निम्न-क्रम पद गुणांक

प्रयोगात्मक परिणाम

मुख्य परिणाम

मानक सीधी रेखा कार्यक्रम (सूची १-४)

संक्रिया विघटन:

• $L$ मैट्रिक्स: १०४ योग
• $R$ मैट्रिक्स: ८४ योग + १ गुणा (बाइनरी शिफ्ट)
• $P$ मैट्रिक्स: ११९ योग + ३३ गुणा (बाइनरी शिफ्ट)
• कुल: ३४१ संक्रियाएं

जटिलता सीमा: $\left(१ + \frac{३४१}{४८-१६}\right)n^{२+\log_४ ३} - \frac{३४१}{३२}n^२ \approx ११.६५६२५n^{२.७९२} - १०.६५६२५n^२$

वैकल्पिक आधार संस्करण (परिशिष्ट C)

संक्रिया विघटन:

• $L_{alt}$: १ योग
• $R_{alt}$: २ योग
• $P_{alt}$: ३ योग
• कुल: ६ संक्रियाएं

आधार परिवर्तन लागत:

• CoB_L: १०३ योग
• CoB_R: ७९ योग + ५ गुणा
• CoB_P: ११६ योग + ३३ गुणा
• कुल: ३३६ संक्रियाएं

जटिलता सीमा: $७n^{२.७९२} + \frac{३३६}{३१}(n^{\log_४ ४७} - n^२) = ७n^{२.७९२} + o(n^{२.७९२})$

मौजूदा विधियों से तुलना

मुख्य निष्कर्ष

१. अस्तित्व प्रमाण: यह सिद्ध किया गया कि AlphaEvolve एल्गोरिदम के समदैशिकता कक्षा में वास्तव में परिमेय बिंदु मौजूद हैं, यह स्पष्ट नहीं था

२. गुणांक सरलता: सभी गुणांक $\{-१, -\frac{१}{२}, ०, \frac{१}{२}, १\}$ हैं, कार्यान्वयन में आसान

३. अनुकूलन सिद्धांत: भले ही $R$ मैट्रिक्स गुणांक केवल $\{-१, ०, १\}$ हैं, इष्टतम सीधी रेखा कार्यक्रम को अभी भी गैर-तुच्छ गुणा की आवश्यकता है (कर्नेल विघटन के कारण)

४. वैकल्पिक आधार श्रेष्ठता: आधार परिवर्तन द्वारा प्रमुख स्थिरांक को ११.६६ से ७.०० तक कम किया जा सकता है, कीमत $o(n^{२.७९२})$ का आधार परिवर्तन लागत है

संबंधित कार्य

तीव्र मैट्रिक्स गुणा इतिहास

१. Strassen (१९६९): पहला $O(n^{२.८१})$ एल्गोरिदम, ७ गुणा से २×२ मैट्रिक्स २. de Groote (१९७८): समदैशिकता समूह और इष्टतम एल्गोरिदम के बीजगणितीय ज्यामिति का अध्ययन ३. प्रमेय २.२: सिद्ध किया कि सभी ७ गुणा २×२ एल्गोरिदम एकल कक्षा बनाते हैं

हाल की प्रगति

१. Fawzi et al. (२०२२) ५: सुदृढ़ शिक्षण का उपयोग करके विशेषता २ पर ४७ गुणा एल्गोरिदम खोजा २. Kaporin (२०२४) ८: गैर-रैखिक न्यूनतम वर्ग का उपयोग करके Brent समीकरण के जटिल समाधान हल किए ३. AlphaEvolve (२०२५) ११: बड़े भाषा मॉडल और विकासात्मक प्रॉक्सी का उपयोग करके ४८ गुणा (जटिल) और ६३ गुणा (३×४×७) एल्गोरिदम खोजे

संख्यात्मक स्थिरता अध्ययन

• Dumas et al. (२०२४) २: Strassen एल्गोरिदम की संख्यात्मक सटीकता का अध्ययन किया, पाया कि यह इष्टतम सटीक नहीं है
• इस पत्र के एल्गोरिदम का संख्यात्मक विश्लेषण अभी शेष है

इस पत्र की श्रेष्ठता

१. सैद्धांतिक कठोरता: समदैशिकता समूह सिद्धांत पर आधारित, न कि केवल अनुमानी खोज पर २. सार्वभौमिकता: परिमेय गुणांक एल्गोरिदम को व्यापक बीजगणितीय संरचनाओं पर लागू करते हैं ३. पुनरावर्तनीयता: पूर्ण मैट्रिक्स निरूपण और मुक्तस्रोत कार्यान्वयन

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

१. AlphaEvolve के जटिल एल्गोरिदम को सफलतापूर्वक परिमेय संख्या एल्गोरिदम में परिवर्तित किया, ४८ गुणा बनाए रखा २. समदैशिकता समूह क्रिया एल्गोरिदम अंतरिक्ष की व्यवस्थित खोज के लिए एक प्रभावी उपकरण है ३. दो कार्यान्वयन प्रदान किए: मानक संस्करण (३४१ संक्रियाएं) और वैकल्पिक आधार संस्करण (६+३३६ संक्रियाएं) ४. एल्गोरिदम $\frac{१}{२}$ युक्त किसी भी वलय पर लागू होता है, अनुप्रयोग सीमा का विस्तार करता है

सीमाएं

१. वलय की सीमा: २ व्युत्क्रमणीय की आवश्यकता है, विशेषता २ डोमेन पर लागू नहीं २. बड़े स्थिरांक पद: मानक संस्करण का स्थिरांक ११.६६ बड़ा है, केवल पर्याप्त बड़े मैट्रिक्स पर लाभदायक ३. संख्यात्मक स्थिरता अज्ञात: अभी तक २ जैसी संख्यात्मक सटीकता विश्लेषण नहीं किया गया ४. गैर-रचनात्मक: समदैशिकता रूपांतरण की खोज अभी भी "शिक्षित अनुमान" पर निर्भर है, पूर्णतः स्वचालित नहीं

भविष्य की दिशाएं

१. ३×४×७ एल्गोरिदम: जुड़वां पत्र ३ AlphaEvolve के दूसरे जटिल एल्गोरिदम को संभालता है २. संख्यात्मक विश्लेषण: इस एल्गोरिदम की त्रुटि प्रसार और कंडीशन संख्या का अध्ययन ३. स्वचालित खोज: समदैशिकता रूपांतरण की व्यवस्थित खोज के लिए विधि विकसित करना ४. अन्य आयाम: समान विधि को ५×५, ३×३×३ आदि स्थितियों पर लागू करना ५. वास्तविक प्रदर्शन: वास्तविक हार्डवेयर पर प्रदर्शन का परीक्षण, कैश, समानांतरता आदि कारकों पर विचार करना

गहन मूल्यांकन

गुण

१. महत्वपूर्ण सैद्धांतिक योगदान

• महत्वपूर्ण अंतराल भरा: AlphaEvolve एल्गोरिदम की जटिल संख्या गुणांक सीमा को हल किया
• पद्धतिगत नवाचार: समदैशिकता समूह सिद्धांत को व्यवस्थित रूप से लागू किया, जटिल से परिमेय तक सैद्धांतिक मार्ग प्रदान किया
• गणितीय कठोरता: Landsberg के टेंसर ज्यामिति सिद्धांत पर आधारित, ठोस बीजगणितीय ज्यामिति नींव

२. उच्च व्यावहारिक मूल्य

• पूर्ण कार्यान्वयन: सीधी रेखा कार्यक्रम और LRP मैट्रिक्स प्रदान किए, सीधे उपयोग किए जा सकते हैं
• मुक्तस्रोत पुनरावर्तनीयता: सभी डेटा और कोड PLinOpt लाइब्रेरी में सार्वजनिक
• व्यापक अनुप्रयोगशीलता: परिमेय गुणांक एल्गोरिदम को पूर्णांक, परिमेय संख्या, परिमित क्षेत्र (विषम विशेषता) आदि पर लागू करते हैं

३. तकनीकी विवरण पूर्ण

• पूर्ण एल्गोरिदम प्रदर्शन: समीकरण २५-७२ सभी ४८ गुणा पदों को विस्तार से सूचीबद्ध करते हैं
• विविध निरूपण: त्रिरेखीय रूप, LRP मैट्रिक्स, सीधी रेखा कार्यक्रम आदि विविध निरूपण प्रदान किए
• अनुकूलन रणनीतियां: कर्नेल विघटन और वैकल्पिक आधार जैसी अनुकूलन तकनीकें प्रदर्शित कीं

४. स्पष्ट लेखन

• पृष्ठभूमि परिचय पूर्ण: Strassen एल्गोरिदम से टेंसर विघटन सिद्धांत तक चरणबद्ध परिचय
• उदाहरण समृद्ध: उदाहरण २.१ दिखाता है कि समदैशिकता कैसे जटिल संख्याएं लाती है
• प्रतीक व्यवस्थित: परिभाषाएं स्पष्ट, प्रतीक संगत

दोष

१. विधि की सीमाएं

• समदैशिकता रूपांतरण की खोज: "शिक्षित अनुमान" के उपयोग को स्वीकार किया, व्यवस्थित खोज विधि का अभाव
• स्थिर उपसमूह निर्भरता: ज्ञात स्थिर उपसमूह $(C_२ \times D_४) \rtimes C_२$ की आवश्यकता है, नई समस्याओं के लिए प्राप्त करना कठिन हो सकता है
• विशेषता सीमा: विशेषता २ डोमेन पर लागू नहीं (Fawzi का ४७ गुणा एल्गोरिदम इसके विपरीत लागू होता है)

२. प्रयोगात्मक विश्लेषण अपर्याप्त

• वास्तविक प्रदर्शन परीक्षण का अभाव: वास्तविक हार्डवेयर पर रनटाइम का परीक्षण नहीं किया गया
• कोई संख्यात्मक स्थिरता विश्लेषण नहीं: इसे भविष्य के कार्य के रूप में स्वीकार किया, लेकिन व्यावहारिक अनुप्रयोगों के लिए महत्वपूर्ण
• स्थिरांक पद तुलना: अन्य एल्गोरिदम के स्थिरांक पदों से मात्रात्मक तुलना नहीं की गई

३. सैद्धांतिक गहराई

• अस्तित्व प्रमाण अपूर्ण: केवल एक परिमेय बिंदु दिखाया, इसकी विशिष्टता या इष्टतमता सिद्ध नहीं की
• कक्षा संरचना अस्पष्ट: कक्षा में परिमेय बिंदुओं की स्थिति, संख्या आदि प्रश्नों पर चर्चा नहीं की गई
• निम्न सीमा शामिल नहीं: ४×४ मैट्रिक्स गुणा की सैद्धांतिक निम्न सीमा पर चर्चा नहीं की (क्या <४८ संभव है?)

४. अभिव्यक्ति विवरण

• प्रतीक जटिलता: बड़ी संख्या में पाद सूचकांक और टेंसर संकेतन गैर-विशेषज्ञों के लिए मित्रवत नहीं हो सकते
• कोड पठनीयता: सीधी रेखा कार्यक्रम (सूची १-४) में टिप्पणियों का अभाव
• मैट्रिक्स प्रदर्शन: परिशिष्ट B के बड़े मैट्रिक्स की संरचना को सीधे समझना कठिन है

प्रभाव

क्षेत्र में योगदान

१. सिद्धांत और व्यवहार का सेतु: AI द्वारा खोजे गए एल्गोरिदम को गणितीय सिद्धांत द्वारा उपयोगी रूप में परिवर्तित किया २. पद्धतिगत प्रदर्शन: एल्गोरिदम अनुकूलन में समदैशिकता समूह सिद्धांत के व्यावहारिक अनुप्रयोग को प्रदर्शित किया ३. अनुवर्ती शोध के लिए प्रेरणा: अन्य AI-खोजे गए जटिल एल्गोरिदम को संभालने के लिए टेम्पलेट प्रदान किया

व्यावहारिक मूल्य

१. मध्यम: बड़े स्थिरांक पद (११.६६) के कारण, केवल बड़े मैट्रिक्स ($n > १००$) पर लाभदायक २. विशिष्ट क्षेत्र: सटीक परिमेय संख्या गणना की आवश्यकता वाले प्रतीकात्मक गणना प्रणालियों में अधिक मूल्यवान ३. शैक्षिक महत्व: टेंसर विघटन और समदैशिकता समूह सिद्धांत अनुप्रयोग का उत्कृष्ट उदाहरण

पुनरावर्तनीयता

• उत्कृष्ट: पूर्ण मैट्रिक्स, कोड और टूलचेन सार्वजनिक
• उपयोगिता: PLinOpt लाइब्रेरी सीधी रेखा कार्यक्रम स्वतः उत्पन्न करने के उपकरण प्रदान करती है
• दस्तावेज़ पूर्ण: परिशिष्ट सभी डेटा फ़ाइल स्थानों को विस्तार से सूचीबद्ध करता है

अनुप्रयोग परिदृश्य

आदर्श अनुप्रयोग परिदृश्य

१. प्रतीकात्मक गणना प्रणालियां: Maple, Mathematica में सटीक मैट्रिक्स संक्रियाएं २. परिमित क्षेत्र गणना: विषम विशेषता परिमित क्षेत्रों पर रैखिक बीजगणित ३. बड़े मैट्रिक्स: पुनरावर्तन द्वारा $n \geq १२८$ मैट्रिक्स पर लागू ४. सैद्धांतिक शोध: तीव्र एल्गोरिदम और टेंसर रैंक के अध्ययन के लिए उपकरण के रूप में

अनुपयुक्त परिदृश्य

१. छोटे मैट्रिक्स: एकल ४×४ मैट्रिक्स के लिए, प्राथमिक एल्गोरिदम (६४ गुणा) छोटे स्थिरांक पद के कारण तेज हो सकता है २. प्लवमान बिंदु गणना: संख्यात्मक स्थिरता अज्ञात, पारंपरिक एल्गोरिदम जितना अच्छा नहीं हो सकता ३. विशेषता २ डोमेन: Fawzi का ४७ गुणा एल्गोरिदम बेहतर ४. हार्डवेयर त्वरण: आधुनिक GPU अनुकूलित मैट्रिक्स गुणा तेज हो सकता है

संदर्भ

प्रमुख उद्धरण

१. १३ Strassen (१९६९): "Gaussian elimination is not optimal" - तीव्र मैट्रिक्स गुणा का आधारभूत कार्य २. ६,७ de Groote (१९७८): समदैशिकता समूह सिद्धांत के मूल पत्र ३. ११ Novikov et al. (२०२५): AlphaEvolve - इस पत्र द्वारा सुधारित मूल जटिल एल्गोरिदम ४. १० Landsberg (२०१६): "Geometry and complexity theory" - सैद्धांतिक आधार ५. २ Dumas et al. (२०२४): Strassen एल्गोरिदम की संख्यात्मक सटीकता विश्लेषण

संबंधित कार्य

• ५ Fawzi et al. (२०२२): सुदृढ़ शिक्षण द्वारा खोजा गया ४७ गुणा एल्गोरिदम (विशेषता २)
• ९ Karstadt & Schwartz (२०१७): मैट्रिक्स गुणा के अन्य अनुकूलन
• ४ Dumas et al. (२०२५): तीव्र सटीक एल्गोरिदम स्वतः उत्पन्न करने की विधियां
• ३ Dumas et al. (२०२५): ३×४×७ मैट्रिक्स के लिए ६३ गुणा एल्गोरिदम (जुड़वां पत्र)

समग्र मूल्यांकन

यह एक उच्च गुणवत्ता वाला सैद्धांतिक कंप्यूटर विज्ञान पत्र है, जो AI द्वारा खोजे गए जटिल डोमेन एल्गोरिदम को सफलतापूर्वक परिमेय संख्या डोमेन एल्गोरिदम में परिवर्तित करता है, जिसका महत्वपूर्ण सैद्धांतिक महत्व और कुछ व्यावहारिक मूल्य है। पत्र के मुख्य गुण हैं:

१. वास्तविक समस्या का समाधान: AlphaEvolve की जटिल संख्या गुणांक सीमा ने अनुप्रयोग सीमा को सीमित किया २. कठोर विधि: परिपक्व टेंसर विघटन और समदैशिकता समूह सिद्धांत पर आधारित ३. पूर्ण कार्यान्वयन: पुनरावर्तनीय मुक्तस्रोत कार्यान्वयन प्रदान किया

मुख्य दोष हैं: १. समदैशिकता रूपांतरण की खोज अभी भी मानव अनुमान पर निर्भर है २. वास्तविक प्रदर्शन और संख्यात्मक स्थिरता विश्लेषण का अभाव ३. बड़े स्थिरांक पद व्यावहारिकता को सीमित करते हैं

सिफारिश सूचकांक: ⭐⭐⭐⭐ (४/५)
प्रतीकात्मक गणना, टेंसर विघटन, तीव्र एल्गोरिदम में रुचि रखने वाले शोधकर्ताओं के लिए पढ़ने योग्य। व्यावहारिक अनुप्रयोगों के लिए, विशिष्ट परिदृश्य के आधार पर मूल्यांकन करना होगा कि क्या यह पारंपरिक विधियों से बेहतर है।