Ritka mátrix

Példa ritka mátrixra   [ 11 22  0  0  0  0  0 ]   [  0 33 44  0  0  0  0 ]   [  0  0 55 66 77  0  0 ]   [  0  0  0  0  0 88  0 ]   [  0  0  0  0  0  0 99 ]

A fenti ritka mátrix csupán 9 nemnulla elemet tartalmaz a 35ből,  a maradék 26 elem értéke nulla.

Kétdimenziós végeselemes feladat megoldásaként kapott ritka mátrix. A nemnulla elemeket fekete pontok jelölik.

Ritka mátrix a numerikus analízis alterületében olyan mátrix (matematika), melyben elemek túlnyomó része 0 (nulla) (Stoer & Bulirsch 2002, p. 619). Ezzel ellentétben a túlnyomórészt nemnulla elemet tartalmazó mátrixokat sűrű mátrixnak nevezzük. A nulla- (vagy éppen nemnulla) elemek aránya a mátrix méretéhez képest, annak ritkaságát (sűrűségét) adja.

A ritka mátrixok gyakorlatilag lazán csatolt rendszereknek felelnek meg. Tekintsünk egy rugókkal összekapcsolt golyókból álló láncot; ez egy ritka rendszer. Azonban ha az összes golyó egy rugón keresztül össze lenne kötve az összes többivel, a rendszert egy sűrű mátrix jellemezné. A ritkaság fogalmát főleg a kombinatorikában és annak alkalmazási területein használják, mint például a hálózatelméletben, ahol kicsi a jelentős adatok vagy összeköttetések sűrűsége.

Nagyméretű ritka mátrixokat eredményeznek a parciális differenciálegyenletek megoldásai különböző tudományos vagy műszaki területeken.

Ritka mátrixok számítógépes kezelése vagy tárolása esetén sokszor előnyös, néhol egyenesen szükséges, olyan algoritmusok és adatszerkezetek alkalmazása, melyeket kihasználják a mátrixok ritka szerkezetét, vagyis kifejezetten ilyen esetekre vannak kidolgozva. A hagyományos mátrixokkal dolgozó műveletek használata ez esetben lassú és fölöslegesen nagy memóriaigényű. Az adatok ritkaságukból adódóan könnyen tömöríthetőek s ezáltal lényegesen kisebb a memóriaigényük. Valóban, nagyon nagy ritka mátrixok hagyományos módszerek, algoritmusok által való kezelése megvalósíthatatlan.

Ritka mátrixok tárolása

Mátrixok tárolására alapvetően kétdimenziós tömbök használatosak, melyekben a tömb minden egyes t[i][j] eleme a mátrix egy-egy a_i,j elemének felel meg. Egyezményesen i a sort jelöli fentről lefele haladva, míg j az oszlopot balról jobbra haladva. Egy m x n méretű mátrix tárolása így m•n darab bejegyzésnek megfelelő memóriát igényel.

Jelentős mennyiségű memória spórolható meg, ha csak a nemnulla elemeket tároljuk. Ezek száma és eloszlása függvényében többféle adatszerkezet is rendelkezésünkre áll, melyek nagymértékű memória-megtakarítást szolgáltatnak a hagyományos módszerekkel szemben.

Formátum szempontjából két fő csoportról beszélhetünk:

• melyek hatékonyan módosíthatók
• melyek hatékonyan vethetők alá különböző, mátrixokkal végzett műveleteknek

Előbbibe tartozik például a DOK (Dictionary of keys - kulcsszótár), a LIL (List of lists - listák listája), a COO (Coordinate list – koordináták listája), ezeket általában a mátrix felépítésére használják. Ha a mátrix már fel van építve, átalakításra kerül a CSR (Compressed Sparse Row – sortömörítés) vagy a CSC (Compressed Sparse Column – oszloptömörítés) formátumok valamelyikébe, melyek optimálisabbak mátrixműveletek elvégzésekor.

