Matricea rară - Sparse matrix

Exemplu de matrice rară ${\ displaystyle \ left ({\ begin {smallmatrix} 11 & 22 & 0 & 0 & 0 & 0 & 0 \\ 0 & 33 & 44 & 0 & 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 \\\ end {smallmat})$

Matricea rar de mai sus conține doar 9 elemente diferite de zero, cu 26 de elemente zero. Raritatea sa este de 74%, iar densitatea sa este de 26%.

O matrice rară obținută la rezolvarea unei probleme de element finit în două dimensiuni. Elementele diferite de zero sunt afișate în negru.

În analiza numerică și calculul științific , o matrice rară sau o matrice rară este o matrice în care majoritatea elementelor sunt zero. Nu există o definiție strictă cu privire la proporția elementelor cu valoare zero pentru ca o matrice să se califice ca fiind rară, dar un criteriu comun este acela că numărul de elemente diferite de zero este aproximativ egal cu numărul de rânduri sau coloane. În schimb, dacă majoritatea elementelor sunt diferite de zero, matricea este considerată densă . Numărul de elemente cu valoare zero împărțit la numărul total de elemente (de exemplu, m × n pentru o matrice m × n) este uneori denumit raritatea matricei.

Conceptual, raritatea corespunde sistemelor cu puține interacțiuni perechi. De exemplu, luați în considerare o linie de bile conectate prin arcuri de la unul la altul: acesta este un sistem rar, deoarece numai bile adiacente sunt cuplate. În schimb, dacă aceeași linie de bile ar avea arcuri care leagă fiecare bilă de toate celelalte bile, sistemul ar corespunde unei matrice dense. Conceptul de raritate este util în combinatorică și domenii de aplicare, cum ar fi teoria rețelelor și analiza numerică , care de obicei au o densitate scăzută de date sau conexiuni semnificative. Matricile mari rare apar adesea în aplicații științifice sau inginerești atunci când se rezolvă ecuații diferențiale parțiale .

Atunci când se stochează și se manipulează matrici rare pe un computer , este benefic și adesea necesar să se utilizeze algoritmi specializați și structuri de date care să profite de structura mică a matricei. Au fost realizate computere specializate pentru matrici rare, deoarece acestea sunt comune în domeniul învățării automate. Operațiile care utilizează structuri și algoritmi standard cu matrice densă sunt lente și ineficiente atunci când sunt aplicate matricilor mari rare, deoarece procesarea și memoria sunt irosite pe zerouri. Datele rare sunt prin natura lor mai ușor de comprimat și, prin urmare, necesită mult mai puțină stocare . Unele matrici rare foarte mari sunt imposibil de manipulat folosind algoritmi standard cu matrice densă.

Stocarea unei matrici rare

O matrice este de obicei stocată ca o matrice bidimensională. Fiecare intrare din matrice reprezintă un element a _{i , j} al matricei și este accesată de cei doi indici i și j . În mod convențional, i este indicele rândului, numerotat de sus în jos și j este indexul coloanei, numerotat de la stânga la dreapta. Pentru o matrice m × n , cantitatea de memorie necesară pentru a stoca matricea în acest format este proporțională cu m × n (fără a ține cont de faptul că dimensiunile matricei trebuie, de asemenea, să fie stocate).

În cazul unei matrici rare, reducerile substanțiale ale cerinței de memorie pot fi realizate stocând doar intrările diferite de zero. În funcție de numărul și distribuția intrărilor diferite de zero, pot fi utilizate diferite structuri de date și generează economii uriașe în memorie în comparație cu abordarea de bază. Schimbul este că accesarea elementelor individuale devine mai complexă și sunt necesare structuri suplimentare pentru a putea recupera matricea originală fără ambiguități.

Formatele pot fi împărțite în două grupe:

• Cei care acceptă modificări eficiente, cum ar fi DOK (Dicționar de chei), LIL (Lista listelor) sau COO (Lista coordonatelor). Acestea sunt de obicei utilizate pentru a construi matricile.
• Cele care acceptă operațiuni eficiente de acces și matrice, cum ar fi CSR (Compressed Sparse Row) sau CSC (Compressed Sparse Column).

Dicționar de chei (DOK)

DOK constă dintr-un dicționar care mapează (rând, coloană) - perechi la valoarea elementelor. Elementele care lipsesc din dicționar sunt considerate zero. Formatul este bun pentru construirea incrementală a unei matrici rare în ordine aleatorie, dar slab pentru iterarea peste valori diferite de zero în ordine lexicografică. Unul construiește de obicei o matrice în acest format și apoi convertește într-un alt format mai eficient pentru procesare.

Lista listelor (LIL)

LIL stochează o listă pe rând, fiecare intrare conținând indexul coloanei și valoarea. De obicei, aceste intrări sunt păstrate sortate după indexul coloanei pentru căutare mai rapidă. Acesta este un alt format bun pentru construcția matricei incrementale.

Lista coordonatelor (COO)

COO stochează o listă de tupluri (rând, coloană, valoare) . În mod ideal, intrările sunt sortate mai întâi după indexul rândurilor și apoi după indexul coloanelor, pentru a îmbunătăți timpul de acces aleatoriu. Acesta este un alt format care este bun pentru construcția matricei incrementale.

Rând rar comprimat (format CSR, CRS sau Yale)

Rând comprimat rare (CSR) sau stocare comprimat rând (SIR) sau formatul Yale reprezintă o matrice M de trei (una unidimensionale), care respectiv conțin valori nenule, cu extinderile rândurilor și indici de coloane. Este similar cu COO, dar comprimă indicii rândurilor, de unde și numele. Acest format permite accesul rapid al rândurilor și multiplicări matrice-vectoriale ( M x ). Formatul CSR a fost utilizat cel puțin de la mijlocul anilor 1960, prima descriere completă apărând în 1967.

Magazinele format CSR o sparse m x n matrice M în formă rând folosind trei (una unidimensionale) (V, COL_INDEX, ROW_INDEX) . Fie NNZ reprezintă numărul de intrări în nenuli M . (Rețineți că aici vor fi folosiți indici pe bază de zero .)

• Matricele V și COL_INDEX sunt de lungime NNZ și conțin nenuli valori și indicii coloană ale acestor valori , respectiv.

• Matricea ROW_INDEX are lungimea m + 1 și codifică indexul în V și COL_INDEX de unde începe rândul dat. Acest lucru este echivalent cu ROW_INDEX [j] care codifică numărul total de nonzero deasupra rândului j . Ultimul element este NNZ , adică indexul fictiv din V imediat după ultimul index valid NNZ - 1 .

De exemplu, matricea

${\ displaystyle {\ begin {pmatrix} 5 & 0 & 0 & 0 \\ 0 & 8 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 6 & 0 & 0 \\\ end {pmatrix}}}$

este o matrice 4 × 4 cu 4 elemente diferite de zero, deci

   V         = [ 5 8 3 6 ]
   COL_INDEX = [ 0 1 2 1 ]
   ROW_INDEX = [ 0 1 2 3 4 ] 

presupunând un limbaj zero indexat.

Pentru a extrage un rând, mai întâi definim:

   row_start = ROW_INDEX[row]
   row_end   = ROW_INDEX[row + 1]

Apoi luăm felii din V și COL_INDEX începând de la rândul_start și terminând la rândul_end.

Pentru a extrage rândul 1 (al doilea rând) al acestei matrice am setat row_start=1și row_end=2. Apoi facem feliile V[1:2] = [8]și COL_INDEX[1:2] = [1]. Acum știm că în rândul 1 avem un element la coloana 1 cu valoarea 8.

În acest caz, reprezentarea CSR conține 13 intrări, comparativ cu 16 în matricea originală. Formatul CSR salvează în memorie numai când NNZ <( m ( n - 1) - 1) / 2 . Un alt exemplu, matricea

${\ 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}}}$

