🔢 mathematics

Efficient approximations of matrix multiplication using truncated decompositions

यह शोध पत्र विशेष रूप से लार्ज लैंग्वेज मॉडल (LLM) ऑपरेशन्स में प्रदर्शन लाभ को लक्षित करते हुए, उपयोगी त्रुटि सहनशीलता (error tolerances) बनाए रखते हुए कम्प्यूटेशनल जटिलता को कम करने के लिए ट्रंकेटेड सिंगुलर वैल्यू, सर्कुलेंट और साइकिल-आधारित अपघटन (decompositions) का उपयोग करके $\mathcal{O}(n^2 \log n)$ समय में बड़े डेंस मैट्रिक्स गुणन को अनुमानित करने की एक कुशल विधि प्रस्तावित करता है।

मूल लेखक: Suvendu Kar, Hariprasad M., Sai Gowri J. N., Murugesan Venkatapathi

प्रकाशित 2026-04-27

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

CC BY 4.0

मूल लेखक: Suvendu Kar, Hariprasad M., Sai Gowri J. N., Murugesan Venkatapathi

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

कल्पना कीजिए कि आप एक पेशेवर शेफ हैं जिन्हें 1,000 मेहमानों के लिए एक विशाल दावत तैयार करने का काम सौंपा गया है। आपके पास दो बड़े क्रेट सामग्री (मैट्रिक्स A और मैट्रिक्स B) हैं जिन्हें मिलाकर एक अंतिम दावत (मैट्रिक्स AB) तैयार की जानी है।

यदि आप हर एक रेसिपी का अक्षरशः पालन करने की कोशिश करते हैं, जैसे कि हर छोटी जड़ी-बूटी को काटना और नमक के हर दाने को पूरी तरह से मापना, तो आप हफ्तों तक रसोई में ही रहेंगे। मेहमान भूखे रह जाएंगे और आप थकान से टूट जाएंगे। यही सटीक मैट्रिक्स गुणन (exact matrix multiplication) की समस्या है: यह समय और कंप्यूटर की शक्ति के मामले में अविश्वसनीय रूप से "महंगा" है।

यह शोध पत्र इस तरीके से उस दावत को बहुत तेज़ी से पकाने का प्रस्ताव देता है—"स्मार्ट शॉर्टकट्स" (Smart Shortcuts) का उपयोग करके—जो ऐसे अनुमान (approximations) हैं जो आपको मूल भोजन जैसा 99% स्वाद देंगे, लेकिन बहुत कम समय में।

यहाँ बताया गया है कि वे इसे तीन अलग-अलग "खाना पकाने की शैलियों" का उपयोग करके कैसे करते हैं:

1. "मुख्य सामग्री" विधि (SVD डिकंपोजिशन)

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

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

परिणाम: आपको गति में भारी उछाल मिलता है क्योंकि आप पार्सले पर घंटों समय बर्बाद नहीं कर रहे हैं।

2. "पैटर्न पहचान" विधि (सर्कुलेंट डिकंपोजिशन)

कल्पना कीजिए कि आप पफ पेस्ट्री की एक बड़ी शीट बना रहे हैं। हर एक आटे के फ्लेक (flake) को एक अद्वितीय वस्तु के रूप में मानने के बजाय, आप महसूस करते हैं कि पेस्ट्री एक दोहराते हुए पैटर्न का पालन करती है: मोड़ो, रोल करो, दोहराओ। क्योंकि आप पैटर्न को पहचान लेते हैं, इसलिए आपको हर फ्लेक के बारे में सोचने की ज़रूरत नहीं है; आप बस "पैटर्न नियम" को बार-बार लागू करते हैं।

यह सर्कुलेंट डिकंपोजिशन (Circulant Decomposition) है। कई वास्तविक दुनिया के डेटा सेट (जैसे चित्र या सिग्नल) में दोहराते हुए पैटर्न या "चक्र" होते हैं। शोधकर्ताओं ने पाया कि यदि वे मैट्रिक्स को इन दोहराते हुए चक्रों में तोड़ देते हैं, तो वे फास्ट फूरियर ट्रांसफॉर्म (FFT) नामक एक गणितीय "चीट कोड" का उपयोग करके उन्हें अविश्वसनीय रूप से तेज़ी से गुणा कर सकते हैं।

