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.
|
9 nemnulla elemet tartalmaz a 35-ből, a maradék 26 elem értéke nulla. |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8a/Finite_element_sparse_matrix.png/640px-Finite_element_sparse_matrix.png)
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 ai,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 . 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 azA
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)
- az
(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 ai,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 ai,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):
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 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
Külső hivatkozások
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.