Nested dissection
આંકડાકીય વિશ્લેષણમાં, નેસ્ટેડ ડિસેક્શન એ ગ્રાફ પાર્ટીશનિંગ પર આધારિત રેખીય સમીકરણોની વિરલ સમપ્રમાણ પ્રણાલીઓના ઉકેલ માટે વિભાજન અને વિજય શોધ છે. નેસ્ટેડ ડિસેક્શન દ્વારા રજૂ કરવામાં આવ્યું હતું; નામ ગેરેટ બિરખોફ દ્વારા સૂચવવામાં આવ્યું હતું. નેસ્ટેડ વિચ્છેદનમાં નીચેના પગલાંઓનો સમાવેશ થાય છેઃ એક દિશાહીન આલેખ બનાવો જેમાં શિરોબિંદુઓ રેખીય સમીકરણોની પ્રણાલીની પંક્તિઓ અને સ્તંભોનું પ્રતિનિધિત્વ કરે છે, અને ધાર પ્રણાલીનું પ્રતિનિધિત્વ કરતા વિરલ મેટ્રિક્સમાં બિન-શૂન્ય એન્ટ્રીનું પ્રતિનિધિત્વ કરે છે. પુનરાવર્તિત રીતે ગ્રાફને વિભાજક, શિરોબિંદુઓના નાના સબસેટનો ઉપયોગ કરીને સબગ્રાફમાં વિભાજિત કરો, જેને દૂર કરવાથી ગ્રાફને શિરોબિંદુઓની સંખ્યાના મહત્તમ અચળ અપૂર્ણાંક સાથે સબગ્રાફમાં વિભાજિત કરવાની મંજૂરી મળે છે. પાર્ટીશનના પુનરાવર્તિત માળખા દ્વારા ચલને દૂર કરવાનો ક્રમ આપતા, કોલેસ્કી વિઘટન (સપ્રમાણ મેટ્રિસીસ માટે ગૌસીયન નાબૂદીનો એક પ્રકાર) કરો, વિભાજકને દૂર કરીને રચાયેલા બે પેટા આલેખમાંથી દરેકને પહેલા દૂર કરવામાં આવે છે, અને પછી વિભાજક શિરોબિંદુઓને દૂર કરવામાં આવે છે. આ અલ્ગોરિધમના પરિણામે, ભરણ (ઇનપુટ મેટ્રિક્સ માળખાનો ભાગ ન હોય તેવી કોલેસ્કી વિઘટનમાં બનાવવામાં આવેલી બિન-શૂન્ય મેટ્રિક્સ એન્ટ્રીઓનો સમૂહ) પુનરાવર્તિત પાર્ટીશનના દરેક સ્તર પર વિભાજક કદના મહત્તમ ચોરસ સુધી મર્યાદિત છે. ખાસ કરીને, સમતલીય આલેખ માટે (દ્વિ-પરિમાણીય મર્યાદિત તત્વ પદ્ધતિ મેશમાંથી મેળવેલ વિરલ રેખીય પ્રણાલીઓના ઉકેલમાં વારંવાર ઉદ્ભવતા) પરિણામી મેટ્રિક્સમાં ઓ (એન લોગ એન) નોનઝેરોસ હોય છે, જે સમતલીય વિભાજક પ્રમેયને કારણે ઓ () કદના વિભાજકોની બાંયધરી આપે છે. મનસ્વી આલેખ માટે એક નેસ્ટેડ વિચ્છેદન છે જે મહત્તમ પરિબળમાં ભરવાની બાંયધરી આપે છે, જ્યાં d એ મહત્તમ ડિગ્રી છે અને m એ બિન-શૂન્યની સંખ્યા છે. આલેખનો ચક્ર ક્રમ અથવા સપ્રમાણ બુલિયન મેટ્રિક્સ પણ જુઓ, જે કોલેસ્કી વિઘટન વર્ટેક્સ વિભાજક નોંધો સંદર્ભો કરવા માટે જરૂરી લઘુતમ સમાંતર સમયને માપે છે. . . . . વિરલ મેટ્રિસીસ આંકડાકીય રેખીય બીજગણિત