परिणाम: यह 1,000 व्यक्तिगत कुकीज़ को हाथ से आकार देने के बजाय कुकी कटर का उपयोग करने जैसा है।

3. "अनिवार्य स्केच" विधि (फूरियर स्पारसिफिकेशन)

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

यह फूरियर स्पारसिफिकेशन (Fourier Sparsification) है। शोधकर्ता मैट्रिक्स को एक "फ्रीक्वेंसी" संस्करण में बदल देते हैं (जैसे एक जटिल गीत को केवल उसकी मुख्य धुन और बेसलाइन में बदलना)। वे तेज़ और प्रभावी नोट्स को रखते हैं और शांत, बैकग्राउंड शोर को हटा देते हैं।

परिणाम: आपको गुणन का एक ऐसा "स्केच" मिलता है जो बहुत हल्का और प्रोसेस करने में तेज़ होता है।

यह वास्तविक दुनिया में क्यों मायने रखता है? (LLM कनेक्शन)

यह शोध पत्र विशेष रूप से लार्ज लैंग्वेज मॉडल्स (LLMs) का उल्लेख करता है—जो ChatGPT जैसी चीज़ों के पीछे के दिमाग हैं।

जब आप किसी AI में प्रॉम्प्ट टाइप करते हैं, तो कंप्यूटर को यह पता लगाने के लिए कि अगला शब्द क्या कहना है, इन अरबों "सामग्री संयोजनों" (मैट्रिक्स गुणन) को करना पड़ता है। इसमें भारी मात्रा में बिजली और समय लगता है।

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

सारांश

समस्या: आधुनिक AI द्वारा उपयोग किए जाने वाले विशाल डेटा के लिए सटीक गणित बहुत धीमा है।
समाधान: पूर्णतावादी (perfectionist) न बनें। सबसे महत्वपूर्ण हिस्सों की पहचान करें (SVD), पैटर्न को पहचानें (Circlet), या बड़े आकारों पर ध्यान केंद्रित करें (Sparsification)।
जीत: तेज़ AI, कम कंप्यूटिंग पावर, और गुणवत्ता में लगभग कोई कमी नहीं।

तकनीकी सारांश: ट्रंकेटेड डिकंपोज़िशन का उपयोग करके मैट्रिक्स गुणन का कुशल सन्निकटन (Approximations)

1. समस्या विवरण

आधुनिक कम्प्यूटेशनल कार्यों में से कई—वैज्ञानिक सिमुलेशन से लेकर डीप लर्निंग तक—में मौलिक बाधा बड़े, घने (dense) मैट्रिसेस का गुणन है। जबकि दो $n \times n$ मैट्रिसेस का सटीक गुणन के लिए $O(n^3)$ अंकगणितीय ऑपरेशनों की आवश्यकता होती है, और स्ट्रैसन (Strassen) या कॉपरस्मिथ-विनोग्राड (Coppersmith-Winograd) जैसे उन्नत एल्गोरिदम बेहतर एसिम्प्टोटिक स्केलिंग (जैसे, $O(n^{2.37})$ ) प्रदान करते हैं, वे व्यावहारिक रूप से कुशलता से लागू करने में अत्यंत कठिन हैं।

लेखक अनुमानित मैट्रिक्स गुणन (approximate matrix multiplication) की आवश्यकता को संबोधित करते हैं, जहाँ लक्ष्य एक नियंत्रित मात्रा में सटीकता (सापेक्ष त्रुटि) के बदले कम्प्यूटेशनल जटिलता में महत्वपूर्ण कमी लाना है। मौजूदा यादृच्छिक (randomized) सन्निकटन विधियों में अक्सर व्यापक व्यावहारिक प्रभाव के लिए आवश्यक सटीकता या दक्षता की कमी होती है।

