Matrice rară

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 13 decembrie 2021; verificările necesită 4 modificări .

O matrice rară este o matrice cu în mare parte zero elemente. În caz contrar, dacă majoritatea elementelor matricei sunt diferite de zero, matricea este considerată a fi densă .

Printre experți, nu există o unitate în a determina exact câte elemente diferite de zero fac o matrice rară. Diferiți autori oferă opțiuni diferite. Pentru o matrice de ordin n, numărul de elemente nenule [1] :

este O(n) . O astfel de definiție este potrivită doar pentru analiza teoretică a proprietăților asimptotice ale algoritmilor matrici;
în fiecare linie nu depășește 10 într-un caz tipic;
limitat unde . $n^{{1+\gamma }}$ $\gamma<1$
este de așa natură încât are sens ca un anumit algoritm și sistem de calcul să beneficieze de prezența zerourilor în el [1] .

Matrici uriașe rare apar adesea atunci când se rezolvă probleme precum ecuațiile cu diferențe parțiale .

Atunci când stocați și convertiți matrici rare într-un computer , este util și adesea necesar să folosiți algoritmi speciali și structuri de date care iau în considerare structura matricei rare. Operațiile și algoritmii utilizați pentru a lucra cu matrici obișnuite, dense, în raport cu matricele rare și mari, sunt relativ lente și necesită cantități semnificative de memorie. Cu toate acestea, matricele rare pot fi comprimate cu ușurință prin scrierea doar a elementelor lor diferite de zero, ceea ce reduce cerințele de memorie ale computerului .

Prezentare

Există mai multe moduri de a stoca (reprezenta) matrici rare, care diferă:

comoditatea schimbării structurii matricei (se folosește în mod activ adresarea indirectă) - acestea sunt structuri sub formă de liste și dicționare.
viteza de acces la elemente și posibila optimizare a calculelor matriceale (se folosesc mai des blocuri dense, crescând localitatea accesului la memorie).

Un dicționar de chei (DOK - Dictionary of Keys) este construit ca un dicționar, unde cheia este o pereche ( rând, coloană ), iar valoarea este elementul matricei corespunzător rândului și coloanei.

O listă de liste (LIL - List of Lists) este construită ca o listă de șiruri, unde un șir este o listă de noduri de forma ( coloană, valoare ).

Lista de coordonate (COO - Lista de coordonate) este o listă de elemente din formular (linie, coloană, valoare).

Stocare pe rând comprimat (CSR - Rând rar comprimat, CRS - Stocare pe rând comprimat, format Yale)

Reprezentăm matricea originală care conține valori diferite de zero ca trei tablouri: $M^{n\times m)$ $N_{NZ)$

matrice de valori - o matrice de dimensiune , care stochează valori diferite de zero luate într-un rând de pe primul rând non-vid, apoi valorile din următorul rând non-vid etc. $N_{NZ)$
matrice de indici de coloane este o matrice de dimensiuni și stochează numerele de coloane corespunzătoare elementelor din matricea de valori. $N_{NZ)$
matrice de indexare a rândurilor - o matrice de dimensiune (număr de rânduri + 1), pentru index stochează numărul de elemente diferite de zero în rânduri de la primul până la rând inclusiv, este de remarcat faptul că ultimul element al indexării rândului matrice este aceeași cu , iar primul este întotdeauna egal cu . $n+1$ $i$ $i-1$ $N_{NZ)$ $0$

Exemple:

Lasă atunci $M={\begin{pmatrix}1&2&0\\0&4&0\\0&2&6\end{pmatrix}}$

array_of_values = { 1 , 2 , 4 , 2 , 6 } array of column_indexes = { 0 , 1 , 1 , 1 , 2 } array of_row_indexing = { 0 , 2 , 3 , 5 } -- stocați primul 0 ca element de blocare

