Nested dissection
সংখ্যাসূচক বিশ্লেষণে, গ্রাফ বিভাজনের উপর ভিত্তি করে রৈখিক সমীকরণের বিরল প্রতিসম ব্যবস্থার সমাধানের জন্য নেস্টেড বিচ্ছিন্নকরণ একটি বিভাজন এবং জয় অনুসন্ধানমূলক। নেস্টেড বিচ্ছিন্নকরণ দ্বারা প্রবর্তিত হয়েছিল; নামটি গ্যারেট বারখফ দ্বারা প্রস্তাবিত হয়েছিল। নেস্টেড বিচ্ছিন্নকরণ নিম্নলিখিত ধাপগুলি নিয়ে গঠিতঃ একটি অনির্দিষ্ট গ্রাফ তৈরি করুন যেখানে শীর্ষগুলি রৈখিক সমীকরণের পদ্ধতির সারি এবং কলামগুলির প্রতিনিধিত্ব করে এবং একটি প্রান্ত সিস্টেমের প্রতিনিধিত্বকারী বিরল ম্যাট্রিক্সে একটি অ-শূন্য প্রবেশের প্রতিনিধিত্ব করে। পুনরাবৃত্তিমূলকভাবে গ্রাফটিকে বিভাজক, শীর্ষগুলির ছোট উপসেট ব্যবহার করে উপগ্রাফগুলিতে বিভক্ত করুন যার অপসারণ গ্রাফটিকে শীর্ষগুলির সংখ্যার সর্বাধিক একটি ধ্রুবক ভগ্নাংশ সহ উপগ্রাফগুলিতে বিভক্ত করার অনুমতি দেয়। পার্টিশনের পুনরাবৃত্তিমূলক কাঠামো দ্বারা ভেরিয়েবলগুলি অপসারণের আদেশ দিয়ে চোলস্কি ডিকম্পোসিশন (প্রতিসম ম্যাট্রিক্সের জন্য গাউসিয়ান নির্মূলের একটি রূপ) সম্পাদন করুনঃ বিভাজক অপসারণের মাধ্যমে গঠিত দুটি উপগ্রাফগুলির প্রত্যেকটি প্রথমে বাদ দেওয়া হয় এবং তারপরে বিভাজকের শীর্ষগুলি বাদ দেওয়া হয়। এই অ্যালগরিদমের ফলস্বরূপ, ফিল-ইন (ইনপুট ম্যাট্রিক্স কাঠামোর অংশ নয় এমন চোলস্কি পচনে তৈরি অ-শূন্য ম্যাট্রিক্স এন্ট্রিগুলির সেট) পুনরাবৃত্তিমূলক বিভাজনের প্রতিটি স্তরে বিভাজকের আকারের সর্বাধিক বর্গক্ষেত্রের মধ্যে সীমাবদ্ধ। বিশেষত, সমতলীয় গ্রাফের জন্য (দ্বি-মাত্রিক সীমাবদ্ধ উপাদান পদ্ধতি জাল থেকে প্রাপ্ত বিরল রৈখিক ব্যবস্থার সমাধানে প্রায়শই উদ্ভূত হয়) ফলস্বরূপ ম্যাট্রিক্সে ও (এন লগ এন) ননজেরোস থাকে, যা সমতলীয় বিভাজক উপপাদ্যের কারণে ও () আকারের বিভাজকের নিশ্চয়তা দেয়। নির্বিচারে গ্রাফের জন্য একটি নেস্টেড বিভাজন রয়েছে যা সর্বোত্তম ফ্যাক্টরের মধ্যে পূরণের নিশ্চয়তা দেয়, যেখানে d হল সর্বাধিক ডিগ্রি এবং m হল অ-শূন্যের সংখ্যা। এছাড়াও একটি গ্রাফের চক্র র্যাঙ্ক বা একটি প্রতিসম বুলিয়ান ম্যাট্রিক্স দেখুন, যা কোলেস্কি ডিকম্পোজিশন ভার্টেক্স সেপারেটর নোটস রেফারেন্স সম্পাদনের জন্য প্রয়োজনীয় ন্যূনতম সমান্তরাল সময় পরিমাপ করে। । । । । বিক্ষিপ্ত ম্যাট্রিক্স সংখ্যাসূচক রৈখিক বীজগণিত