प्रस्तावना

समीकरणों के रैखिक प्रणालियों का संख्यात्मक समाधान लागू गणित, इंजीनियरिंग और आईटी उद्योग के कई क्षेत्रों में एक अनिवार्य कदम है, चाहे वह ग्राफिक्स के साथ काम कर रहा हो, एक हवाई जहाज के वायुगतिकी की गणना कर रहा है, या रसद का अनुकूलन कर रहा है। अब फैशनेबल "मशीन" भी इसके बिना बहुत आगे नहीं बढ़ेगी। इसके अलावा, रैखिक प्रणालियों का समाधान, एक नियम के रूप में, सभी कंप्यूटिंग लागतों का सबसे बड़ा प्रतिशत खाता है। यह स्पष्ट है कि इस महत्वपूर्ण घटक को अधिकतम गति अनुकूलन की आवश्यकता है।

अक्सर तथाकथित के साथ काम करते हैं विरल मैट्रेस - वे जिनके शून्य अन्य मूल्यों से अधिक परिमाण के आदेश हैं। यह, उदाहरण के लिए, अपरिहार्य है यदि आप आंशिक अंतर समीकरणों या कुछ अन्य प्रक्रियाओं के साथ काम कर रहे हैं जिसमें परिभाषित रैखिक संबंधों में उत्पन्न होने वाले तत्व केवल "पड़ोसियों" के साथ जुड़े हुए हैं। यहाँ शास्त्रीय भौतिकी में ज्ञात एक आयामी पोइसन समीकरण के लिए एक विरल मैट्रिक्स का एक संभावित उदाहरण है $$$- \ phi ^ {''} = f$ एक समान ग्रिड पर (हां, जबकि इसमें बहुत सारे शून्य नहीं हैं, लेकिन ग्रिड को पीसते समय वे स्वस्थ होंगे!):

$$

$$\ _ {pmatrix} 2 और -1 & 0 & 0 & 0 & -1 -1 और 2 और -1 & 0 & 0 & 0 & -1 & 2 & -1 & 0 \\ 0 & 0 & -1 & 2 & -1 \\ 0 & 0 & 0 & -1 & 2 \ end {pmatrix}$$

उनके विपरीत मेट्रिस - वे जिनमें वे शून्य की संख्या पर ध्यान नहीं देते हैं और बिना किसी अपवाद के सभी घटकों को ध्यान में रखते हैं - घने कहलाते हैं।

स्पार्स मैट्रीस अक्सर, विभिन्न कारणों से, एक संपीड़ित कॉलम प्रारूप में प्रस्तुत किया जाता है - संपीड़ित स्पार्स कॉलम (सीएससी)। यह विवरण दो पूर्णांक सरणियों और एक अस्थायी बिंदु का उपयोग करता है। मैट्रिक्स के पास सब कुछ है $$$nnz_A$ गैर शून्य और $$$एन$ कॉलम। मैट्रिक्स तत्वों को बिना किसी अपवाद के, बाएं से दाएं स्तंभों में सूचीबद्ध किया गया है। पहली सरणी $$$i_A$ लंबाई $$$nnz_A$ गैर-मैट्रिक्स मैट्रिक्स घटकों की पंक्ति संख्याएं शामिल हैं। दूसरा सरणी $$$j_A$ लंबाई $$$एन + 1$ इसमें ... नहीं, कॉलम संख्या नहीं है, क्योंकि तब मैट्रिक्स को समन्वित प्रारूप (निर्देशांक), या टर्नेरी (ट्रिपल) में लिखा जाएगा। और दूसरे सरणी में उन मैट्रिक्स घटकों के सीरियल नंबर होते हैं जिनके साथ कॉलम शुरू होता है, जिसमें अंत में एक अतिरिक्त डमी कॉलम भी शामिल है। अंत में, तीसरा सरणी $$$v_A$ लंबाई $$$nnz_A$ पहले से ही पहले सरणी के अनुरूप क्रम में, घटक स्वयं शामिल हैं। यहां, उदाहरण के लिए, इस धारणा के तहत कि मैट्रिक्स की पंक्तियों और स्तंभों की संख्या शून्य से शुरू होती है, किसी विशेष मैट्रिक्स के लिए

$$

$$A = \ start {pmatrix} 0 & 1 & 0 & 4 & -1 \\ 7 & 0 और 2.1 & 0 & 3 \\ 0 & 0 और 0 & 10 & 0 \ end {pmatrix}$$

सरणियाँ होंगी $$$i_A = \ {1, 0, 1, 0, 2, 0, 1 \}$ । $$$j_A = \ {0, 1, 2, 3, 5, 7 \}$ । $$$v_A = \ {7, 1, 2.1, 4, 10, -1, 3 \}$ ।

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

चलो एक वर्ग मैट्रिक्स के लिए कहते हैं $$$ए$ हम देख सकते हैं $$$ए = एलयू$ जहाँ $$$एल$ और $$$यू$ - क्रमशः निचला त्रिकोणीय और ऊपरी त्रिकोणीय मैट्रीस। पहला मतलब यह है कि इसमें विकर्ण के ऊपर एक शून्य है, दूसरा मतलब यह है कि यह विकर्ण से नीचे है। हमें वास्तव में यह अपघटन कैसे मिला - हमें अब दिलचस्पी नहीं है। यहाँ एक सरल अपघटन उदाहरण है:

$$