Lasă atunci $M={\begin{pmatrix}1&2&0&3\\0&0&4&0\\0&1&0&11\end{pmatrix}}$

matrice_de_valori = { 1 , 2 , 3 , 4 , 1 , 11 } matrice de indici_coloană = { 0 , 1 , 3 , 2 , 1 , 3 } matrice_de_rânduri_de_index = { 0 , 3 , 4 , 6 primul } -- stochează 0 ca element de blocare

Pentru a restabili matricea originală, trebuie să luați o anumită valoare în prima matrice și indexul corespunzător , apoi numărul coloanei , iar numărul rândului este găsit ca cel mai mic , pentru care , acest lucru este convenabil, de exemplu, atunci când matricea înmulțirea cu un vector dens $v$ $i_{v}:Arr_{valori}[i_{v}]=v$ $n_{c}=Arr_{cols}[i_{v}]$ $n_{r}$ $n_{r}$ $Arr_{rânduri}[n_{r}+1]\geq i_{v}+1$

void smdv ( const crsm * A , double * b , const double * v ) // b += Av { // crsm este o structură {int n, int m, int nnz, double aval[], double aicol[], double airrow[]}; pentru ( int rând = 0 ; rând < n ; ++ rând ) pentru ( int i = A -> aer [ rând ]; i < A -> aer [ rând + 1 ]; ++ i ) b [ rând ] += A -> aval [ i ] * v [ A -> aicol [ i ]]; }

Stocare pe coloană comprimată (CSС - Coloană rară comprimată, CСS - Stocare pe coloană comprimată)

La fel ca CRS, doar rândurile și coloanele își schimbă rolurile - stocăm valori pe coloane, putem determina rândul din a doua matrice, după calcule cu a treia matrice - recunoaștem coloanele.

Biblioteci de software

Pentru calcule cu matrici rare, au fost create o serie de biblioteci pentru diferite limbaje de programare, printre care:

SparseLib++ ( C++ ) [2]
uBLAS (C++, parte din Boost ) [3]
SPARSPAK ( Fortran ) [4]
CSparse ( C ) [5]
Modul rar din biblioteca SciPy ( Python ) [6] [7] .

Note

↑ 1 2 Pissanecki, 1988 , Introducere.
↑ SparseLib++ . Data accesului: 1 august 2012. Arhivat din original pe 21 septembrie 2012. (nedefinit)
↑ uBLAS/Boost . Preluat la 1 august 2012. Arhivat din original la 4 august 2012. (nedefinit)
↑ Alan George, Esmond Ng. O scurtă descriere a pachetului de ecuații liniare rare SPARSPAK Waterloo // Buletin informativ ACM SIGNUM, Volumul 19 Numărul 4, Octombrie 1984. - NY, 1984. - P. 17-20 . — ISBN 978-1-4503-0245-6 . - doi : 10.1145/1057931.1057933 .
^ TA Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, septembrie 2006 . Data accesului: 1 august 2012. Arhivat din original la 29 iulie 2012. (nedefinit)
↑ Matrici rare (scipy.sparse), Ghid de referință SciPy . Consultat la 22 aprilie 2017. Arhivat din original pe 23 aprilie 2017. (nedefinit)
↑ Algebră liniară rară (scipy.sparse.linalg), Ghid de referință SciPy . Consultat la 22 aprilie 2017. Arhivat din original pe 23 aprilie 2017. (nedefinit)

Literatură

Reginald P Tewarson. Matrici rare. - Presa Academică, 1973. - 160 p. — ISBN 0126856508 . traducere: Tuarson R. Sparse Matrices = Sparse Matrices. - M . : Mir, 1977. - 191 p.
Pissanecki S. Sparse Matrix Technology = Sparse Matrix Technology. — M .: Mir, 1988. — 410 p. - ISBN 5-03-000960-4 .
George A., Liu J. Computer Solution of Large Sparse Positive Definite Systems. — M .: Mir, 1984. — 333 p.