Kulcsszótár (DOK – dictionary of keys)

A DOK egyfajta szótárként tárolja a nemnulla elemeket (pl. hash tábla vagy bináris fa formájában), minden (sor, oszlop) számpárnak megfeleltetve egy értéket. Ez az alak előnyös a mátrix fokozatos felépítésekor, azonban gyenge abban az esetben, ha a nemnulla elemek valamilyen sorrend szerint akarjuk iterálni. Az általános eljárás az, hogy a DOK alapján felépítik a mátrixot, majd egy könnyebben kezelhető formátumba konvertálják.

Listák listája (LIL – List of lists)

A LIL listánként egy sort tartalmaz s minden bejegyzés tartalmazza az oszlopindexet és az értéket. A gyors keresés érdekében az oszlopindexek szerint rendezve tárolják. Ez ugyancsak előnyös formátum a mátrix fokozatos felépítésére. Lásd scipy.sparse.lil_matrix.

Koordináták listája (COO – Coordinate list)

A COO egy lista, mely (sor, oszlop, érték) számhármasokat tároló rendezett n-esekből áll. Kedvező esetben a bejegyzések sorok, ezeken belül oszlop szerint rendezettek a hozzáférhetőség megkönnyítése céljából. Jelen tárolási módszer ugyancsak előnyös a mátrixok fokozatos felépítésekor. Lásd scipy.sparse.coo_matrix.

Yale-formátum

A Yale ritkamátrix-formátum sorként tárolja az eredetileg mxn méretű M mátrixot, három egydimenziós tömböt használva. Legyen NN a nemnulla elemek száma M-ben. Legyen az A tömb NN hosszúságú s tárolja M összes nemnulla elemét balról jobbra és fentről lefele haladva a mátrixban. A második tömb legyen IA, melynek hossza m+1 s melynek i. eleme tartalmazza az M mátrix i. sorából az első nemnulla elem A tömbbeli indexét. A mátrix i. sora A[IA[i]]-tól A[IA[i+1]-1]-ig tart, azaz az adott sor első nemnulla elemétől a következő sort kezdő elemet megelőző nemnulla elemig. A harmadik tömb, a JA, az A elemeinek M mátrixbeli oszlopindexét tárolja, így hossza ugyancsak NN. Például a

[ 1 2 0 0 ]

[ 0 3 9 0 ]

[ 0 1 4 0 ]

3 x 4-es mátrixnak 6 nemnulla eleme van, így az őt jellemző tömbök:

A = [ 1 2 3 9 1 4 ]   (a nemnulla elemeket tartalmazó tömb)

IA = [ 0 2 4 6 ]   (az i. sor első nemnulla elemének indexét tároló tömb)

JA = [ 0 1 1 2 1 2 ]   (az A elemeinek oszlopindexei)

Azaz a JA tömbnek megfelelően az A tömb ’1’-es elemének oszlopindexe 0, a ’2’ és ’3’ oszlopindexe 1, a ’9’ oszlopindexe 2, a második ’1’-es oszlopindexe 1, a ’4’-es oszlopindexe pedig 2. A matematikában az oszlopok számozása 1-től 4-ig terjed, a számítástechnikában azonban 0-tól 3-ig.

Feltűnik, hogy a Yale felírási módszer során 16 bejegyzést tárolunk az eredeti mátrix 12 bejegyzéséhez képest, ugyanis a Yale-formátum használata csak akkor előnyös, ha $NN<(m(n-1)-1)/2$. Egy újabb példában az M mátrix

        [ 10 20  0  0  0  0 ]
        [  0 30  0 40  0  0 ]
        [  0  0 50 60 70  0 ]
        [  0  0  0  0  0 80 ]

4 x 6-os, azaz 24 bejegyzést tartalmaz, ebből 8 nemnulla elem, így

        A  = [ 10 20 30 40 50 60 70 80 ]
        IA = [ 0  2  4  7 8 ]
        JA = [  0  1  1  3  2  3  4  5 ]