este o matrice 4 × 6 (24 intrări) cu 8 elemente diferite de zero, deci

   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 ]

Întregul este stocat ca 21 de intrări.

• ROW_INDEX împarte matrice V în rânduri: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX valori se aliniaza in coloane: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Rețineți că în acest format, prima valoare a ROW_INDEX este întotdeauna zero și ultima este întotdeauna NNZ , deci sunt într-un anumit sens redundante (deși în limbajele de programare unde lungimea matricei trebuie să fie stocată în mod explicit, NNZ nu ar fi redundantă). Cu toate acestea, acest lucru evită nevoia de a gestiona un caz excepțional atunci când se calculează lungimea fiecărui rând, deoarece garantează formula ROW_INDEX [ i + 1] - ROW_INDEX [ i ] funcționează pentru orice rând i . Mai mult, costul memoriei acestei stocări redundante este probabil nesemnificativ pentru o matrice suficient de mare.

Formatele (vechi și noi) ale matricii rare Yale sunt instanțe ale schemei CSR. Vechiul format Yale funcționează exact așa cum este descris mai sus, cu trei tablouri; noile combinelor format ROW_INDEX și COL_INDEX într - o singură matrice și mânere diagonala matricei separat.

Pentru matricile de adiacență logice , matricea de date poate fi omisă, deoarece existența unei intrări în matricea de rânduri este suficientă pentru a modela o relație de adiacență binară.

Este cunoscut probabil ca formatul Yale, deoarece a fost propus în raportul din 1977 al pachetului Yale Sparse Matrix de la Departamentul de Informatică de la Universitatea Yale.

