Proređena matrica

Gornja proređena matrica sadrži samo 9 nenultih elemenata, sa 26 nultih elemenata. Njena proređenost je 74%, a gustina 26%

Primer proređene matrice

Proređena matrica dobijena rešavanjem problema konačnih elemenata u dve dimenzije. Ne-nulti elementi su prikazani crnom bojom.

U numeričkoj analizi i naučnom računanju, proređena matrica ili retki niz je matrica u kojoj je većina elemenata nula. Ne postoji stroga definicija koliko mora biti nultih elemenata da bi se matrica smatrala retkom, ali najčešći kriterijum je da je broj nultih elemenata otprilike broj redova ili kolona. Suprotno tome, ako većina elemenata nije nula, matrica se smatra gustom. Broj elemenata sa nultom vrednošću podeljen sa ukupnim brojem elemenata (npr. m × n za m × n matricu) ponekad se naziva proređenošću matrice.

Konceptualno, proređenost odgovara sistemima sa nekoliko uparenih interakcija. Na primer, zamislite liniju kuglica povezanih oprugama od jedne do druge: ovo je proređen sistem jer se spajaju samo susedne lopte. Suprotno tome, ako bi ista linija kuglica imala opruge koje povezuju svaku kuglicu sa svim ostalim kuglicama, sistem bi odgovarao gustoj matrici. Koncept proređenosti je koristan u kombinatorici i područjima primene kao što su teorija mreža i numerička analiza, koje obično imaju malu gustinu značajnih podataka ili veza. Velike proređene matrice često se pojavljuju u naučnim ili inženjerskim primenama pri rešavanju parcijalnih diferencijalnih jednačina.

Prilikom skladištenja i manipulisanja retkim matricama na kompjuteru, korisno je i često je potrebno koristiti specijalizovane algoritme i strukture podataka koji koriste prednost proređene strukture matrice. Za proređene matrice su napravljeni specijalizovani računari, jer su one uobičajene u polju mašinskog učenja. Operacije uz pomoć standardnih struktura i algoritama guste matrice su spore i neefikasne kada se primene na matrice velikih gustina, jer se procesiranje i memorija troše na nule. Raspršeni podaci se po prirodi lakše kompresuju i zbog toga zahtevaju znatno manje skladišta. Nekim vrlo velikim retkim matricama je nemoguće manipulisati uz pomoć standardnih algoritama guste matrice.

Skladištenje proređene matrice

Matrica se obično čuva kao dvodimenzionalni niz. Svaki unos u niz predstavlja element ai,j matrice i njemu se pristupa putem dva indeksa i i j. Uobičajeno, i je indeks reda, numerisan od vrha do dna, a j indeks kolone, numerisan sleva udesno. Za m × n matricu, količina memorije potrebna za čuvanje matrice u ovom formatu srazmerna je m × n (ne uzimajući u obzir činjenicu da dimenzije matrice takođe treba da budu sačuvane).

U slučaju proređene matrice, zahtev za značajnim smanjenjem memorije može se ostvariti skladištenjem samo ne-nultih unosa. U zavisnosti od broja i distribucije ne-nultih unosa, mogu se koristiti različite strukture podataka i ostvariti ogromne uštede u memoriji u poređenju sa osnovnim pristupom. Kompromis je u tome što pristup pojedinačnim elementima postaje složeniji i potrebne su dodatne strukture da bi se jednoznačno mogla povratiti originalna matrica.

Formati se mogu podeliti u dve grupe:

• Oni koji podržavaju efikasne modifikacije, kao što su DOK (Dictionary of keys), LIL (List of lists) ili COO (Coordinate list). Oni se obično koriste za konstrukciju matrica.
• Oni koji podržavaju efikasne operacije pristupa i matrice, kao što su CSR (Compressed Sparse Row) ili CSC (Compressed Sparse Column).

Rečnik ključeva (Dictionary of keys - DOK)

DOK se sastoji od rečnika koji mapira (red, kolona)-parove sa vrednošću elementa. Elementi koji nedostaju u rečniku uzimaju se kao nula. Format je dobar za postepeno konstruiranje proređene matrice slučajnim redosledom, ali loš za iteraciju preko ne-nultih vrednosti u neleksikografskom redosledu. Matrica se obično konstruiše u ovom formatu, a zatim se konvertuje u drugi efikasniji format za obradu.

Spisak listi (List of lists - LIL)

