Harva matriisi

22 lokakuun, 2021
| Ei kommentteja

Matriisi tallennetaan yleensä kaksiulotteisena matriisina. Jokainen matriisin merkintä edustaa matriisin elementtiä ai,j, ja sitä käytetään kahdella indeksillä i ja j. Tavallisesti i on rivi-indeksi, joka numeroidaan ylhäältä alaspäin, ja j on sarakeindeksi, joka numeroidaan vasemmalta oikealle. Kun kyseessä on m × n-matriisi, matriisin tallentamiseen tässä muodossa tarvittavan muistin määrä on verrannollinen m × n:ään (ottamatta huomioon sitä, että myös matriisin dimensiot on tallennettava).

Harvan matriisin tapauksessa muistin tarvetta voidaan vähentää huomattavasti tallentamalla vain nollasta poikkeavat merkinnät. Nollasta riippumattomien merkintöjen määrästä ja jakautumisesta riippuen voidaan käyttää erilaisia tietorakenteita, jotka tuottavat valtavia muistisäästöjä peruslähestymistapaan verrattuna. Kompromissina on se, että yksittäisten elementtien käyttäminen muuttuu monimutkaisemmaksi ja tarvitaan lisärakenteita, jotta alkuperäinen matriisi voidaan palauttaa yksiselitteisesti.

Formaatit voidaan jakaa kahteen ryhmään:

  • Tehokasta muokkausta tukevat formaatit, kuten DOK (avainten sanakirja), LIL (listojen luettelo) tai COO (koordinaattilista). Näitä käytetään tyypillisesti matriisien rakentamiseen.
  • Ne, jotka tukevat tehokasta käyttöä ja matriisioperaatioita, kuten CSR (Compressed Sparse Row) tai CSC (Compressed Sparse Column).

Avainten sanakirja (DOK)Muokkaa

DOK koostuu sanakirjasta, joka mapittaa (rivi, sarake)-parit elementtien arvoihin. Sanakirjasta puuttuvat elementit otetaan nollaksi. Muoto on hyvä harvan matriisin inkrementaaliseen rakentamiseen satunnaisessa järjestyksessä, mutta huono ei-nolla-arvojen iterointiin leksikografisessa järjestyksessä. Tyypillisesti rakennetaan matriisi tässä muodossa ja muunnetaan sitten toiseen tehokkaampaan muotoon käsittelyä varten.

List of lists (LIL)Muokkaa

LIL tallentaa yhden listan per rivi, jossa jokainen merkintä sisältää sarakeindeksin ja arvon. Tyypillisesti nämä merkinnät säilytetään sarakeindeksin mukaan lajiteltuina hakujen nopeuttamiseksi. Tämä on toinen formaatti, joka sopii hyvin inkrementaaliseen matriisien rakentamiseen.

Koordinaattilista (COO)Muokkaa

COO tallentaa listan (rivi, sarake, arvo) tupleista. Ihannetapauksessa merkinnät lajitellaan ensin rivi-indeksin ja sitten sarakeindeksin mukaan satunnaisten hakuaikojen parantamiseksi. Tämä on toinen formaatti, joka on hyvä inkrementaaliseen matriisien rakentamiseen.

Puristettu harva rivi (CSR, CRS tai Yale-muoto)Edit

Puristettu harva rivi (CSR, compressed sparse row) tai puristettu rivitallennus (CRS, compressed row storage) tai Yale-muoto edustaa matriisia M kolmella (yksiulotteisella) ruudulla, jotka sisältävät vastaavasti nollasta poikkeavat arvot, rivien ekstensiot ja sarakkeiden indeksit. Se on samanlainen kuin COO, mutta se pakkaa riviindeksit, mistä nimi johtuu. Tämä muoto mahdollistaa nopean rivien käytön ja matriisi-vektorikertoimet (Mx). CSR-formaatti on ollut käytössä ainakin 1960-luvun puolivälistä lähtien, ja ensimmäinen täydellinen kuvaus ilmestyi vuonna 1967.

CSR-formaatti tallentaa harvan m × n-matriisin M rivimuodossa käyttäen kolmea (yksiulotteista) matriisia (V, COL_INDEX, ROW_INDEX). Olkoon NNZ nollasta poikkeavien merkintöjen lukumäärä M:ssä. (Huomaa, että tässä käytetään nollaan perustuvia indeksejä.)

  • Matriisit V ja COL_INDEX ovat pituudeltaan NNZ, ja ne sisältävät nollasta poikkeavat arvot ja vastaavasti näiden arvojen sarakeindeksit.
  • Matriisi ROW_INDEX on pituudeltaan m + 1, ja se koodaa indeksin V:ssä ja COL_INDEX:ssä, josta kyseinen rivi alkaa. Viimeinen elementti on NNZ , ts, kuvitteellinen indeksi V:ssä heti viimeisen kelvollisen indeksin NNZ – 1 jälkeen.

