Matriz esparsa

Em banda

As matrizes em banda formam uma classe especial de matriz esparsa onde os elementos não nulos estão concentrados perto da diagonal principal. Uma matriz em banda é caracterizada por suas larguras de banda inferior e superior, que se referem ao número de diagonais abaixo e acima (respectivamente) da diagonal principal entre as quais todas as entradas não nulas estão contidas.

Formalmente, a largura de banda inferior de uma matriz A é o menor número p tal que a entrada a_i,j se anula sempre que i > j + p. Similarmente, a largura de banda superior é o menor número p tal que a_i,j = 0 sempre que i < j − p (Golub & Van Loan 1996, §1.2.1). Por exemplo, uma matriz tridiagonal tem largura de banda inferior 1 e largura de banda superior 1. Como outro exemplo, a seguinte matriz esparsa tem largura de banda inferior e superior ambas iguais a 3. Observe que os zeros são representados com pontos para maior clareza. $${\displaystyle {\begin{bmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end{bmatrix}}}$$

Matrizes com larguras de banda superior e inferior razoavelmente pequenas são conhecidas como matrizes em banda e frequentemente permitem algoritmos mais simples do que matrizes esparsas gerais; ou pode-se às vezes aplicar algoritmos de matriz densa e ganhar eficiência simplesmente percorrendo um número reduzido de índices.

Ao rearranjar as linhas e colunas de uma matriz A, pode ser possível obter uma matriz A′ com uma largura de banda menor. Vários algoritmos são projetados para minimização de largura de banda.

Simétrica

Uma matriz esparsa simétrica surge como a matriz de adjacência de um grafo não direcionado; pode ser armazenada eficientemente como uma lista de adjacência.

Diagonal em blocos

Uma matriz diagonal em blocos consiste em submatrizes ao longo de seus blocos diagonais. Uma matriz diagonal em blocos A tem a forma $${\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1}&0&\cdots &0\\0&\mathbf {A} _{2}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}\end{bmatrix}},}$$

onde A_k é uma matriz quadrada para todo k = 1, ..., n.

Modelagem Linear e Amostragem Compressiva

A aplicação de matrizes esparsas permite resolver problemas de aquisição onde o número de medições obtidas (${\displaystyle p}$) é muito inferior ao número de variáveis totais do sistema (${\displaystyle n}$). Este cenário, comum em exames de Ressonância Magnética (RM), é modelado pelo sistema linear:

${\displaystyle y=Cx+\eta }$

Onde:

• ${\displaystyle y}$ representa o vetor de medições adquiridas no k-space;
• ${\displaystyle C}$ é a matriz de amostragem (ou matriz de medição);
• ${\displaystyle x}$ é a imagem a ser reconstruída;
• ${\displaystyle \eta }$ representa o ruído térmico e de medição.

Impacto Clínico e Radiologia Pediátrica

A exploração da esparsidade através da técnica de Compressed Sensing (CS) possibilita a reconstrução de imagens diagnósticas de alta fidelidade mesmo com subamostragem agressiva do espaço de frequências. Em pediatria, essa eficiência matemática traduz-se em exames até 6 vezes mais rápidos, reduzindo a necessidade de sedação e anestesia em crianças, além de mitigar riscos de eventos hipoxêmicos. Tal prática está alinhada ao princípio ALARA (As Low As Reasonably Achievable), que busca a máxima eficácia diagnóstica com a mínima exposição do paciente a riscos desnecessários.

Decomposição SVD e Bases Customizadas

Para problemas de Compressed Sensing, uma escolha apropriada de matriz de base é obtida pela decomposição em valores singulares (SVD). A base ${\displaystyle \Psi =U}$, derivada dos modos espaciais dos dados, permite projetar localizações otimizadas de sensores, minimizando o número de condição do sistema para torná-lo robusto ao ruído.

Otimização e Regularização

A recuperação da informação a partir de matrizes esparsas incompletas exige o uso de algoritmos de otimização que equilibram a fidelidade aos dados e a esparsidade da solução. O modelo padrão utiliza a minimização da norma ${\displaystyle L_{1}}$, que, ao contrário da norma ${\displaystyle L_{2}}$, promove a seleção de variáveis ao "zerar" coeficientes irrelevantes, facilitando a interpretação física do sistema.

A matriz esparsa é implementada através de um conjunto de listas ligadas que apontam para elementos diferentes de zero. De forma que os elementos que possuem valor zero não são armazenados.

Redução do preenchimento

O preenchimento de uma matriz são aquelas entradas que mudam de um zero inicial para um valor não nulo durante a execução de um algoritmo. Para reduzir os requisitos de memória e o número de operações aritméticas usadas durante um algoritmo, é útil minimizar o preenchimento trocando linhas e colunas na matriz. A decomposição de Cholesky simbólica pode ser usada para calcular o pior preenchimento possível antes de realizar a decomposição de Cholesky real.