Ez esetben már csak 21 bejegyzés volt szükséges.

• az IA sorokra bontja az A tömböt: (10, 20) (30, 40) (50, 60, 70) (80)
• a JA oszlopokba rendezi az értékeket: (10, 20, …) (0, 30, 0, 40, …) (0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80)

(Megjegyzés: Ebben a formátumban IA első eleme mindig 0, utolsó eleme mindig NN, így ez a két bejegyzés fölösleges lehet.)

Sortömörítés (CSR – Compressed Sparse Row)

A CSR hatékonyságában a Yale-formátummal megegyező, azzal a különbséggel, hogy az oszlopindexeket tartalmazó tömb általában a sorindexeket tartalmazó előtt kerül tárolásra. Alakja (érték, oszlop_index, sor_pointer), ahol az érték a nemnulla elemek tömbje (balról jobbra és fentről lefele járva be a mátrixot), az oszlop_index az értékeknek megfelelő oszlopindexek tömbje, míg a sor_pointer a sorokat kezdő nemnulla elemek indexeinek listája. Elnevezését arról kapta, hogy a COO formátumhoz képest a sorindexek tárolása tömörített. Előnyös aritmetikai műveletek elvégzésekor, mátrix-vektor szorzat kiszámításakor, sorszeleteléskor, azonban a mátrix felépítésére nem szokás használni. Lásd scipy.sparse.csr_matrix.

Oszloptömörítés (CSC – Compressed Sparse Column)

A CSC a CSR-hez hasonló módszer, a különbség abban rejlik, hogy az elemek oszloponként vannak beolvasva, minden elemnek a sorindexe van tárolva s az oszlopokat tároljuk pointerekben. Alakja (érték, sor_index, oszlop_pointer), ahol az érték a nemnulla elemek tömbje (balról jobbra és fentről lefele járva be a mátrixot), a sor_index az értékeknek megfelelő sorindexek tömbje, míg az oszlop_pointer az oszlopokat kezdő nemnulla elemek indexeinek listája. Elnevezését arról kapta, hogy a COO formátumhoz képest az oszlopindexek tárolása tömörített. Előnyös aritmetikai műveletek elvégzésekor, mátrix-vektor szorzat kiszámításakor, oszlopszeleteléskor, azonban a mátrix felépítésére nem szokás használni. Lásd scipy.sparse.csc_matrix. Hagyományosan ezt a formátumot használja a MATLAB egy ritka mátrix jellemzésére a sparse függvény által.

Különleges szerkezetű ritka mátrixok

Sávmátrix

A sávmátrix a ritka mátrixok egy különleges típusa, melyben az alsó- és felsősáv szélesség viszonylag kis érték. Ezek meghatározása a következő: Az A mátrix alsósáv szélessége az a legkisebb p szám, melyre az a_i,j = 0 bármely i > j+p esetén. Hasonlóképpen az A mátrix felsősáv szélessége az a legkisebb p szám, melyre az a_i,j = 0 bármely i < j-p esetén (Golub & Van Loan 1996, §1.2.1). Például egy tridiagonális mátrix alsó- és felsősáv szélessége is 1. A következő példában azonban mindkettő értéke 3 (az X-ek a nemnulla elemek, a pontok a nullaelemek):

