🔢 mathematics

A fast solver for ill-conditioned linear systems using randomized stable solutions of its blocks

यह शोध पत्र एक उन्नत पंक्ति-आधारित यादृच्छिक ब्लॉक-काczmarz विधि प्रस्तुत करता है जो अत्यधिक दुर्बल-सशर्त (ill-conditioned) रैखिक प्रणालियों को कुशलतापूर्वक हल करने के लिए नियमितीकरण (regularization) और एक गतिशील प्रस्ताव वितरण (dynamic proposal distribution) का उपयोग करता है, जो अन्य पुनरावृत्ति संख्यात्मक विधियों के लिए एक प्री-सॉल्वर या आंतरिक पुनरावृत्ति के रूप में संभावित अनुप्रयोगों की पेशकश करता है।

मूल लेखक: Suvendu Kar, Murugesan Venkatapathi

प्रकाशित 2026-06-17

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

CC BY 4.0

मूल लेखक: Suvendu Kar, Murugesan Venkatapathi

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

कल्पना कीजिए कि आप एक विशाल, बिखरे हुए जिग्सॉ पज़ल (jigsaw puzzle) को सुलझाने की कोशिश कर रहे हैं जहाँ टुकड़े पूरी तरह से एक साथ नहीं बैठते। गणित और इंजीनियरिंग की दुनिया में, यह एक समीकरण प्रणाली (system of equations) को हल करने जैसा है जो "इल-कंडीशन्ड" (ill-conditioned) है। इसका मतलब है कि पज़ल इतना संवेदनशील है कि एक टुकड़े में छोटी सी गलती भी पूरे चित्र को बिगाड़ सकती है, या टुकड़े एक-दूसरे के इतने समान हैं कि यह पहचानना मुश्किल है कि कौन सा कहाँ जाएगा।

यह पेपर इस कठिन पज़ल को हल करने का एक नया, तेज़ तरीका पेश करता है। यहाँ बताया गया है कि यह कैसे काम करता है, सरल उपमाओं (analogies) का उपयोग करके।

समस्या: "डगमगाती मेज" (The Wobbly Table)

आमतौर पर, जब कंप्यूटर इन बिखरे हुए समीकरणों को हल करने की कोशिश करते हैं, तो वे ऐसे तरीकों का उपयोग करते हैं जो एक ऐसे व्यक्ति की तरह होते हैं जो एक समय में एक पैर पर दबाव डालकर डगमगाती हुई मेज को संतुलित करने की कोशिश कर रहा है। यदि मेज बहुत अस्थिर (ill-conditioned) है, तो एक पैर पर दबाव डालने से पूरी मेज जोर से हिल सकती है, या व्यक्ति बिना किसी प्रगति के गोल-गोल घूमते हुए फंस सकता है।

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

समाधान: "स्मार्ट ग्रुप पुश" (ROR-BK)

लेखक एक नई विधि प्रस्तावित करते हैं जिसे ROR-BK (Regularized Orthogonality and Residual based Block-Kaczmarz) कहा जाता है। एक समय में एक पैर को धक्का देने या भारी आधार बनाने के बजाय, वे तीन मुख्य ट्रिक्स वाले एक स्मार्ट रणनीति का उपयोग करते हैं:

1. "टीमवर्क" का दृष्टिकोण (Block Updates)
एक समय में एक समीकरण (एक पज़ल का टुकड़ा) को देखने के बजाय, कंप्यूटर उन्हें "ब्लॉक्स" या टीमों के रूप में समूह में बांट देता है। कल्पना कीजिए कि आप डगमगाती मेज को ठीक करने के लिए एक समय में एक ही पैर के बजाय पैरों के एक पूरे समूह पर दबाव डाल रहे हैं। यह व्यक्तिगत रूप से धक्का देने की तुलना में तेज़ और अधिक स्थिर है।

2. "बेस्ट फ्रेंड्स" का नियम (Orthogonality)
पेपर का सबसे बड़ा नवाचार यह है कि यह समूहों को चुनने का तरीका है।