Existem outros métodos além da decomposição de Cholesky em uso. Métodos de ortogonalização (como a fatoração QR) são comuns, por exemplo, ao resolver problemas por métodos de mínimos quadrados. Embora o preenchimento teórico ainda seja o mesmo, em termos práticos os "falsos não zeros" podem ser diferentes para diferentes métodos. E versões simbólicas desses algoritmos podem ser usadas da mesma forma que o Cholesky simbólico para calcular o preenchimento do pior caso.

Resolução de equações de matrizes esparsas

Existem métodos iterativos e diretos para resolver matrizes esparsas.

Métodos iterativos, como o método do gradiente conjugado e o GMRES, utilizam computações rápidas de produtos matriz-vetor ${\displaystyle Ax_{i}}$, onde a matriz ${\displaystyle A}$ é esparsa. O uso de precondicionadores pode acelerar significativamente a convergência de tais métodos iterativos.

Dicionário de chaves (DOK)

DOK consiste em um dicionário que mapeia pares (linha, coluna) para o valor dos elementos. Elementos que estão faltando no dicionário são considerados zero. O formato é bom para construir incrementalmente uma matriz esparsa em ordem aleatória, mas ruim para iterar sobre valores não nulos 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)

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

Lista de coordenadas (COO)

COO armazena uma lista de tuplas (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 bom para construção incremental de matriz.

Linha esparsa comprimida (CSR, CRS ou formato Yale)

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

O formato CSR armazena uma matriz esparsa m × n M na forma de linha usando três arrays (unidimensionais) (V, COL_INDEX, ROW_INDEX). Seja NNZ o número de entradas não nulas em M. (Observe que índices baseados em zero serão usados aqui.)

• Os arrays V e COL_INDEX têm comprimento NNZ e contêm os valores não nulos e os índices de coluna desses valores, respectivamente.
• COL_INDEX contém a coluna na qual a entrada correspondente V está localizada.
• O array ROW_INDEX tem comprimento m + 1 e codifica o índice em V e COL_INDEX onde a linha dada começa. Isso é equivalente a ROW_INDEX[j] codificando o número total de não nulos acima da linha j. 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 $${\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}}$$ é uma matriz 4 × 4 com 4 elementos não nulos, portanto

V         = [ 5 8 3 6 ]
COL_INDEX = [ 0 1 2 1 ]
ROW_INDEX = [ 0 1 2 3 4 ] 

assumindo uma linguagem com índice baseado em zero.

Para extrair uma linha, primeiro definimos:

row_start = ROW_INDEX[linha]
row_end   = ROW_INDEX[linha + 1]

Então pegamos fatias de V e COL_INDEX começando em row_start e terminando em row_end.

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

Neste caso, a representação CSR contém 13 entradas, comparado a 16 na matriz original. O formato CSR economiza memória apenas quando NNZ < (m (n − 1) − 1) / 2.

Outro exemplo, a matriz $${\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 nulos, portanto

V         = [ 10 20 30 40 50 60 70 80 ]
COL_INDEX = [  0  1  1  3  2  3  4  5 ]   
ROW_INDEX = [  0  2  4  7  8 ]

O todo é armazenado como 21 entradas: 8 em V, 8 em COL_INDEX, e 5 em ROW_INDEX.

• ROW_INDEX divide o array V em linhas: (10, 20) (30, 40) (50, 60, 70) (80), indicando o índice de V (e COL_INDEX) onde cada linha começa e termina;
• COL_INDEX alinha valores em colunas: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Observe que neste formato, o primeiro valor de ROW_INDEX é sempre zero e o último é sempre NNZ, então eles são de certa forma redundantes (embora em linguagens de programação onde o comprimento do array precisa ser explicitamente armazenado, NNZ não seria redundante). No entanto, isso evita a necessidade de lidar com um caso excepcional ao calcular o comprimento de cada linha, pois garante que a fórmula ROW_INDEX[i + 1] − ROW_INDEX[i] 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 esparsa Yale (antigo e novo) são instâncias do esquema CSR. O formato Yale antigo funciona exatamente como descrito acima, com três arrays; o novo formato combina ROW_INDEX e COL_INDEX em um único array e trata a diagonal da matriz separadamente.

Para matrizes de adjacência lógicas, o array de dados pode ser omitido, pois a existência de uma entrada no array de linha é suficiente para modelar uma relação de adjacência binária.

Provavelmente é conhecido como formato Yale porque foi proposto no relatório Yale Sparse Matrix Package de 1977 do Departamento de Ciência da Computação da Universidade de Yale.

Coluna esparsa comprimida (CSC ou CCS)

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