$\left({\begin{smallmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end{smallmatrix}}\right)$

Különleges szerkezetükből adódóan a kezelésükre kidolgozott algoritmusok jóval egyszerűbbek az általános ritka mátrixokkal dolgozó algoritmusoknál, de néha sűrű mátrixok algoritmusai is alkalmazhatók, amikor is a hatékonyságot a feldolgozandó indexek kis száma biztosítja.

Egy A mátrix sorainak és oszlopainak átrendezésével lehetséges egy olyan A’ mátrix, mely rendelkezik alsósáv szélességgel. Számos algoritmus létezik a sávszélességek minimalizálására.

Átlós mátrix

A sávmátrix sajátos típusa az átlós mátrix, ennek legoptimálisabb tárolási módja egy egydimenziós tömb, melybe a főátló elemeit visszük be, így az n•n számú bejegyzés n-re csökken.

Szimmetrikus mátrix

A szimmetrikus ritka mátrixok irányítatlan gráfok szomszédsági mátrixaiból erednek, hatékony tárolási módjuk a szomszédsági lista.

Helyettesítések csökkentése

Helyettesítésnek nevezzük azt a folyamatot, mely során egy eredetileg nulla értékű elem nemnulla elemmé válik, például egy algoritmus futtatása alatt. Az egy algoritmus futtatása során elvégzendő műveletek memóriaigényének csökkentésére hasznos a helyettesítések számának minimalizálása a mátrix sorainak és oszlopainak átrendezésével. A szimbolikus Cholesky-felbontás felhasználható a lehető legrosszabb helyettesítés kiszámolására még mielőtt alkalmaznánk a tényleges Cholesky-felbontást.

Természetesen nem csak Cholesky módszere létezik, népszerűek az ortogonalizációs módszerek (pl. QR felbontás) is a legkisebb négyzetek módszerét használó feladatok esetén. Bár elméletileg a helyettesítés változatlan, a gyakorlatban a „hamis nemnullák” változhatnak módszerenként. Továbbá ezen algoritmusok szimbolikus változatai ugyanúgy használhatók a legrosszabb helyettesítés felmérésére, akárcsak a szimbolikus Cholesky-féle felbontás.

Ritka mátrixok egyenleteinek megoldása

Ritka mátrixok egyenleteinek megoldására iteratív és direkt módszereket is dolgoztak ki.

A konjugált gradiens módszerhez vagy az általánosított minimális reziduális módszerhez hasonló iteratív módszerek az $Ax_{i}$ mátrix-vektor szorzat gyors kiszámítását használják fel, ahol A egy ritka mátrix. Az előtesztelők használata jelentősen felgyorsítja az efféle iteratív módszerek konvergenciáját.

Irodalom

• Matrix Computations, 3rd, Johns Hopkins (1996). ISBN 978-0-8018-5414-9 
• Introduction to Numerical Analysis, 3rd, Berlin, New York: Springer-Verlag (2002). ISBN 978-0-387-95452-3 
• Tewarson, Reginald P.. Sparse Matrices (Part of the Mathematics in Science & Engineering series). Academic Press Inc. (1973. május 1.)  (This book, by a professor at the State University of New York at Stony Book, was the first book exclusively dedicated to Sparse Matrices. Graduate courses using this as a textbook were offered at that University in the early 1980s).
• Sparse Matrix Multiplication Package
• Pissanetzky, Sergio. Sparse Matrix Technology. Academic Press (1984) 
• (1976) „Reducing the profile of sparse symmetric matrices”. Bulletin Géodésique 50 (4), 341. o. DOI:10.1007/BF02521587.   Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

További információk

• (1976) „A comparison of several bandwidth and profile reduction algorithms”. ACM Transactions on Mathematical Software 2 (4), 322–330. o. DOI:10.1145/355705.355707.  
• (1992) „Sparse matrices in MATLAB: Design and Implementation”. SIAM Journal on Matrix Analysis and Applications 13 (1), 333–356. o. DOI:10.1137/0613024.  
• Sparse Matrix Algorithms Research at the University of Florida, containing the UF sparse matrix collection.
• SMALL project A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.

Külső hivatkozások

• Equations Solver Online
• Oral history interview with Harry M. Markowitz, Charles Babbage Institute, University of Minnesota. Markowitz discusses his development of portfolio theory (for which he received a Nobel Prize in Economics), sparse matrix methods, and his work at the RAND Corporation and elsewhere on simulation software development (including computer language SIMSCRIPT), modeling, and operations research.