Gles matris
Från Rilpedia
En gles matris är inom matematiken en matris med mestadels nollor som element. Glesa matriser studeras speciellt inom numerisk analys. Stora diagonalmatriser är exempel på glesa matriser.
Stora glesa matriser uppkommer ofta vid lösningar av partiella differentialekvationer.
Lagring av glesa matriser
När man lagrar glesa matriser i datorer är det oftast väldigt ineffektivt att använda vanliga datastrukturer, istället utnyttjar man att matrisen består mestadels av nollor och lagrar bara de element som är nollskilda. Exempelvis, givet bild bestående av endast vita och svarta pixlar, där en av sorterna är mycket vanligare än den andra, är det effektivare att lagra positionerna för de sällsynta pixlarna av den ena färgen än att lagra hela matrisen.
Det naiva sättet att lagra en matris av format m×n är att använda en tvådimensionell array, så att minnesytan som behövs är m×n. Ett effektivare sätt är Yale Sparse Matrix Format, där en matris, B, lagras i form av tre endimensionella arrayer, kallade A, IA och JA. Arrayen A innehåller alla nollskilda element i B läst vänster till höger, uppifrån och ner. IA innehåller, på plats k, indexet, för A, till första nollskilda element i rad k. JA innehåller kolumnpositionerna för talen i A.
Om B är av format m×n och har x nollskilda element är alltså storleken på representationen: A: x, IA: m + 1, JA: x. Totalt:2x + m + 1, jämfört med m×n med vanliga arrayer.
Exempel
Givet matrisen:
Skulle representationen bli:
A = [ 1 2 3 9 1 4 ] IA = [ 1 3 5 7 ] JA = [ 1 2 2 3 2 3 ]