$$\ start {pmatrix} 1 & -1 और -1 \\ 2 & - 1 & -0.5 \\ 4 & -2 और -1.5 \ end {pmatrix} = \ start {pmatrix} 1 और 0 & 0 \\ 2 2 & 1 & 0 \\ 4 & 2 & 1 \ end {pmatrix} \ start {pmatrix} 1 & -1 और -1 \\ 0 & 1 & 1.5 \\ 0 & 0 & -0.5 \ end {pmatrix}$$

कैसे इस मामले में समीकरणों की प्रणाली को हल करने के लिए $$$अक्ष = च$ उदाहरण के लिए, दाईं ओर $$$f = \ start {pmatrix} 4 \\ 2 \\ 3 \ end {pmatrix}$ ? पहला चरण एक प्रत्यक्ष चाल (आगे का हल = आगे प्रतिस्थापन) है। हम निरूपित करते हैं $$$y: = Ux$ और प्रणाली के साथ काम करते हैं $$$लय = च$ । क्योंकि $$$एल$ - निचले त्रिकोणीय, क्रमिक रूप से चक्र में हम सभी घटकों को ढूंढते हैं $$$य$ ऊपर से नीचे:

$$

$$\ start {pmatrix} 1 & 0 & \ _ 2+ 2 & 1 & 0 \\ 4 & 2 & 1 \ end {pmatrix} \ start {pmatrix} y_1 \\ y_2 \\ y_3 \ end {pmatrix} = \ start {pmatrix} 4 \\ 2 \\ 3 \ end {pmatrix} \ _ y = \ start {pmatrix} 4 \\ -6 \\ -1 \ अंत {pmatrix}$$

केंद्रीय विचार है, खोजने पर $$$मैं$ वेक्टर घटक $$$य$ यह एक ही मैट्रिक्स नंबर के साथ एक कॉलम से गुणा किया जाता है $$$एल$ जो तब दाईं ओर से घटाया जाता है। मैट्रिक्स अपने आप ही बाएं से दाएं ढहने लगता है, आकार में कमी और अधिक से अधिक वेक्टर घटक पाए जाते हैं $$$य$ । इस प्रक्रिया को कॉलम एलिमिनेशन कहा जाता है।

दूसरा चरण एक पिछड़ी चाल (बैकवर्ड सॉल्व = बैकवर्ड प्रतिस्थापन) है। एक वेक्टर पाया गया $$$य$ हम तय करते हैं $$$Ux = y$ । यहां हम पहले से ही नीचे से घटकों के माध्यम से जाते हैं, लेकिन विचार समान रहता है: $$$मैं$ वें स्तंभ को सिर्फ मिले घटक से गुणा किया जाता है $$$x_i$ और दाईं ओर चलता है, और मैट्रिक्स दाईं से बाईं ओर ढह जाता है। नीचे दी गई तस्वीर में उदाहरण में वर्णित मैट्रिक्स के लिए पूरी प्रक्रिया का वर्णन किया गया है:

$$

$$\ small \ start {pmatrix} 1 & 0 & \\ 2 & 1 & 0 \\ 4 & 2 & 1 \ end {pmatrix} \ start {pmatrix} y_1 \\ y_2 \\ y_3 \ end / इसatrix} = \ start {pmatrix} 4 \\ 2 \\ 3 \ end {pmatrix} \ implies \ start {pmatrix} 1 & 0 \\ 2 और 1 \ end {pmatrix} \ start {pmatrix} y start \\ y_3 \ end {pmatrix } = \ start {pmatrix} -6 \\ -13 \ end {pmatrix} \ implies \ start {pmatrix} 1 \ end {pmatrix} \ start {pmatrix} y_3 \ end {pmatrix} = शुरुआत {pmatrix} -1 \ अंत {pmatrix}$$

$$

$$\ small \ {प्रारंभ {}} और -1 & -1 \\ 0 & 1 & 1.5 \\ 0 & 0 & -0.5 \ end {pmatrix} \ start {pmatrix} x_1 \\ x_2 \\ x_3 \ "एंड pmatrix} = \ start {pmatrix} 4 \\ -6 \\ -1 \ end {pmatrix} \ Rightarrow \ start {pmatrix} 1 & -1 \\ 0 & 1 \ end {pmatrix} \ start {iatrix} x_1 \ _ " {pmatrix} -3 \ end {pmatrix}$$

और हमारा निर्णय होगा $$$x = \ start {pmatrix} -3 \\ - 9 \\ 2 \ end {pmatrix}$ ।

यदि मैट्रिक्स घना है, अर्थात, यह किसी प्रकार के सरणी, एक-आयामी या दो-आयामी के रूप में पूरी तरह से दर्शाया गया है, और इसमें एक विशिष्ट तत्व तक पहुंच समय के साथ होती है $$$O (1)$ , तो मौजूदा अपघटन के साथ एक समान समाधान प्रक्रिया मुश्किल नहीं है और कोड करना आसान है, इसलिए हमने इस पर समय बर्बाद नहीं किया। यदि मैट्रिक्स विरल है तो क्या होगा? यहाँ, सिद्धांत रूप में, मुश्किल भी नहीं है। यहां आगे बढ़ने के लिए C ++ कोड है जिसमें समाधान है $$$x$ यह इनपुट डेटा की शुद्धता की जांच किए बिना, दाईं ओर की जगह के लिए लिखा गया है (CSC सरणियाँ निचले त्रिकोणीय मैट्रिक्स के अनुरूप हैं):

एल्गोरिथम 1:

void forward_solve (const std::vector<size_t>& iA, const std::vector<size_t>& jA, const std::vector<double>& vA, std::vector<double>& x) { size_t j, p, n = x.size(); for (j = 0; j < n; j++) //    { x[j] /= vA[jA[j]]; for (p = jA[j]+1; p < jA[j+1]; p++) x[iA[p]] -= vA[p] * x[j] ; } } 

सभी आगे की चर्चा निचले त्रिकोणीय प्रणाली को हल करने के लिए केवल आगे के स्ट्रोक की चिंता करेगी $$$Lx = f$ ।

टाई

लेकिन क्या होगा अगर सही पक्ष, अर्थात्। समान चिह्न के दाईं ओर वेक्टर $$$Lx = f$ क्या यह अपने आप में बड़ी संख्या में शून्य है? फिर शून्य पदों से जुड़ी गणना को छोड़ देना समझदारी है। इस मामले में कोड में परिवर्तन न्यूनतम हैं:

एल्गोरिथम 2:

 void fake_sparse_forward_solve (const std::vector<size_t>& iA, const std::vector<size_t>& jA, const std::vector<double>& vA, std::vector<double>& x) { size_t j, p, n = x.size(); for (j = 0; j < n; j++) //    { if(x[j]) { x[j] /= vA[jA [j]]; for (p = jA[j]+1; p < jA[j+1]; p++) x[iA[p]] -= vA[p] * x[j]; } } } 

केवल एक चीज जो हमने जोड़ी है, वह है if , जिसका उद्देश्य अंकगणितीय परिचालनों की संख्या को उनकी वास्तविक संख्या में कम करना है। यदि, उदाहरण के लिए, पूरे दाहिने हाथ में शून्य होते हैं, तो आपको कुछ भी गिनने की आवश्यकता नहीं है: समाधान दाहिने हाथ की ओर होगा।

सब कुछ बहुत अच्छा लग रहा है और निश्चित रूप से यह काम करेगा, लेकिन यहां, एक लंबे फोरप्ले के बाद, समस्या आखिरकार दिखाई दे रही है - बड़े सिस्टम के मामले में इस सॉल्वर का asymptotically कम प्रदर्शन। और लूप के for होने के तथ्य के कारण सभी। क्या समस्या है? यहां तक ​​कि अगर अंदर की स्थिति बहुत कम हो जाती है, तो शायद ही चक्र से दूर हो रहा है, और यह एल्गोरिथ्म की जटिलता पैदा करता है $$$O (N)$ जहाँ $$$एन$ मैट्रिक्स का आकार है। कोई फर्क नहीं पड़ता कि छोरों को आधुनिक संकलक द्वारा कैसे अनुकूलित किया जाता है, यह जटिलता खुद को बड़े के साथ महसूस करेगी $$$एन$ । विशेष रूप से आक्रामक जब पूरे वेक्टर $$$च$ पूरी तरह से शून्य शामिल हैं, क्योंकि, जैसा कि हमने कहा, फिर इस मामले में कुछ भी नहीं करें! एक भी अंकगणितीय ऑपरेशन नहीं! क्या माजरा है $$$O (N)$ कार्रवाई?

अच्छा, चलिए बताते हैं। फिर भी, आप केवल रन आइडल के for क्यों बर्दाश्त नहीं कर सकते, क्योंकि वास्तविक गणना वास्तविक संख्याओं के साथ, यानी उन है कि if अभी भी कुछ कम हो जाएगा? लेकिन तथ्य यह है कि दुर्लभ प्रवाह वाले दाहिने हाथ के साथ यह प्रत्यक्ष-प्रवाह प्रक्रिया अक्सर बाहरी चक्रों में उपयोग की जाती है और चोल्स्की अपघटन को कम करती है। $$$A = LL ^ T$ और एलयू अपघटन को छोड़ दिया। हां, हां, उन विस्तारों में से एक, बिना ऐसा करने की क्षमता के कि ये सभी प्रत्यक्ष और रिवर्स रैखिक प्रणालियों को हल करने में किस तरह से चलते हैं, सभी व्यावहारिक अर्थ खो देते हैं।

प्रमेय। यदि मैट्रिक्स सममित सकारात्मक निश्चित (एसपीडी) है, तो इसे इस रूप में दर्शाया जा सकता है $$$A = LL ^ T$ एक ही रास्ता जहाँ $$$एल$ - विकर्ण पर सकारात्मक तत्वों के साथ कम त्रिकोणीय मैट्रिक्स।

अत्यधिक विरल एसपीडी मैट्रिस के लिए, अप-लुकिंग चोल्स्की अपघटन का उपयोग किया जाता है। मैट्रिक्स-ब्लॉक रूप में अपघटन का प्रतिनिधित्व करने वाली योजनाएं

$$

$$\ start {pmatrix} \ mathbf {L} _ {11} & \ mathbf {0} \\ \ mathbf {l} _ {12} ^ T & l_ {22} \ end {pmatrix} \ {atatrix} \ _ mathbf {L} _ {11} ^ T & \ mathbf {l} _ {12} \\ \ mathbf {0} & l_ {22} \ end {pmatrix} = \ start {pmatrix} \ mathbf {A} _ { 11} और \ mathbf {a} _ {12} \\ \ mathbf {a} _ {12} ^ T & a_ {22} \ end {pmatrix},$$

संपूर्ण कारक प्रक्रिया को तार्किक रूप से केवल तीन चरणों में विभाजित किया जा सकता है।

एल्गोरिथम 3:

1. छोटे आयाम के चोल्स्की अपघटन की ऊपरी विधि $$$\ mathbf {L} _ {11} \ mathbf {L} _ {11} ^ T = \ mathbf {A} _ {11}$ (Recursion!)
2. कम त्रिकोणीय प्रणाली विरल दाईं ओर $$$\ mathbf {L} _ {11} \ mathbf {l} _ {12} = \ mathbf {a} _ {12}$ ( यहाँ यह है! )
3. गणना $$$l_ {22} = \ sqrt {a_ {22} - \ mathbf {l} _ {12} ^ T \ mathbf {l} _ {12}}$ (तुच्छ ऑपरेशन)

व्यवहार में, इसे इस तरह से लागू किया जाता है कि चरण 3 और 2 एक बड़े चक्र में और इस क्रम में किए जाते हैं। इस प्रकार, मैट्रिक्स को ऊपर से नीचे तक तिरछे ढंग से चलाया जाता है, जिससे मैट्रिक्स बढ़ता है $$$एल$ लूप के प्रत्येक पुनरावृत्ति पर लाइन द्वारा लाइन।

यदि इस तरह के एग्लोरिथेम में चरण 2 में आगे की जटिलता होगी $$$O (N)$ जहाँ $$$एन$ निम्न त्रिकोणीय मैट्रिक्स का आकार है $$$\ mathbf {L} _ {11}$ एक बड़े चक्र की मनमानी पुनरावृत्ति पर, फिर पूरे अपघटन की जटिलता कम से कम होगी $$$O (N ^ 2)$ ! ओह, मैं ऐसा नहीं चाहूंगा!

कला की अवस्था

कई एल्गोरिदम किसी तरह समस्याओं को सुलझाने में मानव कार्यों की नकल करने पर आधारित हैं। यदि आप किसी व्यक्ति को दाहिने हाथ के साथ एक त्रिभुजाकार रैखिक प्रणाली देते हैं, जिसमें केवल 1-2 गैर-शून्य होते हैं, तो निश्चित रूप से वह पहली बार दाईं ओर के हाथ की सदिश को अपनी आंखों के ऊपर से नीचे तक चलाता है (जो कि जटिलता का शापित चक्र है। $$$O (N)$ ! ) इन नॉनवेज को खोजने के लिए। फिर वह शून्य घटकों पर समय बर्बाद किए बिना केवल उनका उपयोग करेगा, क्योंकि उत्तरार्द्ध निर्णय को प्रभावित नहीं करेगा: यह मैट्रिक्स के विकर्ण घटकों में शून्य को विभाजित करने के लिए कोई मतलब नहीं है, साथ ही स्तंभ को शून्य से दाईं ओर गुणा करता है। यह उपरोक्त एल्गोरिथम है 2. कोई चमत्कार नहीं हैं। लेकिन क्या होगा अगर किसी व्यक्ति को तुरंत कुछ अन्य स्रोतों से नॉनज़रो घटकों की संख्या दी जाए? उदाहरण के लिए, यदि दाहिने हाथ की ओर कुछ अन्य मैट्रिक्स का एक स्तंभ है, जैसा कि चोल्स्की के अपघटन के साथ होता है, तो वहां हम इसके गैर-घटक घटकों तक त्वरित पहुंच प्राप्त करते हैं, यदि क्रमिक रूप से अनुरोध किया जाता है:

 //     j,     : for (size_t p = jA[j]; p < jA[j+1]; p++) //    vA[p]     iA[p]   j 

इस पहुंच की जटिलता है $$$O (nnz_j)$ जहाँ $$$nnz_j$ कॉलम जे में नॉनजरो घटकों की संख्या है। सीएससी प्रारूप के लिए भगवान का शुक्र है! जैसा कि आप देख सकते हैं, यह न केवल स्मृति को बचाने के लिए उपयोग किया जाता है।

इस मामले में, हम प्रत्यक्ष पाठ्यक्रम विधि द्वारा हल करते समय जो कुछ हो रहा है उसका सार पकड़ सकते हैं $$$Lx = f$ विरल मैट्रिस के लिए $$$एल$ और दाईं ओर $$$च$ । अपनी सांस पकड़ो: हम एक गैर-शून्य घटक लेते हैं $$$f_i$ दाईं ओर, हम इसी चर को पाते हैं $$$x_i$ द्वारा विभाजित किया जा रहा है $$$L_ {ii}$ और फिर, इस पाया चर द्वारा पूरे i-th कॉलम को गुणा करते हुए, हम इस कॉलम को दाईं ओर से घटाकर अतिरिक्त गैर-शून्य का परिचय देते हैं ! इस प्रक्रिया को अच्छी तरह से ... रेखांकन की भाषा में वर्णित किया गया है। इसके अलावा, उन्मुख और गैर-चक्रीय।

एक कम त्रिकोणीय मैट्रिक्स के लिए जो विकर्ण पर शून्य नहीं है, हम एक जुड़े ग्राफ को परिभाषित करते हैं। हम मानते हैं कि पंक्ति और स्तंभ संख्या शून्य से शुरू होती है।
परिभाषा। कम त्रिकोणीय मैट्रिक्स के लिए एक कनेक्टिविटी ग्राफ $$$एल$ आकार $$$एन$ , जिसका विकर्ण पर कोई शून्य नहीं है, इसे नोड्स का सेट कहा जाता है $$$V = \ {0, ..., N-1 \}$ और उन्मुख किनारों $$$E = \ {(जे, आई) | L_ {ij} \ ne 0 \}$ ।

उदाहरण के लिए, निम्न त्रिकोणीय मैट्रिक्स के लिए कनेक्शन ग्राफ कैसा दिखता है।

जिसमें संख्याएं केवल विकर्ण तत्व के क्रमिक संख्या के अनुरूप होती हैं, और बिंदु तिरछे नीचे गैर-शून्य घटकों को इंगित करते हैं:



परिभाषा। रीचैबिलिटी ओरिएंटेड ग्राफ $$$जी$ कई सूचकांकों पर $$$W \ subset V$ बहुत सारे सूचक कहते हैं $$$R_G (W) \ subset V$ किसी भी सूचकांक में $$ आप कुछ सूचकांक से ग्राफ के माध्यम से प्राप्त कर सकते हैं $$$w (z) \ _ W $ मे$ ।

उदाहरण: चित्र से ग्राफ के लिए $$$R_G (\ {0, 4 \}) = \ {0, 4, 5, 6 \}$ । यह स्पष्ट है कि यह हमेशा धारण करता है $$$W \ सब्सेट R_G (W)$ ।

यदि हम ग्राफ के प्रत्येक नोड को उस मैट्रिक्स के कॉलम नंबर के रूप में दर्शाते हैं, जो इसे उत्पन्न करता है, तो पड़ोसी नोड्स जिसमें इसके किनारों को इस कॉलम में नॉनज़ेरो घटकों की पंक्ति संख्याओं के लिए निर्देशित किया जाता है।

चलो $$$nnz (x) = \ {j | x_j \ ne 0 \ $ वेक्टर x में नॉनज़रो पोजिशन के अनुरूप सूचकांकों के सेट को दर्शाता है।

हिल्बर्ट की प्रमेय (नहीं, जिनके नाम से रिक्त स्थान का नाम नहीं है) $$$nnz (x)$ जहाँ $$$x$ वहाँ एक विरल कम त्रिकोणीय प्रणाली का एक समाधान वेक्टर है $$$Lx = f$ विरल दाईं ओर $$$च$ के साथ मेल खाता है $$$R_G (nnz (f))$ ।

अपने दम पर जोड़: प्रमेय में हम इस संभावना को ध्यान में नहीं रखते हैं कि स्तंभ को नष्ट करते समय दाईं ओर नॉनजरो संख्या शून्य हो सकती है, उदाहरण के लिए, 3 - 3 = 0. इस प्रभाव को संख्यात्मक रद्द कहा जाता है। इस तरह के अनायास होने वाले शून्य को ध्यान में रखना समय की बर्बादी है, और उन्हें गैर-पदों पर अन्य सभी संख्याओं के रूप में माना जाता है।

किसी दिए गए विरल दाएं हाथ से प्रत्यक्ष चालन करने की एक प्रभावी विधि, इस धारणा के तहत कि सूचकांकों द्वारा इसके गैर-शून्य घटकों तक हमारी सीधी पहुंच है, निम्नानुसार है।

1. हम "गहराई पहले खोज" विधि का उपयोग करके ग्राफ के माध्यम से चलाते हैं, अनुक्रमिक रूप से सूचकांक से शुरू करते हैं $$$i \ n nnz (f) $ मे$ दाईं ओर के प्रत्येक नॉनज़ेरो घटक। लेखन एक सरणी में नोड्स मिला $$$R_G (nnz (f))$ इस क्रम में ऐसा करते हुए कि हम ग्राफ पर वापस लौटते हैं! आक्रमणकारियों की सेना के साथ समानता से: हम क्रूरता के बिना देश पर कब्जा कर लेते हैं, लेकिन जब हम पीछे हटने लगे, तो हम क्रोधित होते हैं, इसके मार्ग में सब कुछ नष्ट कर देते हैं।
   यह ध्यान देने योग्य है कि यह बिल्कुल जरूरी नहीं है कि सूचकांकों की सूची $$$nnz (f)$ आरोही द्वारा सॉर्ट किया गया था जब इसे "डेप्थ-फर्स्ट सर्च" एल्गोरिदम के इनपुट के लिए खिलाया गया था। आप सेट पर किसी भी क्रम में शुरू कर सकते हैं $$$nnz (f)$ । सेट से संबंधित विभिन्न अनुक्रम $$$nnz (f)$ इंडेक्स अंतिम समाधान को प्रभावित नहीं करता है, जैसा कि हम उदाहरण में देखेंगे।
   
   इस चरण में किसी वास्तविक सरणी के ज्ञान की आवश्यकता नहीं है। $$$v_A$ ! प्रत्यक्ष विरल सॉल्वरों के साथ काम करते समय प्रतीकात्मक विश्लेषण की दुनिया में आपका स्वागत है!
   
2. हम समाधान के लिए आगे बढ़ते हैं, हमारे निपटान में एक सरणी होती है $$$R_G (nnz (f))$ पिछले चरण से। हम इस सरणी के रिकॉर्ड के रिवर्स ऑर्डर में कॉलम को नष्ट कर देते हैं। देखा!

उदाहरण

एक उदाहरण पर विचार करें जिसमें दोनों चरणों का विस्तार से प्रदर्शन किया गया है। मान लें कि हमारे पास निम्नलिखित फॉर्म का 12 x 12 मैट्रिक्स है:

संबंधित कनेक्टिविटी ग्राफ का रूप है:

नॉनजेरो को दाहिने हिस्से में केवल 3 और 5 के पदों पर रखें, अर्थात $$$nnz (f) = \ {3, 5 \}$ । लिखित क्रम में इन सूचकांकों से शुरू करते हुए, ग्राफ़ के माध्यम से चलते हैं। फिर "गहरी खोज" की विधि निम्नानुसार दिखाई देगी। पहले हम क्रम में सूचकांकों का दौरा करेंगे $$$3 \ _ से 8 $ 11 त$ , के रूप में दौरा किया अनुक्रमित करने के लिए भूल नहीं है। नीचे दिए गए आंकड़े में वे नीले रंग में छायांकित हैं:

जब वापस लौटते हैं, तो हम गैर-सहायक समाधान घटकों के सूचकांकों के हमारे सरणी में सूचकांक दर्ज करते हैं $$$nnz (x): = \ {रंग {नीला} {11}, \ रंग {नीला} 8, \ रंग {नीला} 3 \}$ । इसके बाद, चलाने का प्रयास करें $$$5 \ _8 to ...$ , लेकिन हम पहले से ही चिह्नित नोड 8 पर आते हैं, इसलिए हम इस मार्ग को नहीं छूते हैं और शाखा में जाते हैं $$$5 \ _9 \ _ से ...$ । इस रन का परिणाम होगा $$$5 \ _9 to10$ । हम नोड 11 पर नहीं जा सकते, क्योंकि यह पहले से ही लेबल है। तो, वापस जाएं और सरणी को पूरक करें $$$nnz (x)$ हरे रंग में चिह्नित नई पकड़: $$$nnz (x): = \ {रंग {नीला} {11}, \ रंग {नीला} 8, \ रंग {नीला} 3, \ रंग {हरा} {10}, \ रंग {हरा} 9, \ रंग {हरी} ५ \}$ । और यहाँ चित्र है:

मैला हरा नोड्स 8 और 11 वे हैं जिन्हें हम दूसरे रन के दौरान देखना चाहते थे, लेकिन नहीं कर सके पहले के दौरान पहले से ही दौरा किया।

तो सरणी $$$nnz (x) = R_G (nnz (f))$ का गठन किया। हम दूसरे चरण में पास होते हैं। एक सरल कदम: हम सरणी के माध्यम से चलाते हैं $$$nnz (x)$ रिवर्स ऑर्डर में (दाएं से बाएं), सॉल्यूशन वेक्टर के संबंधित घटकों को खोजते हुए $$$x$ मैट्रिक्स के विकर्ण घटकों द्वारा विभाजन $$$एल$ और कॉलम को दाईं ओर ले जाना। अन्य घटक $$$x$ जैसा कि वे शून्य थे, वे वैसे ही बने रहे। योजनाबद्ध रूप से, यह नीचे दिखाया गया है, जहां नीचे तीर उस क्रम को इंगित करता है जिसमें स्तंभ नष्ट हो गए हैं:

नोट: स्तंभों के विनाश के इस क्रम में, संख्या ३ बाद में संख्या ५, ९ और १० से सामने आएगी! कॉलम आरोही क्रम में नष्ट नहीं होते हैं, जो घने लोगों के लिए एक गलती होगी, अर्थात। अधूरा मैट्रिस। लेकिन विरल मैट्रिस के लिए, यह आम बात है। जैसा कि इस उदाहरण में गैर-शून्य मैट्रिक्स संरचना से देखा जा सकता है, कॉलम 5, 9 और 10 से कॉलम 3 का उपयोग करके प्रतिक्रिया में घटकों को विकृत नहीं किया जाएगा। $$$x_5$ । $$$x_9$ । $$$x_ {10}$ बिल्कुल नहीं, उनके पास सी है $$$x_3$ बस "कोई चौराहा नहीं।" हमारी विधि ने इसे ध्यान में रखा! इसी तरह, कॉलम 9 के बाद कॉलम 8 का उपयोग करने से घटक खराब नहीं होगा $$$x_9$ । महान एल्गोरिथ्म, है ना?

यदि हम सूचकांक 5 से पहले ग्राफ पर घूमते हैं, और फिर सूचकांक 3 से, तो हमारा सरणी होगा $$$nnz (x): = \ {रंग {नीला} {11}, \ रंग {नीला} 8, \ रंग {नीला} {10}, \ रंग {नीला} {9}, \ रंग {नीला} 5, \ रंग {हरा} 3 \}$ । इस एरे के उल्टे क्रम में कॉलम को नष्ट करने से पहले मामले की तरह ही समाधान मिलेगा!

हमारे सभी परिचालनों की जटिलता वास्तविक अंकगणितीय परिचालनों की संख्या और दायीं ओर नॉनज़रो घटकों की संख्या से होती है, लेकिन मैट्रिक्स के आकार से नहीं! हमने अपना लक्ष्य हासिल कर लिया है।

आलोचना

हालांकि! एक महत्वपूर्ण पाठक ध्यान देगा कि शुरुआत में बहुत धारणा है कि हमारे पास "अनुक्रमणिका द्वारा दाईं ओर के नॉनजेरो घटकों तक सीधी पहुंच" है, जिसका अर्थ है कि एक बार पहले हम ऊपर से नीचे की ओर दाईं ओर भागते हुए इन बहुत सूचकांकों को खोजें और उन्हें व्यवस्थित करें। सरणी में $$$nnz (f)$ , अर्थात्, पहले ही खर्च कर चुके हैं $$$O (N)$ एक्शन! इसके अलावा, ग्राफ रन की आवश्यकता है कि हम सबसे पहले अधिकतम संभव लंबाई की मेमोरी आवंटित करें (कहीं और आपको गहराई से खोजकर पाए गए इंडेक्स को लिखने की आवश्यकता है!) ताकि सरणी बढ़ने के दौरान आगे की प्राप्ति से पीड़ित न हो। $$$nnz (x)$ , और इसके लिए भी आवश्यकता है $$$O (N)$ संचालन! क्यों, वे कहते हैं, सभी उपद्रव?

लेकिन वास्तव में, एक विरल निचले त्रिकोणीय प्रणाली के एक बार के समाधान के लिए एक विरल दाहिने हाथ की ओर के साथ, मूल रूप से एक घने वेक्टर के रूप में परिभाषित किया गया है, यह ऊपर उल्लिखित सभी एल्गोरिदम पर डेवलपर समय बर्बाद करने का कोई मतलब नहीं है। ऊपर दिए गए एल्गोरिथ्म 2 द्वारा प्रस्तुत माथे विधि की तुलना में वे और भी धीमी हो सकती हैं। लेकिन, जैसा कि पहले ही उल्लेख किया गया है, यह उपकरण चोल्स्की के कारक के लिए अपरिहार्य है, इसलिए आपको टमाटर मुझ पर नहीं फेंकना चाहिए। दरअसल, एल्गोरिथम 3 को चलाने से पहले, अधिकतम लंबाई की सभी आवश्यक मेमोरी तुरंत आवंटित की जाती है और इसकी आवश्यकता होती है $$$O (N)$ समय। एक और स्तंभ चक्र में $$$ए$ सभी डेटा केवल एक निश्चित लंबाई वाले सरणी में ओवरराइट किए गए हैं $$$एन$ , और केवल उन पदों पर जिसमें यह पुनर्लेखन प्रासंगिक है, गैर-शून्य तत्वों तक सीधी पहुंच के लिए धन्यवाद। और यह ठीक इसी वजह से है कि दक्षता पैदा होती है!

C ++ कार्यान्वयन

कोड में डेटा संरचना के रूप में ग्राफ ही निर्माण के लिए आवश्यक नहीं है। सीधे मैट्रिक्स के साथ काम करते समय इसका उपयोग करना पर्याप्त है। एल्गोरिथ्म द्वारा सभी आवश्यक कनेक्टिविटी को ध्यान में रखा जाएगा। गहराई खोज निश्चित रूप से केले की पुनरावृत्ति का उपयोग करके कार्यान्वित की जाती है। यहां, उदाहरण के लिए, एक एकल प्रारंभ सूचकांक के आधार पर एक पुनरावर्ती गहराई खोज जैसा दिखता है:

 /* j -   iA, jA -    ,    CSC top -     nnz(x);     0 result -   N,    nnz(x)   0  top-1  marked -    N;      */ void DepthFirstSearch(size_t j, const std::vector<size_t>& iA, const std::vector<size_t>& jA, size_t& top, std::vector<size_t>& result, std::vector<int>& marked) { size_t p; marked[j] = 1; //   j   for (p = jA[j]; p < jA[j+1]; p++) //       j { if (!marked[iA[p]]) //  iA[p]   { DepthFirstSearch(iA[p], iA, jA, top, result, marked); //      iA[p] } } result[top++] = j; //  j   nnz(x) } 

यदि आप DepthFirstSearch में बहुत पहले कॉल में शून्य के बराबर top चर पास करते हैं, तो पूरी पुनरावर्ती प्रक्रिया के पूरा होने के बाद, top चर result सरणी में पाए गए अनुक्रमितों की संख्या के बराबर होगा। होमवर्क: एक और फ़ंक्शन लिखें जो दाईं ओर गैर- DepthFirstSearch घटकों के सूचकांकों की एक सरणी लेता है और उन्हें DepthFirstSearch से DepthFirstSearch फ़ंक्शन में क्रमिक रूप से पास करता है। इसके बिना, एल्गोरिथ्म पूरा नहीं होता है। कृपया ध्यान दें: वास्तविक संख्याओं की एक सरणी $$$वीए$ हम इसे फंक्शन में पास नहीं करेंगे, क्योंकि प्रतीकात्मक विश्लेषण की प्रक्रिया में इसकी आवश्यकता नहीं है।

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

 /* j -   N -   iA, jA -    ,    CSC top -     nnz(x) result -   N,     nnz(x)   top  ret-1 ,  ret -    marked -    N work_stack -     N */ size_t DepthFirstSearch(size_t j, size_t N, const std::vector<size_t>& iA, const std::vector<size_t>& jA, size_t top, std::vector<size_t>& result, std::vector<int>& marked, std::vector<size_t>& work_stack) { size_t p, head = N - 1; int done; result[N - 1] = j; //    while (head < N) { j = result[head]; //  j     if (!marked[j]) { marked[j] = 1; //   j   work_stack[head] = jA[j]; } done = 1; //    j      for (p = work_stack[head] + 1; p < jA[j+1]; p++) //    j { //   c   iA[p] if (marked[iA[p]]) continue; //  iA[p]  ,   work_stack[head] = p; //       j result[--head] = iA[p]; //       iA[p] done = 0; //   j    break; } if (done) //      j  { head++; //  j    result[top++] = j; //  j    } } return (top); } 

और यह वही है जो एक गैर-अक्षीय समाधान वेक्टर संरचना का जनरेटर पहले से ही जैसा दिखता है $$$nnz (x)$ :

 /* iA, jA -   ,    CSC iF -        f nnzf -      f result -   N,    nnz(x)   0  ret-1 ,  ret -    marked -    N,    work_stack -     N */ size_t NnzX(const std::vector<size_t>& iA, const std::vector<size_t>& jA, const std::vector<size_t>& iF, size_t nnzf, std::vector<size_t>& result, std::vector<int>& marked, std::vector<size_t>& work_stack) { size_t p, N, top; N = jA.size() - 1; top = 0; for (p = 0; p < nnzf; p++) if (!marked[iF[p]]) //        top = DepthFirstSearch(iF[p], N, iA, jA, vA, top, result, marked, work_stack); for (p = 0; p < top; p++) marked[result[p]] = 0; //   return (top); } 

अंत में, सब कुछ एक में मिलाकर, हम दुर्लभ त्रिकोणीय सॉल्वर को दायें हाथ की ओर रखते हुए लिखते हैं:

 /* iA, jA, vA -  ,    CSC iF -        f nnzf -      f vF -       f result -   N,    nnz(x)   0  ret-1 ,  ret -    marked -    N,    work_stack -     N x -    N,    ;     */ size_t lower_triangular_solve (const std::vector<size_t>& iA, const std::vector<size_t>& jA, const std::vector<double>& vA, const std::vector<size_t>& iF, size_t nnzf, const std::vector<double>& vF, std::vector<size_t>& result, std::vector<int>& marked, std::vector<size_t>& work_stack, std::vector<double>& x) { size_t top, p, j; ptrdiff_t px; top = NnzX(iA, jA, iF, nnzf, result, marked, work_stack); for (p = 0; p < nnzf; p++) x[iF[p]] = vF[p]; //    for (px = top; px > -1; px--) //     { j = result[px]; // x(j)   x [j] /= vA[jA[j]]; //   x(j) for (p = jA[j]+1; p < jA[j+1]; p++) { x[iA[p]] -= vA[p]*x[j]; //  j-  } } return (top) ; } 

हम देखते हैं कि हमारा चक्र केवल सरणी के सूचकांकों के माध्यम से चलता है $$$nnz (x)$ , पूरा सेट नहीं $$$0, 1, ..., एन - 1$ । हो गया!

एक कार्यान्वयन है जो markedमेमोरी को बचाने के लिए टैग की एक सरणी का उपयोग नहीं करता है । इसके बजाय, सूचकांकों का एक अतिरिक्त सेट उपयोग किया जाता है।$$$V_1$ सेट के साथ प्रतिच्छेद नहीं $$$V = \{0, ..., N - 1\}$जिसमें नोड अंकन प्रक्रिया के रूप में एक सरल बीजीय ऑपरेशन द्वारा एक-से-एक मैपिंग है। हालांकि, सस्ती स्मृति के हमारे युग में, इसे एक ही सरणी में सहेजना है$$$एन$ पूरी तरह से बेमानी लगता है।

निष्कर्ष में

एक नियम के रूप में, प्रत्यक्ष विधि द्वारा रैखिक समीकरणों की एक विरल प्रणाली को हल करने की प्रक्रिया को तीन चरणों में विभाजित किया गया है:

1. चरित्र विश्लेषण
2. सिवोल विश्लेषण के आंकड़ों के आधार पर संख्यात्मक कारक
3. घने दाहिने हाथ के साथ प्राप्त त्रिकोणीय प्रणालियों का समाधान

दूसरा चरण, संख्यात्मक कारक, सबसे अधिक संसाधन-खपत वाला हिस्सा है और अनुमानित समय के सबसे (> 90%) को नष्ट कर देता है। पहले चरण का उद्देश्य दूसरे की उच्च लागत को कम करना है। इस पोस्ट में प्रतीकात्मक विश्लेषण का एक उदाहरण प्रस्तुत किया गया था। हालांकि, यह पहला कदम है जिसमें डेवलपर की ओर से सबसे लंबे समय तक विकास और अधिकतम मानसिक लागत की आवश्यकता होती है। एक अच्छे प्रतीकात्मक विश्लेषण में ग्राफ़ और पेड़ों के सिद्धांत और "एल्गोरिथम वृत्ति" के कब्जे के ज्ञान की आवश्यकता होती है। दूसरे चरण को लागू करने के लिए अतुलनीय रूप से आसान है।
खैर, तीसरा चरण, कार्यान्वयन और अनुमानित समय दोनों में, ज्यादातर मामलों में सबसे अधिक स्पष्ट है।

विरल प्रणालियों के लिए प्रत्यक्ष तरीकों का एक अच्छा परिचय टिम डेविस में है , टेक्सास ए एंड एम विश्वविद्यालय में कंप्यूटर विज्ञान विभाग में एक प्रोफेसर , हकदार हैं "स्पार्स लीनियर सिस्टम्स के लिए प्रत्यक्ष तरीके "। ऊपर वर्णित एल्गोरिदम का वर्णन किया गया है। मैं खुद डेविस से परिचित नहीं हूं, हालांकि मैं खुद एक ही विश्वविद्यालय में काम करता था (हालांकि एक अलग संकाय में)। (!)। मैटलैब में इसके अलावा इस्तेमाल किया है, वह एक ही संकाय सूचीबद्ध खुद के अलावा अन्य कोई Bjarne Stroustrup पर भी जिस तरह से गूगल स्ट्रीट व्यू (OLS) में विद्युत जेनरेटर तस्वीर के लिए शामिल किया गया था, - .. सी के ++ निर्माता

शायद किसी दिन मैं विरल मैट्रिस या संख्यात्मक विधियों के बारे में कुछ और नहीं लिखूंगा जनरल में प्रकाशित किया गया था। सभी को अच्छा!