2. कार्यप्रणाली (Methodology)

इस शोध पत्र का मुख्य नवाचार एक "प्रथम-क्रम सन्निकटन" (first-order approximation) दृष्टिकोण का प्रस्ताव करना है। केवल दो मैट्रिसेस के ट्रंकेटेड संस्करणों को गुणा करने (शून्य-क्रम सन्निकटन) के बजाय, लेखक अधिक जानकारी कैप्चर करने के लिए "रेसिड्यू" (residue) पदों को शामिल करते हैं, जिससे जटिलता में उल्लेखनीय वृद्धि किए बिना सूचना का स्तर बढ़ जाता है।

दिए गए दो मैट्रिसेस $A$ और $B$ के लिए, उन्हें प्रमुख घटकों ( $A_i, B_k$ ) और एक घने रेसिड्यू ( $\Delta A, \Delta B$ ) के योग में विभाजित किया जाता है:
$A \approx \sum A_i + \Delta A, \quad B \approx \sum B_k + \Delta B$
प्रस्तावित प्रथम-क्रम सन्निकटन $M$ है:
$M \approx \sum (A_i B) + \sum (\Delta A B_k)$
यह दृष्टिकोण मैट्रिक्स गुणन को $O(n^3)$ के बजाय $O(n^2 \log n)$ या उपयोग किए गए डिकंपोज़िशन के आधार पर $O(kn^2)$ के रूप में स्केल करने की अनुमति देता है।

यह शोध पत्र तीन अलग-अलग डिकंपोज़िशन रणनीतियों का अन्वेषण करता है:

सिंगुलर वैल्यू डिकंपोज़िशन (SVD): $k$ सबसे बड़े सिंगुलर वैल्यू घटकों को निकालने के लिए यादृच्छिक एल्गोरिदम का उपयोग करता है। यह लो-रैंक (low-rank) मैट्रिसेस के लिए अत्यधिक प्रभावी है।
सर्कुलेंट डिकंपोज़िशन (CD): फास्ट फूरियर ट्रांसफॉर्म (FFT) का उपयोग करके एक मैट्रिक्स को $n$ सर्कुलेंट मैट्रिसेस में विभाजित करता है। यह उन मैट्रिसेस के लिए विशेष रूप से कुशल है जिनमें आवधिक संरचनाएं (जैसे, टोप्लिट्ज़ या हैंकेल मैट्रिसेस) होती हैं।
फूरियर-डोमेन स्पार्सिफिकेशन (Fourier-domain Sparsification): फूरियर सीरीज़ का उपयोग करके पंक्तियों (rows) और स्तंभों (columns) का विस्तार करता है और केवल सबसे प्रमुख आवृत्तियों (frequencies) को बनाए रखता है, जो प्रभावी रूप से फ्रीक्वेंसी डोमेन में मैट्रिक्स को स्पार्स (sparse) बनाता है।

3. मुख्य योगदान

प्रथम-क्रम सन्निकटन ढांचा (First-Order Approximation Framework): एक गणितीय ढांचा जो रेसिड्यू-घटक उत्पादों को शामिल करके मानक ट्रंकेटेड (शून्य-क्रम) गुणनों की तुलना में सापेक्ष त्रुटि को काफी कम कर देता है।
त्रुटि अनुमान सिद्धांत (Error Estimation Theory): लेखक अपेक्षित सापेक्ष त्रुटि के लिए कठोर सैद्धांतिक सीमाएं प्रदान करते हैं। वे प्रदर्शित करते हैं कि गुणन में त्रुटि व्यक्तिगत ट्रंकेशन त्रुटियों के गुणनफल से कम हो सकती है, और वे इन त्रुटियों का अनुमान लगाने के लिए विधियाँ प्रदान करते हैं (a priori - गुणन से पहले और a posteriori - गुणन के बाद)।
जटिलता में कमी: वे सिद्ध करते हैं कि एक उपयोगी टॉलरेंस (जैसे, 1% त्रुटि) के लिए, अंकगणितीय संचालन $O(n^2 \log n)$ के रूप में स्केल होते हैं, जो $O(n^3)$ की तुलना में भारी गति प्रदान करता है।
पूरकता विश्लेषण (Complementarity Analysis): शोध पत्र यह पहचानता है कि विशिष्ट मैट्रिक्स प्रकारों के लिए कौन सा डिकंपोज़िशन सबसे उपयुक्त है (जैसे, लो-रैंक के लिए SVD, आवधिक/संरचित मैट्रिसेस के लिए CD)।

