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
4 ARANY I lyen fajta közelítésével, mely csupán a feltöltődés, illetve sávszélesség redukcióját eredményezi. E közelítéseket különböző heurisztikus algoritmusokkal állítják elő a gyakorlatban. A dolgozatban ritka, szimmetrikus mátrixok sávszélesség/profil redukciójával foglalkozunk és 17 algoritmust közlünk. Ezekből 6 eljárás nem csupán eredményében, hanem gépidő-szükségletében is kedvező képet mutat a J. A. GEORGE és J. W H.Liu [53], valamint N. E. GIBBS, W. G. POOLE és P. K. STOCKMEYER [55] ismert algoritmusaival való összehasonlításban. A ritka mátrixok szerkezeti sajátságainak felhasználása iránti igény elsőként a nagyméretű lineáris programozási feladatok kapcsán fogalmazódott meg (G. B. DANTZIG, 1952, [29]). A műszaki alkalmazások, különösen a véges elemek módszerének gyors elterjedése sürgető kényszerként hatott a számítógépes megoldás hatékonyságát növelő eljárások kidolgozására. Számos munka jelent meg az elimináció során fellépő feltöltődés, az elimináció gráfelméleti szimulációja problémakörében. (H. M. MARKOWITZ [68], D. J. ROSE [76], J. R. BUNCH [20], [21]; J. A. GEORGE [39], [47], [53]; R. P. TEWARSON [83]; S. C. EISENSTAT [31].) Egyrészt adott feladat-típus jellegzetességein alapuló eljárásokat hoztak létre (B. M. IRONS [57] ; J. A. FELIPPA [32]). Másrészt feladat-típustól független eljárások jelentek meg, melyekkel a feltöltődés jelentősen csökkenthető a mátrix elemeinek szintjén (H. M. MARKOWITZ [68], D. J. ROSE [76]), illetve teljesen megszüntethető a mátrix bizonyos blokkjaiban (J. A. GEORGE és J. W H. Liu [36], [37], [38], [40], [43], [44], [45], [46], [52], [53]). Megindult a megfelelő software kidolgozása. Új programnyelvek születtek (GRAAL [75], LASCALA [84]) s program-rendszerek készültek ritka mátrixú rendszerek kezelésére (Yale Sparse Matrix Package (Yale University), ill. SIRSM [85]). 1978-ra befejeződött az első, univerzálisnak nevezhető programrendszer, a SPARSPAR [53] kidolgozása (J. A. GEORGE és J. W H. Liu, University of Waterloo), így lehetővé vált a szimmetrikus vagy csupán zérus/nem-zérus szerkezetében szimmetrikus, ritka mátrixú lineáris egyenletrendszerek hatékony direkt megoldásainak alkalmazása. Az ESZR-ben 1975-ben elkészült a ritka, szimmetrikus mátrixok sávszélességredukcióját végző MÁTRIXOK programrendszer [6]. A sávszélesség-redukció problémájára elsőként 1965-ben G. G. ALWAY és D. W. MARTIN [3], majd 1968-ban R. ROSEN [77] fogalmazták meg eljárásaikat, melyek azonban nagy munkaigényük miatt a gyakorlatban nem nyertek alkalmazást. Rövid időn belül számos új eljárás fogalmazódott meg [4], [7], [23], [27], [53], [55], [59], [81], [82], melyek közül [27], [53], [55] a gyakorlatban is hatékonynak bizonyultak. Az alábbiakban az első, gyakorlatban is alkalmazható eljárás megszületésétől napjainkig közölt főbb eredményeket összegezzük. 1969-ben E. H. CUTHILL és J. MCKEE [27] fogalmazták meg az első, ma már klasszikusnak nevezhető eljárásukat. A szerzők irányítatlan gráf kifeszítő fájának alkalmas számozásával érték el a redukált sávszélességet. 1972-ben W. F. SMYTH ILO (International Labour Office) szakértővel és Szóda Lajos kollegámmal közösen új sávszélesség-redukciós eljárást közöltünk [4]. Bevezettük a gráfon értelmezett szintstruktúra fogalmát, s algoritmusunkat szintstruktúra kialakítása és szintstruktúra számozási fázisok együtteseként fogalmaztuk Alkalmazott, Matematikai Lapok 11 (1915)