पुराना तरीका: आप ऐसे समूहों को चुन सकते हैं जो एक-दूसरे के बहुत समान हों (जैसे तीन पैर जो सभी एक ही तरह से थोड़े मुड़े हुए हों)। उन्हें धकेलने से ज्यादा मदद नहीं मिलती क्योंकि वे दोहराव वाले (redundant) हैं।
नया तरीका (ROR-BK): एल्गोरिदम उन समूहों को खोजता है जो "ऑर्थोगोनल" (orthogonal) हैं—एक फैंसी गणितीय शब्द जिसका अर्थ है कि वे एक-दूसरे के लंबवत हैं, या सरल शब्दों में, वे एक-दूसरे से पूरी तरह से अलग हैं।
उपमा: कल्पना कीजिए कि आप एक कार को गड्ढे से बाहर धकेलने की कोशिश कर रहे हैं। यदि आपके पास बिल्कुल एक ही कोण से धक्का देने वाले तीन लोग हैं, तो यह अक्षम है। लेकिन यदि एक सामने से, एक बगल से और एक पीछे से धक्का देता है, तो वे सभी दिशाओं को कवर करते हैं और कार को बहुत तेज़ी से आगे बढ़ाते हैं। ROR-BK विधि लगातार जांचती है कि कौन सी समीकरणों की "टीमें" एक-दूसरे से सबसे अलग हैं और फिर उन्हें काम करने के लिए चुनती है।

3. "सेफ्टी नेट" (Regularization)
कभी-कभी, समीकरणों के सबसे अच्छे समूह भी थोड़े अस्थिर हो सकते हैं। समाधान को क्रैश होने से बचाने के लिए, यह विधि एक "सेफ्टी नेट" जोड़ती है जिसे रेगुलराइजेशन (regularization) कहा जाता है।

उपमा: इसे एक साइकिल के शॉक एब्जॉर्बर (shock absorber) की तरह समझें। जब आप किसी ऊबड़-खाबड़ रास्ते (संख्यात्मक त्रुटि) से टकराते हैं, तो शॉक एब्जॉर्बर उसे सुचारू बना देता है ताकि आप गिर न जाएं। यह समाधान को स्थिर रखता है, भले ही गणित कितना भी उलझा हुआ क्यों न हो।

4. "सबसे खराब पर ध्यान केंद्रित करना" (Dynamic Residuals)
इस विधि में एक "रेसिड्यूअल" (residual) ट्रैकर भी है। यह एक स्कोरकार्ड की तरह है जो बताता है कि पज़ल के कौन से हिस्से अभी भी सबसे अधिक खराब हैं।

उपमा: यदि आप दीवार पेंट कर रहे हैं और आप देखते हैं कि एक कोना अभी भी बिना पेंट के है, तो आप अगले स्थान को पेंट करने के लिए यादृच्छिक (randomly) रूप से कोई जगह नहीं चुनते। आप सीधे उस खराब कोने पर जाते हैं। ROR-BK उन समीकरणों को गतिशील रूप से पकड़कर और तुरंत ठीक करके ऐसा करता है जो सबसे बड़ी त्रुटियों का कारण बन रहे हैं।

यह एक बड़ी बात क्यों है?

लेखकों ने इस नई विधि का परीक्षण कई अन्य प्रसिद्ध सॉल्वर (जैसे GMRES और LSQR) और पुराने ब्लॉक तरीकों के विरुद्ध किया।

गति (Speed): अपने परीक्षणों में, ROR-BK अक्सर प्रतिस्पर्धा की तुलना में 2 से 50 गुना तेज़ था।
स्थिरता (Stability):ity: जब सबसे कठिन, "डगमगाती" समस्याओं के साथ व्यवहार किया गया, तो यह क्रैश नहीं हुआ या फंसा नहीं।
कोई भारी काम नहीं (No Heavy Lifting): इसने उन महंगे, कस्टम "प्री-कंडीशनिंग" आधारों को बनाए बिना इन समस्याओं को हल किया जिनकी अन्य तरीकों को आवश्यकता होती है।

वास्तविक दुनिया का उदाहरण: मेडिकल इमेजिंग

पेपर एक सीटी स्कैन (tomography) का व्यावहारिक उदाहरण दिखाता है।

