En matris lagras vanligtvis som en tvådimensionell matris. Varje post i matrisen representerar ett element ai,j i matrisen och nås genom de två indexen i och j. Konventionellt är i radindexet, numrerat uppifrån och ned, och j är kolumnindexet, numrerat från vänster till höger. För en m × n-matris är den mängd minne som krävs för att lagra matrisen i detta format proportionell mot m × n (om man bortser från det faktum att matrisens dimensioner också måste lagras).
För en sparsam matris kan man minska minnesbehovet avsevärt genom att endast lagra de poster som inte är noll. Beroende på antalet och fördelningen av de poster som inte är noll kan olika datastrukturer användas och ge stora minnesbesparingar jämfört med det grundläggande tillvägagångssättet. Motprestationen är att åtkomsten till de enskilda elementen blir mer komplex och ytterligare strukturer behövs för att kunna återskapa den ursprungliga matrisen otvetydigt.
Formaten kan delas in i två grupper:
- De som stödjer effektiv modifiering, t.ex. DOK (Dictionary of keys), LIL (List of lists), eller COO (Coordinate list). Dessa används vanligtvis för att konstruera matriserna.
- De som stöder effektiv åtkomst och matrisoperationer, t.ex. CSR (Compressed Sparse Row) eller CSC (Compressed Sparse Column).
Dictionary of keys (DOK)Redigera
DOK består av ett lexikon som mappar (rad, kolumn)-paren till värdet av elementen. Element som saknas i ordlistan antas vara noll. Formatet är bra för att stegvis konstruera en sparsam matris i slumpmässig ordning, men dåligt för att iterera över värden som inte är noll i lexikografisk ordning. Man konstruerar vanligtvis en matris i detta format och konverterar sedan till ett annat effektivare format för bearbetning.
List of lists (LIL)Edit
LIL lagrar en lista per rad, där varje post innehåller kolumnindex och värdet. Vanligtvis hålls dessa poster sorterade efter kolumnindex för snabbare sökning. Detta är ett annat format som är bra för inkrementell matriskonstruktion.
Koordinatlista (COO)Redigera
COO lagrar en lista med (rad, kolumn, värde) tupler. Helst sorteras posterna först efter radindex och sedan efter kolumnindex, för att förbättra slumpmässiga åtkomsttider. Detta är ett annat format som är bra för inkrementell matriskonstruktion.
Compressed sparse row (CSR, CRS eller Yale-format)Edit
Det komprimerade sparse row-formatet (CSR) eller komprimerad radlagring (CRS) eller Yale-formatet representerar en matris M genom tre (endimensionella) matriser, som innehåller värden som inte är noll, radernas utbredning och kolumnindex. Det liknar COO, men komprimerar radindexen, därav namnet. Detta format möjliggör snabb åtkomst till rader och multiplikationer mellan matris och vektor (Mx). CSR-formatet har använts åtminstone sedan mitten av 1960-talet och den första fullständiga beskrivningen dök upp 1967.
CSR-formatet lagrar en gles m × n-matris M i radform med hjälp av tre (endimensionella) matriser (V, COL_INDEX, ROW_INDEX). Låt NNZ beteckna antalet icke-noll poster i M. (Observera att nollbaserade index skall användas här.)
- Matriserna V och COL_INDEX har längden NNZ och innehåller de icke-noll värden respektive kolumnindexen för dessa värden.
- Matrisen ROW_INDEX har längden m + 1 och kodar indexet i V och COL_INDEX där den givna raden börjar. Det sista elementet är NNZ , dvs, det fiktiva indexet i V omedelbart efter det sista giltiga indexet NNZ – 1.
Till exempel matrisen
( 5 0 0 0 0 0 0 8 0 0 0 0 0 0 3 0 0 0 6 0 0 0 ) {\displaystyle {\begin{pmatrix}5&0&0&0&0\0&8&0&0&0&0\0&0&3&0\0\0&6&0&0&0\\\end{pmatrix}}}
är en 4 × 4-matris med 4 element som inte är noll, därav
V = COL_INDEX = ROW_INDEX =
om man antar ett nollindexerat språk.
För att extrahera en rad definierar vi först:
row_start = ROW_INDEX row_end = ROW_INDEX
Därefter tar vi skivor från V och COL_INDEX som börjar vid row_start och slutar vid row_end.
För att extrahera rad 1 (den andra raden) i denna matris ställer vi in row_start=1 och row_end=2. Sedan gör vi skivorna V = och COL_INDEX = . Vi vet nu att vi i rad 1 har ett element i kolumn 1 med värdet 8.
I detta fall innehåller CSR-representationen 13 poster, jämfört med 16 i den ursprungliga matrisen. CSR-formatet sparar på minnet endast när NNZ < (m (n – 1) – 1) / 2.Ett annat exempel, matrisen
( 10 20 0 0 0 0 0 0 30 0 0 40 0 0 0 0 0 0 50 60 70 0 0 0 0 0 0 0 0 80 ) {\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}}}
är en 4 × 6-matris (24 poster) med 8 element som inte är noll, så
V = COL_INDEX = ROW_INDEX =
Den totala matrisen sparas som 21 poster.
- ROW_INDEX delar upp matrisen V i rader:
(10, 20) (30, 40) (50, 60, 70) (80); - COL_INDEX delar upp värdena i kolumner:
(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).
Notera att i detta format är det första värdet av ROW_INDEX alltid noll och det sista alltid NNZ, så de är på sätt och vis överflödiga (även om NNZ inte skulle vara överflödigt i programmeringsspråk där matrisens längd måste lagras explicit). Icke desto mindre undviker detta behovet av att hantera ett undantagsfall vid beräkning av längden för varje rad, eftersom det garanterar att formeln ROW_INDEX – ROW_INDEX fungerar för alla rader i. Dessutom är minneskostnaden för denna redundanta lagring troligen obetydlig för en tillräckligt stor matris.
De (gamla och nya) Yale sparse matrix-formaten är exempel på CSR-ordningen. Det gamla Yale-formatet fungerar exakt som beskrivet ovan, med tre matriser; det nya formatet kombinerar ROW_INDEX och COL_INDEX till en enda matris och hanterar matrisens diagonal separat.
För logiska adjacensmatriser kan datamatrisen utelämnas, eftersom det räcker med att det finns en post i radmatrisen för att modellera en binär adjacensrelation.
Det är sannolikt känt som Yale-formatet eftersom det föreslogs i rapporten Yale Sparse Matrix Package från 1977 från Department of Computer Science vid Yale University.
Compressed sparse column (CSC eller CCS)Redigera
CSC liknar CSR med undantag för att värdena läses först kolumnvis, att ett radindex lagras för varje värde och att kolumnpekare lagras. CSC är till exempel (val, row_ind, col_ptr), där val är en matris med matrisens värden som inte är noll (uppifrån och ned och sedan från vänster till höger), row_ind är de radindex som motsvarar värdena och col_ptr är en lista med valindex där varje kolumn börjar. Namnet är baserat på det faktum att informationen om kolumnindex är komprimerad i förhållande till COO-formatet. Man använder vanligtvis ett annat format (LIL, DOK, COO) för konstruktion. Det här formatet är effektivt för aritmetiska operationer, kolumnskivning och matris-vektorprodukter. Se scipy.sparse.csc_matrix.Detta är det traditionella formatet för att ange en sparse-matris i MATLAB (via funktionen sparse).