Esimerkiksi matriisi

( 5 0 0 0 0 0 8 0 0 0 0 3 0 0 0 6 0 0 ) {\displaystyle {\begin{pmatrix}5&0&0&0&0&0&0&0&8&0&0&0&0&0&0 &0&3&0ὠ0Ǽ

{\displaystyle {\begin{pmatrix}5000\\\0800\\\0030\\\0600\\\\\\end{pmatrix}}}

on 4 × 4 matriisi, jossa on 4 nollasta poikkeavaa elementtiä, joten

 V = COL_INDEX = ROW_INDEX =

oletetaan nollaindeksoitua kieltä.

Rivin poimimiseksi määrittelemme ensin:

 row_start = ROW_INDEX row_end = ROW_INDEX

Sitten otamme viipaleita V:stä ja COL_INDEX:stä alkaen rivin_alkupäästä ja päättyen rivin_loppupäähän.

Tämän matriisin rivin 1 (toisen rivin) poimimiseksi asetamme row_start=1 ja row_end=2. Sitten teemme viipaleet V = ja COL_INDEX = . Tiedämme nyt, että rivillä 1 on yksi elementti sarakkeessa 1, jonka arvo on 8.

Tässä tapauksessa CSR-edustus sisältää 13 merkintää, kun alkuperäisessä matriisissa on 16 merkintää. CSR-muoto säästää muistia vain silloin, kun NNZ < (m (n – 1) – 1) / 2.Toinen esimerkki, matriisi

( 10 20 0 0 0 0 0 0 30 0 40 0 0 0 0 50 60 70 0 0 0 0 0 0 0 0 0 80 ) {\displaystyle {\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}}

{\begin{pmatrix}10200000\\\03004000\\\005060700\\\0000080\\\\\\end{pmatrix}}

on 4 × 6 -matriisi (24 merkintää), jossa on 8 nollasta poikkeavaa elementtiä, joten

 V = COL_INDEX = ROW_INDEX =

Kokonaisuus tallennetaan 21 merkintänä.

  • ROW_INDEX jakaa matriisin V riveihin: (10, 20) (30, 40) (50, 60, 70) (80);
  • COL_INDEX kohdistaa arvot sarakkeisiin: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Huomaa, että tässä muodossa ROW_INDEX:n ensimmäinen arvo on aina nolla ja viimeinen arvo on aina NNZ, joten ne ovat tavallaan tarpeettomia (vaikka ohjelmointikielissä, joissa matriisin pituus on tallennettava eksplisiittisesti, NNZ ei olisi tarpeeton). Näin vältetään kuitenkin tarve käsitellä poikkeustapausta kunkin rivin pituutta laskettaessa, koska se takaa, että kaava ROW_INDEX – ROW_INDEX toimii mille tahansa riville i. Lisäksi tämän redundantin tallennuksen aiheuttamat muistikustannukset ovat todennäköisesti merkityksettömiä riittävän suurelle matriisille.

Yalen (vanha ja uusi) harvan matriisin formaatit ovat CSR-järjestelmän esimerkkejä. Vanha Yale-formaatti toimii täsmälleen edellä kuvatulla tavalla kolmella matriisilla; uusi formaatti yhdistää ROW_INDEX- ja COL_INDEX-matriisit yhdeksi matriisiksi ja käsittelee matriisin diagonaalin erikseen.

Loogisten vierekkäisyysmatriisien kohdalla tietomatriisi voidaan jättää pois, sillä merkinnän olemassaolo rivimatriisissa riittää mallintamaan binäärisen vierekkäisyyssuhteen.

Se tunnetaan todennäköisesti Yale-formaattina, koska sitä ehdotettiin Yalen yliopiston tietojenkäsittelytieteen laitoksen Yale Sparse Matrix Package -raportissa vuonna 1977.

Compressed sparse column (CSC tai CCS)Edit

CSC on samankaltainen kuin CSR sillä erotuksella, että arvot luetaan ensin sarakkeittain, jokaiselle arvolle tallennetaan riviosoitin ja sarakkeisiin tallennetaan sarakkeenosoittimet. Esimerkiksi CSC on (val, row_ind, col_ptr), jossa val on matriisin nollasta poikkeavien arvojen joukko (ylhäältä alas, sitten vasemmalta oikealle), row_ind on arvoja vastaavat rivi-indeksit ja col_ptr on lista val-indekseistä, joista kukin sarake alkaa. Nimi perustuu siihen, että sarakeindeksitiedot on pakattu COO-formaattiin verrattuna. Rakentamiseen käytetään yleensä jotain muuta muotoa (LIL, DOK, COO). Tämä formaatti on tehokas aritmeettisille operaatioille, sarakkeiden pilkkomiselle ja matriisi-vektorituotteille. Katso scipy.sparse.csc_matrix.Tämä on perinteinen formaatti harvan matriisin määrittämiseen MATLABissa (sparse-funktion kautta).

Articles