Coloană rar comprimată (CSC sau CCS)

CSC este similar cu CSR, cu excepția faptului că valorile sunt citite mai întâi de coloană, un indice de rând este stocat pentru fiecare valoare și indicatorii de coloană sunt stocate. De exemplu, CSC este (val, row_ind, col_ptr) , unde val este o matrice a valorilor (zero de sus în jos, apoi de la stânga la dreapta) diferite de zero ale matricei; rând_ind este indicii rândului care corespund valorilor; și, col_ptr este lista indexurilor val de unde începe fiecare coloană. Numele se bazează pe faptul că informațiile despre indexul coloanei sunt comprimate în raport cu formatul COO. Unul folosește de obicei un alt format (LIL, DOK, COO) pentru construcție. Acest format este eficient pentru operații aritmetice, tranșarea coloanelor și produse vector-matrice. Vezi scipy.sparse.csc_matrix . Acesta este formatul tradițional pentru specificarea unei matrice rare în MATLAB (prin intermediul sparsefuncției).

Structură specială

În bandă

Un tip special important de matrice rare este matricea de benzi , definită după cum urmează. Lățime de bandă mai mică a unei matrice A este cel mai mic număr p astfel încât intrarea unui _{i , j} dispare ori de câte ori i > j + p . În mod similar, lățimea de bandă superioară este cel mai mic număr p astfel încât a _{i , j} = 0 ori de câte ori i < j - p ( Golub & Van Loan 1996 , §1.2.1). De exemplu, o matrice tridiagonală are lățimea de bandă inferioară 1 și lățimea de bandă superioară 1 . Ca un alt exemplu, următoarea matrice rară are lățimea de bandă inferioară și superioară ambele egale cu 3. Observați că zerourile sunt reprezentate cu puncte pentru claritate.

${\ displaystyle \ 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 & \ cd cdot & X & \ cdot & X & \\\ end {smallmatrix}} \ right)}$

Matricile cu lățime de bandă superioară și inferioară destul de mică sunt cunoscute sub numele de matrici de bandă și se pretează adesea la algoritmi mai simpli decât matricile generale rare; sau, uneori, se pot aplica algoritmi cu matrice densă și pot câștiga eficiență pur și simplu prin looping pe un număr redus de indici.

Prin rearanjarea rândurilor și coloanelor unei matrice A poate fi posibil să se obțină o matrice A ′ cu o lățime de bandă mai mică. O serie de algoritmi sunt proiectați pentru minimizarea lățimii de bandă .

Diagonală

O structură foarte eficientă pentru un caz extrem de matrice de benzi, matricea diagonală , este stocarea doar a intrărilor în diagonala principală ca o matrice unidimensională , astfel încât o matrice diagonală n × n necesită doar n intrări.

Simetric

O matrice rară simetrică apare ca matricea de adiacență a unui grafic neorientat ; poate fi stocat eficient ca o listă de adiacență .

Diagonală bloc

O matrice bloc-diagonală constă din sub-matrice de-a lungul blocurilor sale diagonale. O matrice diagonală bloc A are forma

${\ displaystyle \ mathbf {A} = {\ begin {bmatrix} \ mathbf {A} _ {1} & 0 & \ cdots & 0 \\ 0 & \ mathbf {A} _ {2} & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & \ mathbf {A} _ {n} \ end {bmatrix}},}$

unde A _k este o matrice pătrată pentru toate k = 1, ..., n .

Reducerea completării

De umplere a unei matrice sunt acele intrări care se schimbă de la un zero , inițial la o valoare nenulă în timpul executării unui algoritm. Pentru a reduce cerințele de memorie și numărul de operații aritmetice utilizate în timpul unui algoritm, este util să minimizați completarea prin comutarea rândurilor și coloanelor din matrice. Descompunerea Cholesky simbolic poate fi folosit pentru a calcula umplerea în cel mai rău posibil , înainte de a face efectiv descompunerea Cholesky .

Există alte metode decât descompunerea Cholesky în uz. Metodele de ortogonalizare (cum ar fi factorizarea QR) sunt frecvente, de exemplu, atunci când se rezolvă probleme prin metode de cel puțin pătrate. În timp ce completarea teoretică este încă aceeași, în termeni practici „falsele zerouri false” pot fi diferite pentru diferite metode. Iar versiunile simbolice ale acestor algoritmi pot fi folosite în același mod ca simbolul Cholesky pentru a calcula completarea cazului cel mai rău.

Rezolvarea ecuațiilor matricei rare

Ambele metode iterative și directe există pentru rezolvarea matricii rare.