LIL čuva jednu listu po redu, pri čemu svaki unos sadrži indeks kolone i vrednost. Ti unosi se obično sortiraju prema indeksu kolone radi bržeg pretraživanja. Ovo je još jedan format koji je dobar za izgradnju inkrementalne matrice.

Lista koordinata (Coordinate list - COO)

COO čuva listu torki (red, kolona, vrednost). Idealno je da se unosi sortiraju prvo prema indeksu redova, a zatim prema indeksu kolona, kako bi se poboljšala vremena nasumičnog pristupa. Ovo je još jedan format koji je dobar za izgradnju inkrementalne matrice.

Kompresovani proređeni red (Compressed sparse row - CSR, CRS ili Yale format)

Compressed sparse row (CSR) ili compressed row storage (CRS) ili Yale format predstavljaju matricu M puta tri (jednodimenzionalna) niza, koji sadrže ne-nulte vrednosti, obim redova i indekse kolona. Slično je COO-u, ali su indeksi redova kompresovani, pa otuda i naziv. Ovaj format omogućava brz pristup redovima i umnožavanje vektora i matrice (Mx). CSR format se koristi najmanje od sredine 1960-ih, a prvi potpuni opis pojavio se 1967. godine.

CSR format čuva retku m × n matricu M u obliku reda koristeći tri (jednodimenzionalna) niza (V, COL_INDEX, ROW_INDEX). Neka NNZ označava broj ne-nultih unosa u M. (Imajte na umu da će se ovde koristiti indeksi zasnovani na nuli.)

Nizovi V i COL_INDEX su dužine NNZ i sadrže vrednosti koje nisu nula i indekse kolona tih vrednosti.

Niz ROW_INDEX je dužine m + 1 i kodira indeks u V i COL_INDEX odakle započinje dati red.

Poslednji element je NNZ, tj. fiktivni indeks u V neposredno posle poslednjeg validnog indeksa NNZ - 1.

Na primer, matrica (5 0 0 0;0 8 0 0;0 0 3 0;0 6 0 0) je 4x4 matrica sa 4 elementa koji nisu nula, stoga

v = [ 5 8 3 6 ]

COL_INDEX = [ 0 1 2 1 ]

ROW_INDEX = [ 0 1 2 3 4 ]

pretpostavlja se jezik indeksiran nulom.

Da bi se izdvojio red, prvo definišemo:

row_start = ROW_INDEX[row]

row_end = ROW_INDEX[row + 1]

Zatim uzimamo delove od V i COL_INDEX započinjući u row_start i završavajući u row_end.

Da bismo izdvojili red 1 (drugi red) ove matrice postavili smo row_start=1 i row_end=2. Zatim pravimo delove v[1:2]=[8] i COL_INDEX[1:2]=[1]. Sada znamo da u redu 1 imamo jedan element u koloni 1 sa vrednošću 8.

U ovom slučaju CSR reprezentacija sadrži 13 unosa, u poređenju sa 16 u originalnoj matrici. CSR format štedi na memoriji samo kada je NNZ < (m (n - 1) - 1) / 2. Drugi primer, matrica [10 20 0 0 0 0; 0 30 0 40 0 0; 0 0 50 60 70 0; 0 0 0 0 0 80] je 4x6 matrica (24 unosa) sa 8 ne-nultih elemenata, stoga v = [10 20 30 40 50 60 70 80], COL_INDEX = [0 1 1 3 2 3 4 5], ROW_INDEX = [0 2 4 7 8].

Ceo red se skladišti kao 21 unos.

• ROW_INDEX deli niz V u redove (10,20) (30,40) (50,60,70) (80)
• COL_INDEX poravnava vrednosti u kolone (10,20,...) (0,30,0,40,...) (0,0,50,60,70,0) (0,0,0,0,0,80)

Imajte na umu da je u ovom formatu prva vrednost ROW_INDEX- a uvek nula, a poslednja uvek NNZ, tako da su oni u nekom smislu suvišni (iako u programskim jezicima gde dužina niza treba da bude eksplicitno uskladištena, NNZ ne bi bio suvišan). Ipak, ovo izbegava potrebu da se obračunava izuzetan slučaj prilikom izračunavanja dužine svakog reda, jer to garantuje da formula ROW_INDEX[i + 1] - ROW_INDEX[i] radi za bilo koji red i. Štaviše, troškovi memorije ovog suvišnog skladišta verovatno su beznačajni za dovoljno veliku matricu.

(Stari i novi) Yale-ovi formati proređene matrice su primeri CSR šeme. Stari Yale format radi tačno onako kako je gore opisano, sa tri niza; novi format kombinuje ROW_INDEX i COL_INDEX u jedan niz i odvojeno obrađuje dijagonalu matrice.