परिदृश्य: कल्पना कीजिए कि बहुत कम एक्स-रे कोणों से मानव मस्तिष्क की स्पष्ट छवि बनाने की कोशिश की जा रही है। यह एक "गंभीर रूप से अंडरडिटरमाइंड" (severely underdetermined) समस्या है (पिक्सेल की संख्या के लिए बहुत कम सुराग हैं)।
परिणाम: जब लेखकों ने मस्तिष्क की स्पष्ट छवि बनाने के लिए ROR-BK का उपयोग किया, तो इसने अन्य तरीकों की तुलना में अधिक स्पष्ट चित्र (उच्च गुणवत्ता) बनाया और इसे बहुत तेज़ी से किया। इसने डेटा में "नॉइज़" (शोर/static) को बेहतर ढंग से संभाला, जिसके परिणामस्वरूप मस्तिष्क की अधिक स्पष्ट छवि प्राप्त हुई।

सारांश

यह पेपर एक नया "फास्ट सॉल्वर" प्रस्तुत करता है जो कठिन गणितीय समस्याओं को एक टीम स्पोर्ट्स की तरह मानता है। अकेले काम करने या भारी, नाजुक उपकरणों का उपयोग करने के बजाय, यह:

कार्यों को समूहों में बांटता है।
दक्षता को अधिकतम करने के लिए ऐसे समूहों को चुनता है जो एक-दूसरे से भिन्न हों।
क्रैश होने से बचने के लिए एक सेफ्टी नेट जोड़ता है।
तुरंत सबसे खराब त्रुटियों पर ध्यान केंद्रित करता है।

परिणामस्वरूप, यह एक ऐसी विधि है जो वर्तमान उपकरणों की तुलना में तेज़, अधिक स्थिर और कम सेटअप की आवश्यकता वाली है, जो इसे इंजीनियरिंग और विज्ञान में पाई जाने वाली "असंभव" गणितीय समस्याओं को हल करने के लिए उत्कृष्ट बनाती है।

समस्या विवरण
यह शोध पत्र सुसंगत रैखिक समीकरण प्रणालियों $Ax = b $को हल करने की चुनौती को संबोधित करता है, जहाँ$ A \in \mathbb{R}^{m \times n} $और$ b \in \mathbb{R}^{m \times 1}$ है। मुख्य ध्यान अत्यधिक इल-कंडीशन्ड (ill-conditioned) प्रणालियों पर है, जिनमें स्पार्स सिस्टम, डेंस लीस्ट-स्क्वायर समस्याएं, और काफी अधिक ओवर-डिटरमिन्ड या अंडर-डिटरमिन्ड मामले शामिल हैं। लेखक बताते हैं कि मानक पुनरावृत्ति विधियाँ (iterative methods), जैसे कि GMRES, इन प्रणालियों के साथ अक्सर संघर्ष करती हैं क्योंकि अवशेष नॉर्म (residual norm) को कम करने का अर्थ आवश्यक रूप से इल-कंडीशन्ड समस्याओं के लिए सापेक्ष त्रुटि (relative error) में अभिसरण (convergence) सुनिश्चित करना नहीं होता है। इसके अलावा, पारंपरिक प्रीकंडीशनिंग तकनीकें (जैसे ILU, Jacobi) बहुत बड़े कंडीशन नंबर वाले मैट्रिसेस पर लागू होने पर संख्यात्मक अस्थिरता, पिवट ब्रेकडाउन, या अत्यधिक फिल-इन (fill-in) से ग्रस्त हो सकती हैं, और वे ठीक उसी समय विफल हो जाती हैं जब मजबूत त्वरण (robust acceleration) की सबसे अधिक आवश्यकता होती है।

कार्यप्रणाली
लेखक रेगुलराइज्ड ऑर्थोगोनैलिटी एंड रेसिडुअल बेस्ड ब्लॉक-काचमार्ज़ (ROR-BK) नामक एक उन्नत एल्गोरिदम प्रस्तावित करते हैं। यह विधि रैंडमाइज्ड ब्लॉक-काचमार्ज़ ढांचे पर आधारित है लेकिन इसमें स्थिरता और अभिसरण में सुधार के लिए तीन विशिष्ट संवर्द्धन किए गए हैं:

