Szerkesztő:Vigyori93/próbalap

Ritka mátrix Ritka mátrix a numerikus analízis alterületében olyan mátrix, melyben elemek túlnyomó része 0 (nulla) (Stoer & Bulirsch 2002, 619. old.). 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ó össze kötve lenne egy rugón keresztül 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ásai területein használják, mint például a hálózatkutatásban, 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 aij 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. 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. Yale-formátum A Yale ritkamátrix-formátum sorként tárolja az eredetileg m x n 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. 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. 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 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 aij = 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 aij = 0 bármely i < j-p esetén. 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): (mátrix) 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ó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 x 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-féle 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ódszeréhez vagy az általánosított minimális reziduális módszerhez hasonló iteratív módszerek az Axi 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.