Gles matris

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.

En stor gles matris som fås vid lösning av ett finit elementproblem. De svarta punkterna är nollskilda element.

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 ett tvådimensionellt fält, 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 fält, kallade A, IA och JA. Fältet 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 fält.

Exempel

Givet matrisen:

$B={\begin{pmatrix}1&2&0&0&\\0&3&9&0\\0&1&4&0\end{pmatrix}}$

Skulle representationen bli:

A  = [ 1 2 3 9 1 4 ]
IA = [ 1 3 5 7 ]
JA = [ 1 2 2 3 2 3 ]

Se även

• Bandmatris

Externa länkar

• Wikimedia Commons har media som rör Gles matris.
  Bilder & media