डायनेमिक रेसिडुअल-आधारित एकत्रीकरण (Dynamic Residual-Based Aggregation): केवल निश्चित ब्लॉक्स पर निर्भर रहने के बजाय, यह विधि प्रत्येक पुनरावृत्ति (iteration) में वर्तमान रेसिडुअल वेक्टर के आधार पर समीकरणों के एक उपसमुच्चय (subset) को गतिशील रूप से एकत्रित करती है। विशेष रूप से, यह एक ब्लॉक बनाने के लिए उन पंक्तियों (rows) का चयन करती है जो वर्ग रेसिडुअल (squared residual) में सबसे अधिक योगदान देती हैं, जिसका लक्ष्य प्रत्येक चरण में रेसिडुअल नॉर्म को अधिक प्रभावी ढंग से कम करना है।
प्रभावी पारस्परिक ऑर्थोगोनैलिटी सैंपलिंग (Effective Mutual Orthogonality Sampling): यह विधि ब्लॉक जोड़ों के बीच ऑर्थोगोनैलिटी (Simple Orthogonal Block-Kaczmarz या SOBK विधि में प्रयुक्त) की अवधारणा को एकल ब्लॉक और अन्य सभी ब्लॉक्स के बीच "प्रभावी ऑर्थोगोनैलिटी" (effective orthogonality) के रूप में सामान्य बनाती है। एक सममित मैट्रिक्स $C$ की गणना की जाती है जहाँ प्रविष्टियाँ ब्लॉक सेंट्रॉइड्स के बीच प्रभावी कोण के कोसाइन (cosine) का प्रतिनिधित्व करती हैं। फिर ब्लॉक्स को एक ऐसे वितरण के आधार पर संभाव्यता से सैंपल किया जाता है जो उन ब्लॉक्स को प्राथमिकता देता है जिनका शेष सिस्टम के साथ उच्च संचयी ऑर्थोगोनैलिटी होता है।
रेगुलराइजेशन (Regularization): संख्यात्मक स्थिरता सुनिश्चित करने के लिए, विशेष रूप से जब ब्लॉक्स रैंक-डेफिशिएंट या इल-कंडीशन्ड हों, तो ब्लॉक अपडेट्स एक रेगुलराइज्ड स्यूडो-इनवर्स (pseudo-inverse) का उपयोग करते हैं। मानक मूर-पेनरोज़ इनवर्स $B^\dagger = B^T(BB^T)^{-1}$ के बजाय, विधि $B^T(BB^T + \mu I)^{-1}$ वाले रेगुलराइज्ड रूप का उपयोग करती है, जहाँ $\mu$ एक छोटा धनात्मक स्थिरांक है। इसे एक स्टोकेस्टिक प्रॉक्सिमल पॉइंट एल्गोरिदम के रूप में व्याख्यायित किया गया है।

एल्गोरिदम ऑर्थोगोनैलिटी-सैंपल किए गए ब्लॉक्स का उपयोग करके अपडेट करने और रेसिडुअल-आधारित डायनेमिक ब्लॉक्स का उपयोग करके अपडेट करने के बीच बारी-बारी से कार्य करता है। लेखक यह भी प्रदर्शित करते हैं कि यह विधि फ्लेक्सिबल GMRES (FAB-GMRES) सॉल्वर के लिए एक आंतरिक पुनरावृत्ति (inner iteration/preconditioner) के रूप में कार्य कर सकती है।

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

एल्गोरिद्मिक नवाचार: ROR-BK का परिचय, जो ब्लॉक-काचमार्ज़ ढांचे के भीतर रेसिडुअल-आधारित डायनेमिक ब्लॉक चयन, ग्लोबल ऑर्थोगोनैलिटी-अवेयर सैंपलिंग और टिखोनोव-शैली (Tikhonov-style) के रेगुलराइजेशन को जोड़ता है।
सैद्धांतिक विश्लेषण: शोध पत्र एक अभिसरण विश्लेषण (Theorems 2.3 और 2.4) प्रदान करता है जो दिखाता है कि यह विधि तब भी स्थिर अभिसरण प्राप्त करती है जब ब्लॉक्स संख्यात्मक रूप से रैंक-डेफिशिएंट होते हैं। यह स्थापित करता है कि त्रुटि में कमी $\mu$ द्वारा और ब्लॉक मैट्रिसेस के सबसे छोटे गैर-शून्य आइजनवैल्यू (eigenvalue) द्वारा सीमित है। प्रमेय 2.4 आगे तर्क देता है कि अधिकतम रेसिडुअल के आधार पर ब्लॉक्स का चयन त्रुटि के ऊपरी और निचले स्तरों (bounds) में सुधार करता है।
प्रीकंडीशनिंग रणनीति: अत्यधिक इल-कंडीशन्ड सिस्टम के समाधान को तेज करने के लिए एक स्पष्ट, संभावित रूप से अस्थिर बाहरी प्रीकंडिशनर की आवश्यकता के बिना, ROR-BK को GMRES के लिए एक प्री-सॉल्वर या आंतरिक पुनरावृत्ति के रूप में उपयोग करने का प्रस्ताव।

