The double splitting iteration method for solving the large indefinite least squares problem

तकनीकी सारांश: बड़े अनिश्चित न्यूनतम वर्ग (Indefinite Least Squares) समस्याओं के लिए डबल स्प्लिटिंग इटरेशन विधि

समस्या विवरण
यह शोध पत्र बड़े पैमाने की अनिश्चित न्यूनतम वर्ग (Indefinite Least Squares - ILS) समस्याओं को हल करने से जुड़ी कम्प्यूटेशनल चुनौतियों को संबोधित करता है, जिन्हें अनिश्चित द्विघात रूप (indefinite quadratic form) $(b - Ax)^T J (b - Ax)$ को न्यूनतम करने के रूप में तैयार किया गया है, जहाँ $A \in \mathbb{R}^{m \times n}$ एक बड़ा विरल (sparse) आव्यूह है, $b \in \mathbb{R}^m$ है, और $J = \text{diag}(I_p, -I_q)$ एक सिग्नेचर आव्यूह है जहाँ $p+q=m$। जब $pq > 0$ होता है, तो यह समस्या एक सामान्य समीकरण (normal equation) $A^T J A x = A^T J b$ की ओर ले जाती है जिसमें एक हेसियन मैट्रिक्स (Hessian matrix) शामिल होता है जो धनात्मक निश्चित (positive definite) नहीं होता है। जबकि छोटे सघन (dense) समस्याओं के लिए प्रत्यक्ष विधियाँ मौजूद हैं, बड़े पैमाने की प्रणालियों के लिए पुनरावृत्ति योजनाएँ (iterative schemes) अधिक उपयुक्त होती हैं। इस समस्या के लिए मौजूदा अत्याधुनिक इटरेटिव सॉल्वर मुख्य रूप से गुणांक आव्यूह $A^T J A = M - N$ के एकल विभाजन (single splitting) रणनीतियों पर निर्भर करते हैं, जैसे कि स्प्लिटिंग-आधारित (SP), जनरलाइज्ड SP (GSP), और अल्टरनेटिंग डायरेक्शन इम्प्लिसिट (ADI) विधियाँ।

कार्यप्रणाली
लेखक एक नवीन डबल स्प्लिटिंग (DS) इटरेशन विधि प्रस्तावित करते हैं। पारंपरिक दृष्टिकोणों के विपरीत, जो गुणांक आव्यूह को दो भागों ($M - N$) में विभाजित करते हैं, यह विधि तीन-भाग वाले अपघटन (decomposition) का उपयोग करती है:
$$A^T J A = P - R - S$$
जहाँ $P$ एक गैर-विलक्षण (nonsingular) आव्यूह है। GSP विधि की संरचना से प्रेरित होकर, लेखक विभाजन $A = [A_1; A_2]$ के आधार पर विशिष्ट आव्यूह परिभाषित करते हैं:

• $P = \alpha I + A_1^T A_1$ (सिमेट्रिक पॉजिटिव डेफिनिट, SPD)
• $R = A_2^T A_2$ (सिमेट्रिक)
• $S = \alpha I$ (सिमेट्रिक)
  जहाँ $\alpha > 0$ एक दिया गया पैरामीटर है।

यह अपघटन एक दो-चरणीय स्थिर पुनरावृत्ति योजना (two-step stationary iteration scheme) की ओर ले जाता है:
$$x_{k+1} = P^{-1} R x_k + P^{-1} S x_{k-1} + P^{-1} A^T J b$$
यह सूत्र पिछले दो इटरेट्स ($x_k$ और $x_{k-1}$) से जानकारी को समाहित करता है, जो इसे SP और GSP विधियों की एक-चरणीय प्रकृति से अलग करता है। इस योजना के अभिसरण (convergence) का विश्लेषण संबद्ध ब्लॉक इटरेशन मैट्रिक्स $W$ के स्पेक्ट्रल रेडियस $\rho(W)$ की जांच करके किया जाता है। लेखक $W$ के आइगेनवैल्यू $\lambda$ के लिए एक स्केलर द्विघात समीकरण व्युत्पन्न करते हैं और द्विघात समीकरणों के मूलों (roots) से संबंधित एक लेम्मा का उपयोग करके यह सिद्ध करते हैं कि सभी $\alpha > 0$ के लिए $|\lambda| < 1$ है।

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