4. परिणाम

लेखकों ने व्यापक संख्यात्मक प्रयोगों के माध्यम से अपने तरीकों को मान्य किया:

मैट्रिक्स प्रकार: उन्होंने सिमेट्रिक (Symmetric), टोप्लिट्ज़ (Toeplitz), हैंकेल (Hankel), DFT मॉडल और अनस्ट्रक्चर्ड रैंडम मैट्रिसेस सहित विभिन्न मैट्रिसेस का परीक्षण किया।
SVD प्रदर्शन: लो-रैंक और स्ट्रक्चर्ड मैट्रिसेस के लिए, प्रथम-क्रम SVD दृष्टिकोण ने पारंपरिक रैंडमाइज्ड लो-रैंक विधियों की तुलना में बहुत कम घटकों के साथ 1% सापेक्ष त्रुटि प्राप्त की।
CD प्रदर्शन: आवधिकता वाले मैट्रिसेस (जैसे, टोप्लिट्ज़) के लिए, सर्कुलेंट डिकंपोज़िशन अत्यधिक कुशल था और मैट्रिक्स रैंक पर निर्भर नहीं था।
लार्ज लैंग्वेज मॉडल्स (LLMs): OPT-125M और OPT-1.3B मॉडल्स से संबंधित एक वास्तविक अनुप्रयोग में, लेखकों ने प्रदर्शित किया कि प्रथम-क्रम सन्निकटन गति और सटीकता के बीच एक "पारेटो फ्रंट" (Pareto front) बनाता है।
- OPT-1.3B मॉडल के लिए, उन्होंने लगभग लॉसलेस परप्लेक्सिटी (सटीकता) बनाए रखते हुए प्रीफिलिंग चरण में 3.07x तक एंड-टू-एंड स्पीडअप हासिल किया।
रन-टाइम लाभ: Apple M4 Pro हार्डवेयर पर प्रयोगों ने दिखाया कि जैसे-जैसे मैट्रिक्स के आयाम (dimensions) बढ़ते हैं, प्रस्तावित तरीके नेटिव सटीक गुणन और मौजूदा रैंडमाइज्ड विधियों से बेहतर प्रदर्शन करते हैं।

5. महत्व

यह कार्य हाई-परफॉर्मेंस कंप्यूटिंग (HPC) और आर्टिफिशियल इंटेलिजेंस के क्षेत्र के लिए अत्यधिक महत्वपूर्ण है। अनुमानित त्रुटि सीमाओं के साथ मैट्रिक्स गुणन को अनुमानित करने का एक गणितीय रूप से सुदृढ़ तरीका प्रदान करके, यह निम्नलिखित पथ प्रशस्त करता है:

LLM इन्फरेंस को तेज करना: बड़े पैमाने के ट्रांसफार्मर मॉडल्स में "प्रीफिलिंग" चरण की विलंबता (latency) को कम करना।
ऊर्जा दक्षता: विशाल लीनियर अलजेब्रा वर्कलोड के लिए आवश्यक कुल FLOPs को कम करना, जो सीधे डेटा केंद्रों में कम बिजली खपत में परिवर्तित होता है।
स्केलेबिलिटी: ऐसे एल्गोरिदम प्रदान करना जो बढ़ते मैट्रिक्स आयामों के साथ बहुत बेहतर तरीके से स्केल करते हैं, जिससे बड़े डेटासेट और अधिक जटिल मॉडल्स को प्रोसेस करना संभव होता है।