परिणाम
लेखकों ने ROR-BK की तुलना निम्नलिखित के विरुद्ध व्यापक संख्यात्मक प्रयोगों के माध्यम से की:

रैंडमाइज्ड सॉल्वर: सिंपल ऑर्थोगोनल ब्लॉक-काचमार्ज़ (SOBK) और टेल एवरेजड रेगुलराइज्ड ब्लॉक काचमार्ज़ (TA-ReBlocK-U)।
क्रायलोव सबस्पेस सॉल्वर: LSQR और जैकोबी, ILU, और रोबस्ट इनकम्प्लीट फैक्टराइजेशन (RIF) जैसे प्रीकंडिशनर्स के साथ विभिन्न GMRES वेरिएंट (AB/BA-GMRES)।

प्रदर्शन निष्कर्ष:

गति और पुनरावृत्ति (Iterations): परीक्षण मैट्रिसेस की एक विस्तृत श्रृंखला (यूनिवर्सिटी ऑफ फ्लोरिडा कलेक्शन से स्पार्स मैट्रिसेस और रैंडमली जेनरेटेड डेंस मैट्रिसेस सहित) में, ROR-BK ने लगातार SOBK और TA-ReBlocK-U की तुलना में कम पुनरावृत्तियों और कम CPU समय की आवश्यकता दिखाई। CPU समय के मामले में SOBK पर 1.23x से 5.17x तक और TA-ReBlocK-U पर 49.08x तक की गति वृद्धि देखी गई।
इल-कंडीशन्ड सिस्टम: अत्यधिक इल-कंडीशन्ड परिदृश्यों में (कंडीशन नंबर $10^{20}$ तक), कई क्रायलोव सॉल्वर और उनके प्रीकंडिश्न्ड संस्करण पुनरावृत्ति सीमा के भीतर अभिसरण करने में विफल रहे या बड़े सापेक्ष त्रुटि उत्पन्न की। ROR-BK इन मामलों में सफलतापूर्वक अभिसरित हुआ, और अक्सर कम सापेक्ष त्रुटियां प्राप्त कीं।
वास्तविक दुनिया का अनुप्रयोग: विधि का परीक्षण शोर वाले डेटा और गंभीर रूप से अंडर-डिटरमिन्ड सिस्टम वाले इमेज रिकंस्ट्रक्शन समस्याओं (पैरेलल-बीम टोमोग्राफी और MRI) पर किया गया। ROR-BK ने अन्य तरीकों की तुलना में, विशेष रूप से उन परिदृश्यों में जहाँ अन्य सॉल्वर अस्थिरता या विफलता से ग्रस्त थे, PSNR और SSIM के संदर्भ में बेहतर प्रदर्शन किया।

महत्व और दावे
शोध पत्र का दावा है कि ROR-BK उन रैखिक प्रणालियों को हल करने के लिए एक आशाजनक विकल्प प्रदान करता है जहाँ मैट्रिक्स $A$ इल-कंडीशन्ड है, जो स्पष्ट प्रीकंडिशनिंग की आवश्यकता के बिना कुशल सन्निकटन (approximations) प्राप्त करता है। लेखक तर्क देते हैं कि जबकि प्रीकंडिशनर का लक्ष्य मैट्रिक्स के कंडीशन नंबर को कम करना होता है, वे आवश्यक रूप से समस्या के स्वयं के कंडीशन नंबर को कम नहीं करते हैं और संख्यात्मक अस्थिरता पैदा कर सकते हैं। सिस्टम को ब्लॉक्स में विभाजित करके और प्रभावी ऑर्थोगोनैलिटी और रेगुलराइजेशन का उपयोग करके, ROR-BK संभावित रूप से सुव्यवस्थित (well-conditioned) उप-समस्याओं में सहवर्ती (covariant) समीकरणों को वितरित करता है।

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

समस्या: "डगमगाती मेज" (The Wobbly Table)

समाधान: "स्मार्ट ग्रुप पुश" (ROR-BK)

यह एक बड़ी बात क्यों है?

वास्तविक दुनिया का उदाहरण: मेडिकल इमेजिंग

सारांश

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