ALKALMAZOTT MATEMATIKAI LAPOK 10. KÖTET (A MTA Matematikai és Fizikai Tudományok Osztályának Közleményei, 1985)
1985 / 1-2. sz. - Arany Ilona: Nagyméretű, ritka, szimmetrikus mátrixok hatékony számítógépes kezelése
Alkalmazott Matematikai Lapok LT (1985) 1—90 NAGYMÉRETŰ, RITKA, SZIMMETIKUS MÁTRIXOK HATÉKONY SZÁMÍTÓGÉPES KEZELÉSE ARANY ILONA Budapest Jelen dolgozatban a sávszélesség/profil-redukció problémáját elemezzük. Alkalmas terminológia bevezetése után értékeljük a Gibbs—Poole—Stockmeyer-, illetve a George—Liu-eljárásokat. Részletesen foglalkozunk a sávszélesség/profit-redukció algoritmusában a szintstruktúra kialakítási és számozási fázisok problémáival. Ennek eredményeképpen 17 algoritmust fogalmazunk meg ritka, szimmetrikus mátrixok sávszélesség/profil-redukciójára. Ezek közül 6 eljárás nem csupán eredményében, hanem gépidő szükségletében is jónak minősül a fenti jól ismert algoritmusokkal való összehasonlításban. Bevezetés Számos alkalmazási területen, különösen a műszaki gyakorlatban felvetődő problémák (parciális differenciálegyenletek numerikus megoldása, statikai számítások, stb.) gyakran eredményeznek nagyméretű, ritka, szimmetrikus mátrixot. A számítógépes hatékonyság növelése érdekében ekkor speciális mátrix-kezelési technikák alkalmazása szükséges. Tekintsük például az (1) Axeb lineáris algebrai egyenletrendszert, ahol A nagyméretű, szimmetrikus, sok zérus-elemet tartalmazó pozitív definit mátrix. Ekkor (1) direkt módszerrel való számítógépes megoldásakor a faktorizáció során fellépő feltöltődés (fill-in) folytán a mátrix nem-zérus elemeinek száma erősen megnőhet, ezáltal megnő a tárigény és a végrehajtandó műveletek száma. Vagyis a megoldás gazdaságtalanná válik. A számítógépes hatékonyság növelése, illetve igen nagy (több 10 000-es) méret esetén a központi tárban való kezelhetőség érdekében célszerű volna olyan P° permutációs mátrixot meghatározni, hogy Ap° P°APor zérus/nem-zérus szerkezete a választott megoldási módszer szempontjából optimális, azaz ApD olyan szerkezetű, hogy az elimináció során fellépő feltöltődés minimális; vagy Ap° sáv-mátrix, minimális sávszélességgel. Mindkét esetben azonban P° meghatározása NP-teljes probléma (P. Z. CHINN és munkatársai [24]; M. R. GAREY és munkatársai [34]; CH. H. PAPADIMITRIU [73], [74]; J. A. GEORGE [50], [51]), ezért a gyakorlatban meg kell elégednünk P° valami- Alkalmazott Matematikai Lapok 11 (1985)