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ó össze­hasonlí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 tech­nikák alkalmazása szükséges. Tekintsük például az (1) Ax­e­b lineáris algebrai egyenletrendszert, ahol A nagyméretű, szimmetrikus, sok zérus-ele­met 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égrehaj­tandó 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° per­mutá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)

Next