Uma matriz é tipicamente armazenada como uma matriz bidimensional. Cada entrada na matriz representa um elemento ai,j da matriz e é acessada pelos dois índices i e j. Convencionalmente, i é o índice da linha, numerada de cima para baixo, e j é o índice da coluna, numerada da esquerda para a direita. Para uma matriz m × n, a quantidade de memória necessária para armazenar a matriz neste formato é proporcional a m × n (desconsiderando o fato de que as dimensões da matriz também precisam ser armazenadas).

No caso de uma matriz esparsa, reduções substanciais da necessidade de memória podem ser realizadas armazenando apenas as entradas não zeradas. Dependendo do número e distribuição das entradas não-zero, diferentes estruturas de dados podem ser usadas e geram uma grande economia de memória quando comparadas com a abordagem básica. O trade-off é que o acesso aos elementos individuais torna-se mais complexo e estruturas adicionais são necessárias para poder recuperar a matriz original sem ambiguidades.

Formatos podem ser divididos em dois grupos:

• Os que suportam modificações eficientes, tais como DOK (Dicionário de chaves), LIL (Lista de listas), ou COO (Lista de coordenadas). Estes são tipicamente usados para construir as matrizes.
• Os que suportam operações eficientes de acesso e matriz, tais como CSR (Compressed Sparse Row) ou CSC (Compressed Sparse Column).

Dicionário de chaves (DOK)Editar

DOK consiste em um dicionário que mapeia (linha, coluna)-pares para o valor dos elementos. Os elementos que faltam no dicionário são considerados como sendo zero. O formato é bom para construir incrementalmente uma matriz esparsa em ordem aleatória, mas pobre para iterar sobre valores não-zero em ordem lexicográfica. Normalmente constrói-se uma matriz neste formato e depois converte-se para outro formato mais eficiente para processamento.

Lista de listas (LIL)Editar

LIL armazena uma lista por linha, com cada entrada contendo o índice da coluna e o valor. Tipicamente, estas entradas são mantidas ordenadas por índice de coluna para uma pesquisa mais rápida. Este é outro formato bom para construção de matriz incremental.

Lista de coordenadas (COO)Editar

COO armazena uma lista de tuplos (linha, coluna, valor). Idealmente, as entradas são ordenadas primeiro por índice de linha e depois por índice de coluna, para melhorar os tempos de acesso aleatório. Este é outro formato que é bom para construção de matriz incremental.

Linha esparsa comprimida (CSR, CRS ou formato Yale)Editar

O armazenamento de linha esparsa comprimida (CSR) ou armazenamento de linha comprimida (CRS) ou formato Yale representa uma matriz M por três matrizes (unidimensionais), que respectivamente contêm valores não zero, os extensões das linhas e os índices das colunas. É semelhante ao COO, mas comprime os índices de linha, daí o nome. Este formato permite acesso rápido a linhas e multiplicações matriz-vetor (Mx). O formato CSR está em uso desde pelo menos meados dos anos 60, com a primeira descrição completa aparecendo em 1967.

O formato CSR armazena uma matriz M esparsa m × n em forma de linha usando três matrizes (unidimensionais) (V, COL_INDEX, ROW_INDEX). Deixe NNZ denotar o número de entradas não zero em M. (Note que os índices baseados em zero devem ser usados aqui.)

• As matrizes V e COL_INDEX são de comprimento NNZ, e contêm os valores não zero e os índices das colunas desses valores respectivamente.

• A matriz ROW_INDEX é de comprimento m + 1 e codifica o índice em V e COL_INDEX onde a linha dada começa. O último elemento é NNZ , ou seja o índice fictício em V imediatamente após o último índice válido NNZ – 1.

Por exemplo, a matriz

( 5 0 0 0 0 8 0 0 0 0 3 0 0 0 6 0 0 ) {\i1}displaystyle {\i1}begin{\i}5&0&0&050>0\i}250>8&0&050>0&050>3&0\i}050&6&0&050>000\i}end{\i}}

é uma matriz 4 × 4 com 4 elementos não zero, portanto

 V = COL_INDEX = ROW_INDEX = 

assumindo uma linguagem indexada a zero.

Para extrair uma linha, primeiro definimos:

 row_start = ROW_INDEX row_end = ROW_INDEX

Então tiramos fatias de V e COL_INDEX começando na linha_início e terminando na linha_fim.

Para extrair a linha 1 (a segunda linha) desta matriz definimos row_start=1 e row_end=2. Depois fazemos as fatias V = e COL_INDEX = . Agora sabemos que na linha 1 temos um elemento na coluna 1 com o valor 8,

Neste caso a representação do CSR contém 13 entradas, em comparação com 16 na matriz original. O formato CSR salva na memória apenas quando NNZ < (m (n – 1) – 1) / 2.Outro exemplo, a matriz

( 10 20 0 0 0 0 0 0 30 0 0 0 0 0 0 50 60 70 0 0 0 0 0 0 0 80 ) {\i1}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}}}

é uma matriz 4 × 6 (24 entradas) com 8 elementos não zero, portanto

 V = COL_INDEX = ROW_INDEX = 

O todo é armazenado como 21 entradas.

• ROW_INDEX divide a matriz V em linhas: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX alinha os valores em colunas: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Note que neste formato, o primeiro valor do ROW_INDEX é sempre zero e o último é sempre NNZ, portanto eles são de alguma forma redundantes (embora em linguagens de programação onde o comprimento do array precisa ser explicitamente armazenado, NNZ não seria redundante). No entanto, isto evita a necessidade de lidar com um caso excepcional ao calcular o comprimento de cada linha, pois garante que a fórmula ROW_INDEX – ROW_INDEX funciona para qualquer linha i. Além disso, o custo de memória deste armazenamento redundante é provavelmente insignificante para uma matriz suficientemente grande.

Os formatos de matriz Yale (antigo e novo) são instâncias do esquema CSR. O antigo formato Yale funciona exatamente como descrito acima, com três matrizes; o novo formato combina ROW_INDEX e COL_INDEX em uma única matriz e trata a diagonal da matriz separadamente.

Para matrizes de adjacências lógicas, a matriz de dados pode ser omitida, pois a existência de uma entrada na matriz de linhas é suficiente para modelar uma relação de adjacências binárias.

É provavelmente conhecido como o formato Yale porque foi proposto no relatório de 1977 do Yale Sparse Matrix Package do Departamento de Informática da Universidade de Yale.

Coluna esparsa comprimida (CSC ou CCS)Editar

CSC é similar ao CSR exceto que os valores são lidos primeiro por coluna, um índice de linha é armazenado para cada valor, e ponteiros de coluna são armazenados. Por exemplo, CSC é (val, row_ind, col_ptr), onde val é uma matriz dos valores não zero da matriz (de cima para baixo, depois da esquerda para a direita); row_ind é os índices de linha correspondentes aos valores; e, col_ptr é a lista de índices de valor onde cada coluna começa. O nome é baseado no fato de que a informação do índice da coluna é comprimida em relação ao formato COO. Um normalmente usa outro formato (LIL, DOK, COO) para construção. Este formato é eficiente para operações aritméticas, corte de colunas e produtos vetoriais de matriz. Veja scipy.sparse.csc_matrix.Este é o formato tradicional para especificar uma matriz esparsa no MATLAB (através da função sparse).