Nested dissection
संख्यात्मक विश्लेषण में, नेस्टेड विच्छेदन ग्राफ विभाजन के आधार पर रैखिक समीकरणों की विरल सममित प्रणालियों के समाधान के लिए एक विभाजन और विजय शोध है। नेस्टेड विच्छेदन की शुरुआत गैरेट बिरखॉफ द्वारा की गई थी। नेस्टेड विच्छेदन में निम्नलिखित चरण होते हैंः एक अनिर्दिष्ट ग्राफ बनाएं जिसमें शीर्ष रैखिक समीकरणों की प्रणाली की पंक्तियों और स्तंभों का प्रतिनिधित्व करते हैं, और एक किनारा प्रणाली का प्रतिनिधित्व करने वाले विरल मैट्रिक्स में एक गैर-शून्य प्रविष्टि का प्रतिनिधित्व करता है। आवर्ती रूप से ग्राफ को विभाजक, शीर्षों के छोटे उपसमुच्चय का उपयोग करके उपग्राफ में विभाजित करें, जिसके हटाने से ग्राफ को शीर्षों की संख्या के अधिक से अधिक एक स्थिर अंश के साथ उपग्राफ में विभाजित किया जा सकता है। चोल्स्की अपघटन (सममित मैट्रिक्स के लिए गॉसियन उन्मूलन का एक प्रकार) करें, विभाजन की पुनरावर्ती संरचना द्वारा चर के उन्मूलन का आदेश देते हुएः विभाजक को हटाकर बनाए गए दो उपग्राफ में से प्रत्येक को पहले समाप्त कर दिया जाता है, और फिर विभाजक शीर्ष को समाप्त कर दिया जाता है। इस एल्गोरिथम के परिणामस्वरूप, फिल-इन (चोल्स्की अपघटन में बनाई गई गैर-शून्य मैट्रिक्स प्रविष्टियों का सेट जो इनपुट मैट्रिक्स संरचना का हिस्सा नहीं हैं) पुनरावर्ती विभाजन के प्रत्येक स्तर पर विभाजक आकार के अधिकतम वर्ग तक सीमित है। विशेष रूप से, समतल ग्राफ के लिए (अक्सर द्वि-आयामी परिमित तत्व विधि जाल से प्राप्त विरल रैखिक प्रणालियों के समाधान में उत्पन्न होने वाले) परिणामी मैट्रिक्स में ओ (एन लॉग एन) गैर-शून्य होता है, जो समतल विभाजक प्रमेय के कारण आकार ओ () के विभाजक की गारंटी देता है। मनमाने आलेखों के लिए एक नेस्टेड विच्छेदन होता है जो इष्टतम के कारक के भीतर भरने की गारंटी देता है, जहां d अधिकतम डिग्री है और m गैर-शून्य की संख्या है। ग्राफ की चक्र श्रेणी, या एक सममित बूलियन मैट्रिक्स भी देखें, जो चोल्स्की अपघटन वर्टेक्स विभाजक नोट्स संदर्भों को करने के लिए आवश्यक न्यूनतम समानांतर समय को मापता है। .. .. .. .. विरल मैट्रिक्स संख्यात्मक रैखिक बीजगणित