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 35-ből, a maradék 26 elem értéke nulla.

A ritka mátrix a numerikus analízis alterületén olyan mátrix, melyben az elemek túlnyomó része 0 (nulla).^[1] 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 leggyakrabban parciális differenciálegyenletek megoldásai eredményeznek. 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.

Ritka mátrixok esetében 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

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.

Feltöltődés

A ritka mátrixok Gauss-eliminációja során fellépő jelenséget, hogy olyan helyeken keletkezik nemzérus elem, ahol eredetileg nulla állt, feltöltődésnek nevezik. Mivel a ritka mátrixokban a nulla elemeket általában helytakarékosan tárolják, ezért a feltöltődésre ügyelni kell: helyet kell szerezni az újonnan keletkezett elemeknek. Ha külön nem foglalkoznak vele, a feltöltődés nagymértékű is lehet; egy eliminációs lépés alatt akár az egész mátrix feltöltődhet.^[2]

A minimális feltöltődés (minimum fill-in) elérése kívánatos cél, a szükséges számítási bonyolultságról még kevés tanulmány született;^[3] általában segíthet, ha a problémát okozó sorokat, oszlopokat a Gauss-elimináció végén kezeljük, amit a minimális fokszám algoritmus (az elimináció k-adik lépésében azt a főátlóbeli elemet választjuk főelemnek, amelynek az i index fokszáma minimális) valósít meg.

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. [2014. december 21-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. február 8.)
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.

Jegyzetek

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. [2008. június 6-i dátummal az eredetiből archiválva]. DOI:10.1137/0613024. (Hozzáférés: 2014. február 8.)
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.

[1] (Stoer & Bulirsch 2002, p. 619)

[2] Stoyan Gisbert-Takó Galina: Numerikus módszerek I.

[3] Yixin Cao, R. B. Sandeep: Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

[1]

[2]

[3]