Nested dissection
عددی تجزیے میں، نیسٹڈ ڈسیکشن گراف پارٹیشننگ پر مبنی لکیری مساوات کے غیر معمولی سمیٹرک سسٹمز کے حل کے لیے ایک ڈیویڈ اینڈ کونکیور ہیورسٹک ہے۔ نیسٹڈ ڈسیکشن متعارف کرایا گیا تھا ؛ نام گیریٹ برخوف نے تجویز کیا تھا۔ نیسٹڈ ڈسیکشن مندرجہ ذیل مراحل پر مشتمل ہوتا ہے: ایک غیر ہدایت شدہ گراف بنائیں جس میں عمودی لکیری مساوات کے نظام کی قطاریں اور کالموں کی نمائندگی کرتے ہیں، اور ایک کنارہ نظام کی نمائندگی کرنے والے اسپارس میٹرکس میں غیر صفر اندراج کی نمائندگی کرتا ہے۔ گراف کو بار بار ذیلی گرافوں میں تقسیم کرنے کے لیے جداکار، عمودی حصوں کے چھوٹے ذیلی سیٹ استعمال کیے جاتے ہیں جن کو ہٹانے سے گراف کو ذیلی گرافوں میں تقسیم کیا جا سکتا ہے جس میں عمودی حصوں کی تعداد کا زیادہ سے زیادہ مستقل حصہ ہوتا ہے۔ کلیسکی سڑنا (سمیٹرک میٹرکس کے لیے گوسیائی خاتمے کا ایک متغیر) انجام دیں، تقسیم کے تکراری ڈھانچے کے ذریعے متغیرات کے خاتمے کا حکم دیتے ہوئے: جداکار کو ہٹانے سے بننے والے دو ذیلی گرافوں میں سے ہر ایک کو پہلے ختم کر دیا جاتا ہے، اور پھر جداکار کے عمودی حصے کو ختم کر دیا جاتا ہے۔ اس الگورتھم کے نتیجے میں، فل-ان (چولسکی سڑنے میں پیدا ہونے والی غیر صفر میٹرکس اندراجات کا مجموعہ جو ان پٹ میٹرکس ڈھانچے کا حصہ نہیں ہے) تکراری تقسیم کے ہر درجے پر جداکار کے سائز کے زیادہ سے زیادہ مربع تک محدود ہے۔ خاص طور پر، پلانر گراف کے لیے (اکثر دو جہتی محدود عنصر کے طریقہ کار کے میش سے ماخوذ غیر معمولی لکیری نظاموں کے حل میں پیدا ہونے والے) نتیجے میں میٹرکس میں O (n log n) نان زیرو ہوتا ہے، جس کی وجہ پلانر سیپریٹر تھیوریم ہے جو سائز O () کے علیحدگی کاروں کی ضمانت دیتا ہے۔ صوابدیدی گرافوں کے لیے ایک نیسٹڈ ڈسیکشن ہوتا ہے جو زیادہ سے زیادہ عنصر کے اندر بھرنے کی ضمانت دیتا ہے، جہاں d زیادہ سے زیادہ ڈگری ہے اور m غیر صفر کی تعداد ہے۔ گراف کا سائیکل رینک، یا سمیٹرک بولین میٹرکس بھی دیکھیں، جو کہ چولسکی سڑن ورٹیکس جداکار نوٹ حوالہ جات انجام دینے کے لیے درکار کم از کم متوازی وقت کی پیمائش کرتا ہے۔ ۔ ۔ ۔ ۔ مبہم میٹرکس عددی لکیری الجبرا