Gles matris

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 december 2021; kontroller kräver 4 redigeringar .

En gles matris är en matris med mestadels noll element. Annars, om de flesta av matriselementen är icke-noll, anses matrisen vara tät .

Bland experter finns det ingen enhet i att bestämma exakt hur många icke-nollelement som gör en matris gles. Olika författare erbjuder olika alternativ. För en matris av ordningen n, antalet element som inte är noll [1] :

är O(n) . En sådan definition är endast lämplig för den teoretiska analysen av de asymptotiska egenskaperna hos matrisalgoritmer;
i varje rad inte överstiger 10 i ett typiskt fall;
begränsat var . $n^{{1+\gamma }}$ $\gamma<1$
är sådan att det är meningsfullt för en given algoritm och datorsystem att dra nytta av närvaron av nollor i den [1] .

Enorma glesa matriser uppstår ofta när man löser problem som partiella differentialekvationer .

När man lagrar och konverterar glesa matriser i en dator är det användbart, och ofta nödvändigt, att använda speciella algoritmer och datastrukturer som tar hänsyn till den glesa matrisstrukturen. Operationer och algoritmer som används för att arbeta med vanliga, täta matriser, i förhållande till stora glesa matriser, är relativt långsamma och kräver betydande mängder minne. Men glesa matriser kan enkelt komprimeras genom att bara skriva deras icke-noll-element, vilket minskar datorns minneskrav .

Presentation

Det finns flera sätt att lagra (representera) glesa matriser, som skiljer sig åt:

bekvämligheten med att ändra matrisstrukturen (indirekt adressering används aktivt) - det här är strukturer i form av listor och ordböcker.
hastigheten för åtkomst till element och möjlig optimering av matrisberäkningar (täta blockmatriser används oftare, vilket ökar lokaliteten för minnesåtkomst).

En Dictionary of Keys (DOK - Dictionary of Keys) är byggd som en ordbok, där nyckeln är ett par ( rad, kolumn ), och värdet är matriselementet som motsvarar raden och kolumnen.

En lista med listor (LIL - List of Lists) är byggd som en lista med strängar, där en sträng är en lista med noder av formen ( kolumn, värde ).

Koordinatlistan (COO - Koordinatlista) är en lista med element i formuläret (rad, kolumn, värde).

Compressed Row Storage (CSR - Compressed Sparse Row, CRS - Compressed Row Storage, Yale-format)

Vi representerar den ursprungliga matrisen som innehåller icke-nollvärden som tre arrayer: ${\displaystyle M^{n\times m))$ ${\displaystyle N_{NZ))$

matris av värden - en matris med storlek , som lagrar värden som inte är noll tagna i rad från den första icke-tomma raden, sedan värdena från nästa icke-tomma rad, etc. ${\displaystyle N_{NZ))$
array av kolumnindex är en array av storlek och lagrar kolumnnumren som motsvarar element från värdematrisen. ${\displaystyle N_{NZ))$
radindexeringsmatris - en matris med storlek (antal rader + 1), för indexet lagrar den antalet element som inte är noll i rader från första till rad inklusive, det är värt att notera att det sista elementet i radindexeringen array är samma som , och den första är alltid lika med . $n+1$ $i$ $i-1$ ${\displaystyle N_{NZ))$ $0$

Exempel:

Låt då $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 } -- lagra 0 först som låselement

Låt då $M={\begin{pmatrix}1&2&0&3\\0&0&4&0\\0&1&0&11\end{pmatrix}}$

array_of_values = { 1 , 2 , 3 , 4 , 1 , 11 } array of column_indexes = { 0 , 1 , 3 , 2 , 1 , 3 } array_of_index_rows = { 0 , 3 , 4 , 0 first } _ som ett låselement

För att återställa den ursprungliga matrisen måste du ta något värde i den första matrisen och motsvarande index , sedan kolumnnumret och radnumret hittas som det minsta , för vilket detta är praktiskt, till exempel när matrisen multiplikation med en tät vektor $v$ $i_{v}:Arr_{values}[i_{v}]=v$ $n_{c}=Arr_{cols}[i_{v}]$ $n_{r}$ $n_{r}$ $Arr_{rader}[n_{r}+1]\geq i_{v}+1$

void smdv ( const crsm * A , double * b , const double * v ) // b += Av { // crsm är en struktur {int n, int m, int nnz, double aval[], double aicol[], double airow[]}; för ( int rad = 0 ; rad < n ; ++ rad ) för ( int i = A -> airow [ rad ]; i < A -> airow [ rad + 1 ]; ++ i ) b [ rad ] += A -> aval [ i ] * v [ A -> aicol [ i ]]; }

Komprimerad kolumnlagring (CSС - Compressed Sparse Column, CСS - Compressed Column Storage)

Samma som CRS, bara rader och kolumner ändrar roller - vi lagrar värden efter kolumner, vi kan bestämma raden från den andra matrisen, efter beräkningar med den tredje matrisen - vi känner igen kolumnerna.

Programvarubibliotek

För beräkningar med glesa matriser har ett antal bibliotek skapats för olika programmeringsspråk, bland annat:

SparseLib++ ( C++ ) [2]
uBLAS (C++, del av Boost ) [3]
SPARSPAK ( Fortran ) [4]
CSarse ( C ) [5]
Gles modul från SciPy ( Python ) biblioteket [6] [7] .

Anteckningar

↑ 1 2 Pissanecki, 1988 , Inledning.
↑ SparseLib++ . Datum för åtkomst: 1 augusti 2012. Arkiverad från originalet 21 september 2012. (obestämd)
↑ uBLAS/Boost . Hämtad 1 augusti 2012. Arkiverad från original 4 augusti 2012. (obestämd)
↑ Alan George, Esmond Ng. En kort beskrivning av SPARSPAK Waterloo sparse linear equations package // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 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, september 2006 . Datum för åtkomst: 1 augusti 2012. Arkiverad från originalet den 29 juli 2012. (obestämd)
↑ Sparse matriser (scipy.sparse), SciPy Reference Guide . Hämtad 22 april 2017. Arkiverad från originalet 23 april 2017. (obestämd)
↑ Gles linjär algebra (scipy.sparse.linalg), SciPy Referensguide . Hämtad 22 april 2017. Arkiverad från originalet 23 april 2017. (obestämd)

Litteratur

Reginald P Tewarson. Glesa matriser. - Academic Press, 1973. - 160 sid. — ISBN 0126856508 . översättning: Tuarson R. Gles matriser = Gles matriser. - M . : Mir, 1977. - 191 sid.
Pissanecki S. Sparse Matrix Technology = Sparse Matrix Technology. — M .: Mir, 1988. — 410 sid. - ISBN 5-03-000960-4 .
George A., Liu J. Datorlösning av stora glesa positiva bestämda system. — M .: Mir, 1984. — 333 sid.