Algoritm för lägsta grad

I numerisk analys är minimigradsalgoritmen en algoritm som används för att permutera raderna och kolumnerna i en symmetrisk gles matris innan Cholesky-nedbrytningen tillämpas , för att minska antalet icke-nollor i Cholesky-faktorn. Detta resulterar i minskade lagringskrav och gör att Cholesky-faktorn kan tillämpas med färre aritmetiska operationer. (Ibland kan det också hänföra sig till en ofullständig Cholesky-faktor som används som förkonditionering – till exempel i den förkonditionerade konjugerade gradientalgoritmen.)

Minimigradsalgoritmer används ofta i finita elementmetoden där omordningen av noder kan utföras endast beroende på maskans topologi, snarare än på koefficienterna i den partiella differentialekvationen, vilket resulterar i effektivitetsbesparingar när samma nät används för en mängd olika koefficientvärden.

Givet ett linjärt system

$\mathbf {A} \mathbf {x} =\mathbf {b}$

där A är en $n\ gånger n$ reell symmetrisk gles kvadratisk matris. Cholesky-faktorn L kommer vanligtvis att lida av "fill in", det vill säga ha fler icke-nollor än den övre triangeln av A . Vi söker en permutationsmatris P , så att matrisen ${\displaystyle \mathbf {P} ^{T}\mathbf {A} \mathbf {P} } ,$ som också är symmetrisk, har minsta möjliga fyllning i dess Cholesky faktor. Vi löser det omordnade systemet

$\left(\mathbf {P} ^{T}\mathbf {A} \mathbf {P} \right)\left(\mathbf {P} ^{T}\mathbf {x} \right)=\ mathbf {P} ^{T}\mathbf {b} .$

Problemet med att hitta den bästa ordningen är ett NP-komplett problem och är därmed svårlöst, så heuristiska metoder används istället. Algoritmen för minimigraden är härledd från en metod som först föreslogs av Markowitz 1959 för icke-symmetriska linjära programmeringsproblem, som beskrivs löst enligt följande. Vid varje steg i Gauss eliminering utförs rad- och kolumnpermutationer för att minimera antalet off diagonala icke-nollor i pivotraden och kolumnen. En symmetrisk version av Markowitz-metoden beskrevs av Tinney och Walker 1967 och Rose härledde senare en grafteoretisk version av algoritmen där faktoriseringen bara simuleras, och denna fick namnet minimigradsalgoritmen. Grafen som refereras till är grafen med n hörn, med hörn i och j förbundna med en kant när $a_{ij}\neq 0$ , och graden är graden av hörnen. En avgörande aspekt av sådana algoritmer är en oavgjort strategi när det finns ett val av omnumrering som resulterar i samma grad.

En version av minimigradsalgoritmen implementerades i MATLAB -funktionen symmmd (där MMD står för multiple minimum degree), men har nu ersatts av en symmetrisk ungefärlig multipel minimigradsfunktion symamd , som är snabbare. Detta bekräftas av teoretisk analys, som visar att för grafer med n hörn och m kanter, har MMD en snäv övre gräns för $O(n^{2}m)$ på sin gångtid, medan för AMD gäller en snäv gräns för ${\displaystyle O(nm)} .$ Cummings, Fahrbach och Fatehpuria designade en exakt minimigradsalgoritm med $O(nm)$ körtid och visade att ingen sådan algoritm kan existera som löper i tiden ${ \displaystyle O(nm^{1-\varepsilon })}$ , för alla $\varepsilon >0$ , om man antar den starka exponentiella tidshypotesen .

•    Cummings, Robert; Fahrbach, Matthew; Fatehpuria, Animesh (2021). "En snabb minimigradsalgoritm och matchande nedre gräns". Proceedings of the 32th Annual ACM-SIAM Symposium on Discrete Algorithms : 724–734. doi : 10.1137/1.9781611976465.45 . ISBN 978-1-61197-646-5 . S2CID 198968052 .
•    George, Alan; Liu, Joseph (1989). "Utvecklingen av algoritmen för minsta gradbeställning". SIAM recension . 31 (1): 1–19. doi : 10.1137/1031001 . JSTOR 2030845 . OTI 5686483 .
• Heggernes, P. ; Eisenstat, SC; Kumfert, G.; Pothen, A. (2001), The Computational Complexity of the Minimum Degree Algorithm (PDF) (Teknisk rapport), Institutet för datortillämpningar inom naturvetenskap och teknik
•   Markowitz, HM (1957). "Elimineringsformen för inversen och dess tillämpning på linjär programmering" . Management Science . 3 (3): 255–269. doi : 10.1287/mnsc.3.3.255 . JSTOR 2627454 . Arkiverad från originalet den 24 september 2017.
•   Rose, DJ (1972). "En grafteoretisk studie av den numeriska lösningen av glesa positiva bestämda system av linjära ekvationer". Grafteori och beräkningar . Akademisk press. s. 183–217. ISBN 0-12-583850-6 .
• Tinney, WF; Walker, JW (1967). "Direktlösning av glesa nätverksekvationer genom optimalt ordnad triangulär faktorisering". Proc. IEEE . 55 (11): 1801–1809. doi : 10.1109/PROC.1967.6011 .