क्रायलोव सबस्पेस विधियाँ

क्रायलोव सबस्पेस विधियाँ बड़े विरल रैखिक प्रणालियों को बार-बार मैट्रिक्स-वेक्टर उत्पादों द्वारा उत्पन्न सबस्पेस से सर्वोत्तम सन्निकटन निकालकर हल करती हैं, जिसके लिए मैट्रिक्स की प्रविष्टियों के बजाय केवल उसकी क्रिया की आवश्यकता होती है।

Definition

एक क्रायलोव सबस्पेस विधि एक पुनरावृत्त सॉल्वर है जो, m-वें चरण में, अवशिष्ट और मैट्रिक्स के तहत इसकी क्रमिक छवियों द्वारा फैले m-आयामी क्रायलोव सबस्पेस में एक अनुमानित समाधान चाहता है, एक प्रक्षेपण या न्यूनीकरण स्थिति द्वारा पुनरावृत्ति का चयन करता है।

Scope

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

Core questions

• क्रायलोव सबस्पेस क्या है, और इसके लिए एक ऑर्थोनॉर्मल आधार को stably कैसे बनाया जाता है?
• सममित धनात्मक-निश्चित प्रणालियों के लिए संयुग्मी ग्रेडिएंट विधि इष्टतम और लघु-पुनरावृत्ति क्यों है?
• GMRES सामान्य असममित प्रणालियों को कैसे संभालता है, और इसे बढ़ते भंडारण की आवश्यकता क्यों होती है?
• मैट्रिक्स के स्पेक्ट्रल गुण अभिसरण की दर को कैसे निर्धारित करते हैं?

Key theories

संयुग्मी ग्रेडिएंट विधि

सममित धनात्मक-निश्चित प्रणालियों के लिए, संयुग्मी ग्रेडिएंट विधि क्रायलोव सबस्पेस पर त्रुटि के ऊर्जा मानदंड को एक छोटी तीन-अवधि की पुनरावृत्ति का उपयोग करके कम करती है, सटीक अंकगणित में अधिकतम n चरणों में अभिसरण करती है और जब आइगेनवैल्यूज़ क्लस्टर होते हैं तो कहीं अधिक तेज़ी से अभिसरण करती है।

GMRES और अर्नोल्डी प्रक्रिया

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

Mechanisms

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

Clinical relevance

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

History

संयुग्मी ग्रेडिएंट विधि को हेस्टेन्स और स्टीफेल ने 1952 में और अंतर्निहित लैंक्ज़ोस प्रक्रिया को 1950 में प्रस्तुत किया था; पुनरावृत्त सॉल्वर के रूप में उनकी पूरी शक्ति को 1970 के दशक में पहचाना गया, और 1986 में साद और शुल्त्स द्वारा GMRES के विकास और स्थिर बायोरथोगोनल विधियों ने इस दृष्टिकोण को सामान्य असममित प्रणालियों तक विस्तारित किया।

Key figures

• Magnus Hestenes
• Eduard Stiefel
• Cornelius Lanczos
• Yousef Saad
• Henk van der Vorst

Seminal works

• saad2003
• greenbaum1997

Frequently asked questions

संयुग्मी ग्रेडिएंट विधि केवल सममित धनात्मक-निश्चित मैट्रिसेस के लिए ही क्यों काम करती है?

इसकी छोटी, कुशल पुनरावृत्ति और ऊर्जा मानदंड में इसकी इष्टतमता मैट्रिक्स के सममित धनात्मक-निश्चित होने पर निर्भर करती है। सममित अनिश्चित या असममित मैट्रिसेस के लिए, MINRES या GMRES जैसी विभिन्न विधियों की आवश्यकता होती है, सामान्यतः प्रति चरण अधिक भंडारण या कार्य के साथ।

GMRES को इतनी अधिक मेमोरी की आवश्यकता क्यों होती है?

एक सामान्य असममित मैट्रिक्स के लिए कोई छोटी पुनरावृत्ति नहीं होती है जो क्रायलोव आधार को ऑर्थोगोनल रखती है, इसलिए GMRES को अवशिष्ट को कम करने के लिए प्रत्येक आधार वेक्टर को संग्रहीत करना पड़ता है। पुनरारंभ किया गया GMRES समय-समय पर आधार को त्यागकर मेमोरी को सीमित करता है, जिसकी लागत धीमी अभिसरण होती है।