Minimális fokozatú algoritmus - Minimum degree algorithm

A numerikus elemzés során a minimális fokozatú algoritmus egy olyan algoritmus, amelyet a szimmetrikus ritka mátrix sorainak és oszlopainak átjárására használnak, mielőtt alkalmaznák a Cholesky-bontást , és csökkentenék a nullák számát a Cholesky-faktorban. Ez csökkentett tárolási követelményeket eredményez, és azt jelenti, hogy a Cholesky-tényező kevesebb számtani művelettel alkalmazható. (Néha előfordulhat, hogy az előfeltételként használt hiányos Cholesky-faktor is előfordul, például az előfeltételezett konjugált gradiens algoritmusban.)

Minimális fokozatú algoritmusokat gyakran alkalmaznak a végeselemes módszerben, ahol a csomópontok átrendezése csak a háló topológiájától függően hajtható végre, a részleges differenciálegyenlet együtthatói helyett, ami hatékonyságmegtakarítást eredményez, ha ugyanazt a hálót használják az együtthatóértékek sokfélesége.

Adott egy lineáris rendszer

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

ahol A egy valós szimmetrikus ritka négyzetmátrix. A Cholesky tényező L jellemzően szenvedni „kitölt”, vagyis több nem nullák, mint a felső háromszög A . Keresünk egy P permutációs mátrixot , hogy a szintén szimmetrikus mátrix a lehető legkevesebb kitöltéssel töltse be Cholesky-tényezőjét. Megoldjuk az átrendezett rendszert ${\ displaystyle n \ alkalommal n}$ ${\ displaystyle \ mathbf {P} ^ {T} \ mathbf {A} \ mathbf {P}}$

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

A legjobb megrendelés megtalálásának problémája NP-teljes probléma, így megoldhatatlan, ezért heurisztikus módszereket alkalmaznak helyettük. A minimális fokozatú algoritmus egy olyan módszerből származik, amelyet Markowitz először 1959-ben javasolt nem szimmetrikus lineáris programozási problémákra, amelyet lazán az alábbiakban írunk le. A Gauss-eliminációs sorok és oszlopok permutációit minden lépésben végrehajtjuk, hogy minimalizáljuk az átlós nem nullák számát az elforduló sorban és oszlopban. A Markowitz módszer szimmetrikus változatát Tinney és Walker írta le 1967-ben, és Rose később levezette az algoritmus grafikonelméleti változatát, ahol a faktorizációt csak szimulálják, és ezt nevezték el a minimális fokozatú algoritmusnak. A hivatkozott gráf az a gráf, amelynek n csúcsa van, az i és j csúcsokkal egy él kapcsolódik, amikor , és a fok a csúcsok foka. Az ilyen algoritmusok kulcsfontosságú szempontja a döntetlen-megszakítási stratégia, ha van lehetőség az azonos számot eredményező újraszámozásra. ${\ displaystyle a_ {ij} \ neq 0}$

A minimum fokozatú algoritmus egy verziója a symmmd MATLAB függvényben valósult meg (ahol az MMD többszörös minimum fokozatot jelent), de most egy szimmetrikus, közelítő többszörös minimum fokozatú függvény szimamd váltotta fel , amely gyorsabb. Ezt megerősíti az elméleti elemzés, amely azt mutatja, hogy n csúcson és m szélen lévő grafikonok esetében az MMD futási idejének szűk felső határa van , míg az AMD esetében szoros tartási korlát . ${\ displaystyle O (n ^ {2} m)}$${\ displaystyle O (nm)}$

Hivatkozások

• Markowitz, HM (1957). Msgstr "Az inverz eliminációs formája és alkalmazása lineáris programozásra" . Vezetéstudomány . 3 (3): 255–269. doi : 10.1287 / mnsc.3.3.255 . JSTOR  2627454 .
• George, Alan; Liu, Joseph (1989). "A minimális fokozatrendelési algoritmus alakulása". SIAM Review . 31. (1): 1–19. doi : 10.1137 / 1031001 . JSTOR  2030845 .
• Tinney, WF; Walker, JW (1967). "Ritka hálózati egyenletek közvetlen megoldása optimálisan elrendezett háromszög faktorosítással". Proc. IEEE . 55 (11): 1801–1809. doi : 10.1109 / PROC.1967.6011 .
• Rose, DJ (1972). "Grafikonelméleti tanulmány a ritkán pozitív, meghatározott, lineáris egyenletrendszerek numerikus megoldásáról". In Read, RC (szerk.). Grafikonelmélet és számítástechnika . New York: Academic Press. 183–217. ISBN 0-12-583850-6.
• Heggernes, P .; Eisenstat, SC; Kumfert, G .; Pothen, A. (2001. december), A minimális fokozatú algoritmus számítási komplexitása (PDF) (Műszaki jelentés), Tudományos és Műszaki Számítógépes Alkalmazások Intézete