Metodele iterative, cum ar fi metoda gradientului conjugat și GMRES utilizează calcule rapide ale produselor matrice-vector , unde matricea este rară. Utilizarea precondiționarilor poate accelera semnificativ convergența unor astfel de metode iterative. ${\ displaystyle Ax_ {i}}$${\ displaystyle A}$

Software

Multe biblioteci software acceptă matrici rare și oferă soluții pentru ecuații ale matricei rare. Următoarele sunt open-source:

• SuiteSparse , o suită de algoritmi cu matrice rară, orientată spre soluția directă a sistemelor liniare rare.
• PETSc , o bibliotecă mare C, care conține mai multe soluții de matrice diferite pentru o varietate de formate de stocare a matricei.
• Trilinos , o bibliotecă mare C ++, cu sub-biblioteci dedicate stocării matricilor dense și rare și soluției sistemelor liniare corespunzătoare.
• Eigen3 este o bibliotecă C ++ care conține mai mulți rezolvatori de matrici rare. Cu toate acestea, niciuna dintre ele nu este paralelizată .
• MUMPS ( MU ltifrontal M assively P arallel rare directă S Olver), scrisă în Fortran90, este un solver frontal .
• DUNE , o bibliotecă cu elemente finite care are și o sub-bibliotecă pentru sisteme liniare rare și soluția lor.
• PaStix .
• SuperLU .
• Armadillo oferă un ambalaj C ++ ușor de utilizat pentru BLAS și LAPACK.
• SciPy oferă suport pentru mai multe formate matriciale rare, algebră liniară și rezolvatori.
• SPArse Matrix (spam) R și pachetul Python pentru matrici rare.
• Instrumente de limbaj Wolfram pentru manipularea matricelor rare
• ALGLIB este o bibliotecă C ++ și C # cu suport algebric liniar rar
• Biblioteca ARPACK Fortran 77 pentru diagonalizarea și manipularea matricei rare, utilizând algoritmul Arnoldi
• Pachetul de referință SPARSE (vechi) NIST pentru diagonalizarea matricei rare (reale sau complexe)
• Biblioteca SLEPc pentru soluția sistemelor liniare la scară largă și a matricelor rare
• Sympiler , un generator de cod și bibliotecă specific domeniului pentru rezolvarea sistemelor liniare și a problemelor de programare pătratică.
• Scikit-learn Un pachet Python pentru analiza datelor, inclusiv matrici rare.

Istorie

Termenul de matrice rar a fost inventat de Harry Markowitz, care a inițiat o lucrare de pionierat, dar a părăsit terenul.

Vezi si

Note

Referințe

• Golub, Gene H .; Van Loan, Charles F. (1996). Calcule matrice (ediția a 3-a). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Stoer, Josef; Bulirsch, Roland (2002). Introducere în analiza numerică (ediția a 3-a). Berlin, New York: Springer-Verlag . ISBN 978-0-387-95452-3.
• Tewarson, Reginald P. (mai 1973). Matrici rare (parte a seriei Matematică în știință și inginerie) . Academic Press Inc. (Această carte, a unui profesor de la Universitatea de Stat din New York la Stony Book, a fost prima carte dedicată exclusiv matricilor rare. Cursurile postuniversitare care au folosit acest lucru ca manual au fost oferite la acea universitate la începutul anilor 1980).
• Bank, Randolph E .; Douglas, Craig C. „Pachet de multiplicare a matricei rare” (PDF) .
• Pissanetzky, Sergio (1984). Tehnologie Sparse Matrix . Academic Press.
• Snay, Richard A. (1976). "Reducerea profilului matricilor simetrice rare". Buletinul Géodésique . 50 (4): 341-352. Cod Bib : 1976BGeod..50..341S . doi : 10.1007 / BF02521587 . hdl : 2027 / uc1.31210024848523 . S2CID  123079384 . De asemenea, Memorandumul Tehnic NOAA NOS NGS-4, National Geodetic Survey, Rockville, MD.

Lecturi suplimentare

• Gibbs, Norman E .; Poole, William G .; Stockmeyer, Paul K. (1976). „O comparație a mai multor lățimi de bandă și algoritmi de reducere a profilului” . Tranzacții ACM pe software matematic . 2 (4): 322-330. doi : 10.1145 / 355705.355707 . S2CID  14494429 .
• Gilbert, John R .; Moler, Cleve; Schreiber, Robert (1992). "Matrici rare în MATLAB: Proiectare și implementare" . SIAM Journal on Matrix Analysis and Applications . 13 (1): 333–356. CiteSeerX  10.1.1.470.1054 . doi : 10.1137 / 0613024 .
• Sparse Matrix Algorithms Research la Texas A&M University.
• Colecția SuiteSparse Matrix
• Proiect MIC Un proiect finanțat de UE privind modele rare, algoritmi și învățare a dicționarelor pentru date la scară largă.