1. नवीन इटरेटिव फ्रेमवर्क: यह शोध पत्र एक ठोस डबल स्प्लिटिंग रणनीति प्रस्तुत करता है जो विशेष रूप से ILS समस्याओं से उत्पन्न होने वाले सामान्य समीकरणों के लिए तैयार की गई है, जो प्रमुख एकल विभाजन प्रतिमानों के लिए एक विशिष्ट विकल्प प्रदान करती है।
2. अनकंडीशनल कन्वर्जेंस प्रूफ: लेखक एक कठोर स्पेक्ट्रल विश्लेषण प्रदान करते हैं जो यह प्रदर्शित करता है कि प्रस्तावित DS इटरेशन विधि किसी भी धनात्मक पैरामीटर $\alpha$ के लिए बिना किसी शर्त के (unconditionally) अभिसरित होती है। इस परिणाम को पूर्व साहित्य में पाए जाने वाले हर्मिटियन पॉजिटिव डेफिनिट मैट्रिसेस के मौजूदा अभिसरण मानदंडों से जोड़कर और अधिक स्पष्ट किया गया है।
3. एल्गोरिदम कार्यान्वयन: एक विस्तृत एल्गोरिदम (एल्गोरिदम 2.1) प्रस्तुत किया गया है, जो गणनात्मक चरणों को रेखांकित करता है, जिसमें SPD आव्यूह $P$ को उलटने (invert करने) के लिए चोलेस्की अपघटन (Cholesky decomposition) का उपयोग शामिल है।

संख्यात्मक परिणाम
DS विधि के प्रदर्शन का मूल्यांकन करने के लिए SP, GSP और ADI विधियों के विरुद्ध दो संख्यात्मक प्रयोग किए गए:

• उदाहरण 3.1 (सघन आव्यूह): यादृच्छिक बड़े पैमाने के सघन आव्यूहों का उपयोग करके, DS विधि का परीक्षण विभिन्न आयामों ($m$ तक 54,000) के साथ किया गया। एक इष्टतम पैरामीटर $\alpha=1$ के साथ, DS विधि ठीक 2 इटरेशन में अभिसरित हुई। जबकि SP और GSP भी 1 इटरेशन में अभिसरित हुए, DS विधि ने काफी कम CPU समय प्राप्त किया (जैसे, $m=51,000$ पर GSP के ~75s के मुकाबले ~4.8s)।
• उदाहरण 3.2 (विरल आव्यूह): टोटल लीस्ट स्क्वायर्स समस्याओं से प्राप्त आव्यूहों का उपयोग करके, DS विधि का परीक्षण विरल संरचनाओं के साथ किया गया। इष्टतम पैरामीटर $\alpha=10^{-4}$ के साथ, DS विधि ने फिर से 2 इटरेशन में अभिसरण प्राप्त किया। इसने सभी परीक्षण किए गए आकारों ( $m=8,192$ तक) में गणनात्मक समय के मामले में एकल विभाजन विधियों को लगातार पछाड़ दिया, जिससे बढ़ती समस्या के आकार के साथ भी बेहतर दक्षता प्रदर्शित हुई।

महत्व और दावे
शोध पत्र का दावा है कि प्रस्तावित डबल स्प्लिटिंग इटरेशन प्रतिमान पारंपरिक एकल विभाजन दृष्टिकोणों पर एक रचनात्मक सुधार प्रदान करता है। प्राथमिक महत्व विधि की तेज़ अभिसरण गति (CPU समय के संदर्भ में) और मजबूती (robustness) प्राप्त करने की क्षमता में निहित है। लेखक इस बात पर जोर देते हैं कि हालांकि इस विधि के लिए दो पिछले इटरेट्स की आवश्यकता होती है, लेकिन इस ऐतिहासिक जानकारी को शामिल करने से एकल-चरणीय SP, GSP और ADI विधियों की तुलना में गणनात्मक लागत में पर्याप्त कमी आती है। यह कार्य भविष्य के अनुसंधान के लिए पद्धतिगत संदर्भ प्रदान करता है और एडेप्टिव पैरामीटर चयन और अन्य प्रकार की अनिश्चित रैखिक प्रणालियों में संभावित विस्तार का सुझाव देता है।