Matrice goală

În disciplina analizei numerice a matematicii , o matrice rară este o matrice care conține o mulțime de zerouri.

Conceptual, matricele rare corespund unor sisteme care nu sunt foarte cuplate. Dacă luăm în considerare o linie de bile, fiecare dintre ele fiind conectată la vecinii săi direcți prin benzi de cauciuc, acest sistem ar fi reprezentat de o matrice goală. Dimpotrivă, dacă fiecare bilă din linie este conectată la toate celelalte bile, acest sistem ar fi reprezentat de o matrice densă . Acest concept de matrice rară este utilizat pe scară largă în analiza combinatorie și câmpurile sale de aplicare, cum ar fi teoria rețelelor , care au o densitate redusă a conexiunilor.

Matrici mari rare apar adesea în știință sau inginerie pentru rezolvarea ecuațiilor diferențiale parțiale .

Atunci când dorim să manipulăm sau să stocăm matrici rare folosind instrumentul computerizat, este avantajos sau chiar adesea necesar să folosim algoritmi și structuri de date care țin cont de structura rară a matricei: deoarece coordonatele rândurilor și coloanelor oferă acces la o adresă, indiferent de a organizării fizice a datelor.

Reprezentarea fizică a tuturor acestor zerouri în memorie atunci când este utilizată pe matrici mari rare ar fi costisitoare și lentă. Este mai ieftin și mai rapid să spunem că orice valoare necompletată pentru coordonatele date este zero. Această comprimare a datelor duce aproape întotdeauna la o diviziune semnificativă a consumului de memorie, pentru un cost suplimentar neglijabil de procesare. Cu toate acestea, unele matrici rare foarte mari nu pot fi tratate de algoritmi convenționali.

Structura de date naivă utilizată pentru a stoca o matrice este o matrice bidimensională. Fiecare intrare din matrice reprezintă un element a i , j al matricei la care se poate ajunge prin cei doi indici i și j . Pentru o matrice m × n , sunt necesare cel puțin ( m × n ) spații de memorie de dimensiuni fixe pentru a reprezenta matricea.

Multe, dacă nu majoritatea intrărilor dintr-o matrice rară sunt zerouri. Ideea de bază este apoi de a stoca doar intrările diferite de zero ale matricei, mai degrabă decât de a le stoca pe toate. În funcție de numărul și distribuția de intrări diferite de zero, pot fi utilizate diferite structuri de date și duc la economii mari în dimensiunea utilizată în memorie în comparație cu structura naivă. Această tehnică este utilizată și atunci când matricea reprezintă un grafic : dacă marginea bitului, este preferată lista de adiacențe pentru matricea de adiacență .

Un exemplu de astfel de reprezentare este formatul Yale Sparse Matrix. Stochează o matrice M de dimensiunea m × n ca trei tablouri unidimensionale. Dacă notăm NNNnumărul de intrări în matrice nenulă M .

Prima matrice este notată Ași are o lungime NNN. Conține toate valorile intrărilor diferite de zero ale lui M de la stânga la dreapta și de sus în jos (valorile sunt luate de la stânga la dreapta pe primul rând, apoi de la stânga la dreapta pe al doilea și așa mai departe ).

A doua matrice este notată IAprin lungime (numărul de rânduri plus unul). Este definit recursiv: și unde este numărul de intrări diferite de zero în rândul i (indexarea de la 0). Linia i a matricei originale M este alcătuită din elementele de la index la index (sau altfel este goală dacă ). $m + 1$ IA(0)=0IA(i+1)=IA(i)+NNNiNNNiAIA(i)IA(i+1)-1IA(i)=IA(i+1)

A treia matrice este notată JAprin lungime NNNconține numărul coloanei fiecărui element din A.

De exemplu, următoarea matrice 4 × 8
[ 1 2 0 0 0 0 0 0 ] [ 0 3 0 0 0 0 9 0 ] [ 0 0 0 0 0 0 0 0 ] [ 0 0 1 0 0 0 0 4 ]
este reprezentat în acest format de
A = [ 1 2 3 9 1 4 ] IA = [ 0 2 4 4 6 ] JA = [ 0 1 1 6 2 7 ]

Exemplu

O hartă de biți care are doar două culori, dintre care una este dominantă (de exemplu, un fișier care conține o semnătură), poate fi salvată ca o matrice rară care conține doar pixelii culorii non-dominante.

Matrici diagonale

O structură foarte eficientă pentru stocarea unei matrice diagonale este stocarea numai a intrărilor diagonalei principale într-un tablou unidimensional. O n × n matrice diagonală necesită doar n intrări.

Lățime de bandă

Lățime de bandă redusă a unei matrice M este cel mai mic număr întreg p astfel încât intrările de ij sunt zero pentru i > j + p. La fel, lățimea de bandă mare este cel mai mic număr întreg p astfel încât intrările a ij sunt zero pentru i < j - p. De exemplu, o matrice tridiagonală are o lățime de bandă scăzută de 1 și o lățime de bandă mare de 1.

Matricile cu lățimi mici de bandă înaltă și joasă sunt denumite matrici de bandă (în) și algoritmi mai eficienți decât cei de pe matricele rare.

De exemplu, algoritmul Cuthill-McKee (în) reduce lățimea de bandă a unei matrice goale și simetrică și există multe alte metode pentru a reduce această lățime de bandă.

Fenomen de umplere

De umplere a unei matrice rară reprezintă numărul de intrări care, în timpul executării unui algoritm, du - te de la o valoare zero , la o altă valoare decât zero. Pentru a reduce cerințele suplimentare în memorie și în costurile de calcul pe care le induce acest fenomen, este necesar să se limiteze această umplere, care se poate face prin schimbarea coloanelor și rândurilor matricei. Umplerea este o noțiune teoretică care nu se schimbă între diferiții algoritmi ( factorizarea Cholesky , descompunerea QR etc.) care pot fi aplicate matricei, dar numărul de zerouri care iau o valoare diferită de zero în timpul execuției variază în funcție de 'algoritmul aplicat, iar unii algoritmi au un simbol de versiune care oferă umplerea în cel mai rău caz, cum ar fi descompunerea simbolică Cholesky (în) .

Rezolvarea ecuațiilor reprezentate de o matrice rară

Există metode iterative și directe pentru rezolvarea sistemelor reprezentate prin matrici rare. O metodă iterativă larg utilizată este metoda gradientului conjugat .

Referințe

(fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „ Sparse matrix ” ( vezi lista autorilor ) .
(ro) Reginald P. Tewarson, Sparse Matrices (parte a seriei Matematică în științe și inginerie), Academic Press, 1973
(ro) Randolph E. Bank și Craig C. Douglas, pachet de multiplicare a matricei rare
(ro) Sergio Pissanetzky, Sparse Matrix Technology , Academic Press, 1984
(ro) RA Snay, „Reducerea profilului matricilor simetrice rare”, în Bulletin Géodésique , 50: 341–352, 1976. De asemenea, în Memorandumul Tehnic NOAA NOS NGS-4, National Geodetic Survey, Rockville, MD

linkuri externe

(ro) John R. Gilbert, Cleve Moler și Robert Schreiber, „ Sparse matrices in MATLAB: Design and Implementation ” , SIAM Journal on Matrix Analysis and Applications , vol. 13, n o 1,1992, p. 333-356 ( DOI 10.1137 / 0613024 , citiți online )
(ro) Cercetarea algoritmilor cu matrici rare la Universitatea din Florida
(ro) R.Buda, „Procedura de agregare bidimensională: o alternativă la algoritmul algebric al matricei” , în Computational Economics , 31 (4), 2008, p. 397-408