Za matrice logičkog susedstva, niz podataka može biti izostavljen, jer je postojanje unosa u nizu redova dovoljno za modeliranje odnosa binarnog susedstva.

Ovo je verovatno poznato kao Yale format jer je predložen u izveštaju Yale Sparse Matrix 1977. godine iz Odeljenja za računarske nauke na Yale univerzitetu.

Kompresovana proređena kolona (Compressed sparse column - CSC ili CCS)

CSC (http://netlib.org/linalg/html_templates/node92.html#SECTION00931200000000000000) je sličan CSR-u, osim što se vrednosti čitaju prvo po koloni, indeks reda se čuva za svaku vrednost, a skladište se i pokazivači kolone. Na primer, CSC je (val, row_ind, col_ptr), gde je val niz (od vrha do dna, a zatim sleva nadesno) ne-nultih vrednosti matrice; row_ind su indeksi redova koji odgovaraju vrednostima; i, col_ptr je lista indeksa val gde svaka kolona počinje. Naziv se zasniva na činjenici da su informacije o indeksu kolone kompresovane u odnosu na format COO. Obično se koristi drugi format (LIL, DOK, COO) za izgradnju. Ovaj format je efikasan za aritmetičke operacije, rezanje kolona i matrično-vektorske proizvode. Pogledajte scipy.sparse.csc_matrix (http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csc_matrix.html). Ovo je tradicionalni format za specifikaciju proređene matrice u MATLAB-u (putem (https://www.mathworks.com/help/matlab/ref/sparse.html funkcije).

Posebne strukture

Matrica opsega

Važna posebna vrsta retkih matrica je matrica opsega, definisana na sledeći način. Donji propusni opseg matrice A je najmanji broj p takav da unos ai,j nestaje kad god je i > j + p. Slično tome, gornji propusni opseg je najmanji broj p takav da je ai,j = 0 kad god je i < j - p (Golub & Van Loan 1996, §1.2.1). Na primer, tridijagonalna matrica ima donji propusni opseg 1 i gornji propusni opseg 1. Kao još jedan primer, sledeća proređena matrica ima i gornji i donji propusni opseg jednak 3. Primetite da su nule predstavljene tačkama radi jasnoće.

Matrice sa relativno malim gornjim i donjim propusnim opsegom poznate su kao matrice opsega i često se prilagođavaju jednostavnijim algoritmima od opštih retkih matrica;ili se ponekad može primeniti algoritam guste matrice i postići efikasnost jednostavnim prevlačenjem preko smanjenog broja indeksa.

Preuređivanjem redova i stupaca matrice A može biti moguće dobiti matricu A′ sa nižim propusnim opsegom. Brojni algoritmi su dizajnirani za minimiziranje propusnog opsega.

Dijagonalna

Veoma efikasna struktura za ekstremni slučaj matrica opsega, dijagonalna matrica služi tome da se samo unosi u glavnoj dijagonali čuvaju kao jednodimenzionalni niz, tako da dijagonalna n × n matrica zahteva samo n unosa.

Simetrična

Simetrična proređena matrica nastaje kao matrica susednosti neusmerenog grafa; može se efikasno čuvati kao lista susednosti.

Blok dijagonala

Blok-dijagonalna matrica sastoji se od pod-matrica duž svojih dijagonalnih blokova. Blok-dijagonalna matrica A ima oblik

gde je Ak kvadratna matrica za sve k = 1, …, n.

Smanjivanje popunjavanja

Popunjavanje matrice se odnosi na one unose koji se menjaju od početne nulte vrednosti do vrednosti koja nije nula tokom izvršavanja algoritma. Da bi se smanjili zahtevi za memorijom i broj aritmetičkih operacija korišćenih tokom algoritma, korisno je minimizirati popunjavanje prebacivanjem redova i kolona u matrici. Simbolična Choleksy razgradnja može se koristiti za izračunavanje najgoreg mogućeg popunjavanja pre nego što se izvrši stvarna Cholesky razgradnja. U upotrebi su druge metode osim Choleksy razgradnje. Metode ortogonalizacije (kao što je QR faktorizacija) su uobičajene, na primer, kada se problemi rešavaju metodama najmanjeg kvadrata. Iako je teorijsko popunjavanje još uvek isto, u praksi se „lažne ne-nule“ mogu razlikovati za različite metode. A simboličke verzije tih algoritama mogu se koristiti na isti način kao i simbolička Cholesky razgradnja za izračunavanje najgorih slučajeva popunjavanja.

Softver

Mnoge softverske biblioteke podržavaju proređene matrice, i pružaju rešenja za jednačine retkih matrica. Sledeći su open-source:

• SuiteSparse, skup algoritama proređene matrice, usmeren ka direktnom rešenju retkih linearnih sistema.
• PETSc, velika C biblioteka, koja sadrži mnoštvo različitih rešavača matrice za razne formate skladišta matrice.
• Trilinos, velika C ++ biblioteka, sa podbibliotekama posvećenim čuvanju gustih i retkih matrica i rešavanju odgovarajućih linearnih sistema.
• Eigen3 je C ++ biblioteka koja sadrži nekoliko rešavača retkih matrica. Međutim, nijedan od njih nije paralelizovan.
• MUMPS (MUltifrontal Massively Parallel sparse direct Solver), napisan u Fortran90, je frontalni rešavač.
• DUNE, biblioteka konačnih elemenata koja takođe ima podbiblioteku za proređene linearne sisteme i njihovo rešavanje.
• PaStik (http://pastix.gforge.inria.fr/).
• SuperLU (http://crd-legacy.lbl.gov/~xiaoye/SuperLU/).
• Armadillo nudi C ++ omot za BLAS i LAPACK koji je lagan za upotrebu.
• SciPy pruža podršku za nekoliko formata retkih matrica, linearnu algebru i rešavače.
• SPArse Matrix (spam) (https://cran.r-project.org/web/packages/spam/index.html) R paket za proređene matrice.
• Wolfram jezik (https://reference.wolfram.com/language/guide/SparseArrays.html) Alati za rukovanje retkim nizovima
• ALGLIB C ++ i C # biblioteka sa podrškom proređene linearne algebre
• ARPACK Fortran 77 biblioteka za dijagonalizaciju i manipulaciju retkim matricama, koristeći Arnoldijev algoritam
• SPARSE (https://www.netlib.org/sparse/) Referentni (stari) NIST paket za (stvarnu ili složenu) dijagonalizaciju proređene matrice
• SLEPc biblioteka za rešavanje linearnih sistema velikih razmera i retkih matrica
• Sympiler (https://www.sympiler.com/), generator koda i biblioteka za specifične domene za rešavanje linearnih sistema i problema kvadratnog programiranja.

Istorija

Izraz proređena matrica je verovatno skovao Henri Markovic koji je pokrenuo neke pionirske radove, ali je zatim napustio ovo polje.

Literatura

• Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd izd.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9. 
• Stoer, Josef; Bulirsch, Roland (2002). Introduction to Numerical Analysis (3rd izd.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-95452-3. 
• Tewarson, Reginald P. (maj 1973). Sparse Matrices (Part of the Mathematics in Science & Engineering series). Academic Press Inc. CS1 održavanje: Format datuma (veza) (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).
• Bank, Randolph E.; Douglas, Craig C. „Sparse Matrix Multiplication Package” (PDF). Arhivirano iz originala (PDF) 21. 12. 2014. g. Pristupljeno 01. 06. 2021. 
• Pissanetzky, Sergio (1984). Sparse Matrix Technology. Academic Press. ISBN 9780125575805. 
• Snay, Richard A. (1976). „Reducing the profile of sparse symmetric matrices”. Bulletin Géodésique. 50 (4): 341—352. Bibcode:1976BGeod..50..341S. S2CID 123079384. doi:10.1007/BF02521587. hdl:2027/uc1.31210024848523 .  Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.
• Saad, Yousef (2003). Iterative methods for sparse linear systems. SIAM. 
• Gibbs, Norman E.; Poole, William G.; Stockmeyer, Paul K. (1976). „A comparison of several bandwidth and profile reduction algorithms”. ACM Transactions on Mathematical Software. 2 (4): 322—330. S2CID 14494429. doi:10.1145/355705.355707. 
• Gilbert, John R.; Moler, Cleve; Schreiber, Robert (1992). „Sparse matrices in MATLAB: Design and Implementation”. SIAM Journal on Matrix Analysis and Applications. 13 (1): 333—356. CiteSeerX 10.1.1.470.1054 . doi:10.1137/0613024. 

Spoljašnje veze

• Sparse Matrix Algorithms Research at the Texas A&M University.
• SuiteSparse Matrix Collection
• SMALL project A EU-funded project on sparse models, algorithms and dictionary learning for large-scale data.