Matriz esparsa 📖 Wikipedia

Exemplo de matriz esparsa ${\displaystyle \left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)}$

A matriz esparsa acima contém apenas 9 elementos não nulos, com 26 elementos nulos. Sua esparsidade é 74%, e sua densidade é 26%.

Em análise numérica e computação científica, uma matriz esparsa ou arranjo esparso é uma matriz na qual a maioria dos elementos é zero.^[1] Não há uma definição rigorosa quanto à proporção de elementos zero para que uma matriz seja qualificada como esparsa, mas um critério comum é que o número de elementos não nulos é aproximadamente igual ao número de linhas ou colunas. Por outro lado, se a maioria dos elementos é não nula, a matriz é considerada densa.^[1] O número de elementos zero dividido pelo número total de elementos (por exemplo, m × n para uma matriz m × n) é às vezes chamado de esparsidade da matriz.

Conceitualmente, a esparsidade corresponde a sistemas com poucas interações aos pares. Por exemplo, considere uma linha de bolas conectadas por molas de uma para a próxima: este é um sistema esparso, pois apenas bolas adjacentes são acopladas. Por outro lado, se a mesma linha de bolas tivesse molas conectando cada bola a todas as outras, o sistema corresponderia a uma matriz densa. O conceito de esparsidade é útil em combinatória e áreas de aplicação como teoria das redes e análise numérica, que tipicamente têm uma baixa densidade de dados ou conexões significativas. Grandes matrizes esparsas frequentemente aparecem em aplicações científicas ou de engenharia ao resolver equações diferenciais parciais.

Ao armazenar e manipular matrizes esparsas em um computador, é benéfico e frequentemente necessário usar algoritmos e estruturas de dados especializadas que aproveitam a estrutura esparsa da matriz. Computadores especializados foram feitos para matrizes esparsas,^[2] pois são comuns no campo do aprendizado de máquina.^[3] Operações que usam estruturas e algoritmos de matriz densa padrão são lentas e ineficientes quando aplicadas a grandes matrizes esparsas, pois o processamento e a memória são desperdiçados nos zeros. Dados esparsos são por natureza mais facilmente comprimidos e, portanto, requerem significativamente menos armazenamento. Algumas matrizes esparsas muito grandes são inviáveis de manipular usando algoritmos de matriz densa padrão.

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.

Uma matriz diagonal é o caso extremo de uma matriz em banda, com largura de banda superior e inferior zero. Uma matriz diagonal pode ser armazenada eficientemente armazenando apenas as entradas da diagonal principal como um array unidimensional, de modo que uma matriz diagonal n × n requer apenas n entradas em memória.

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.

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.

No contexto da ciência de dados e do processamento digital de sinais, a esparsidade é uma propriedade que indica que um sinal ou imagem pode ser representado por um número reduzido de coeficientes não nulos em uma base transformara específica (como Wavelet ou Transformada de Fourier). Matematicamente, se uma matriz de dados ${\displaystyle x}$ é esparsa, a maior parte de sua informação útil está concentrada em poucos elementos, permitindo a compressão e a reconstrução eficiente do sinal original.

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.

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.^[4][5]

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.

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.

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.

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.

Uma matriz é tipicamente armazenada como um array bidimensional. Cada entrada no array representa um elemento a_i,j da matriz e é acessada pelos dois índices i e j. Convencionalmente, i é o índice da linha, numerado de cima para baixo, e j é o índice da coluna, numerado 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 nos requisitos de memória podem ser realizadas armazenando apenas as entradas não nulas. Dependendo do número e distribuição das entradas não nulas, diferentes estruturas de dados podem ser usadas e resultar em enormes economias de memória quando comparadas à abordagem básica. A contrapartida é que acessar os elementos individuais se torna mais complexo e estruturas adicionais são necessárias para poder recuperar a matriz original de forma inequívoca.

Os formatos podem ser divididos em dois grupos:

• Aqueles que suportam modificação eficiente, como DOK (Dictionary of keys), LIL (List of lists), ou COO (Coordinate list). Estes são tipicamente usados para construir as matrizes.
• Aqueles que suportam acesso eficiente e operações matriciais, como CSR (Compressed Sparse Row) ou CSC (Compressed Sparse Column).

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.^[6]

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.^[7]

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.^[8]

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.^[9]

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.^[10]

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.^[11]

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.^[12]

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).

Muitas bibliotecas de software suportam matrizes esparsas e fornecem solucionadores para equações de matrizes esparsas. As seguintes são de código aberto:

• PETSc, uma grande biblioteca C, contendo muitos solucionadores de matrizes diferentes para uma variedade de formatos de armazenamento de matriz.
• Trilinos, uma grande biblioteca C++, com sub-bibliotecas dedicadas ao armazenamento de matrizes densas e esparsas e solução de sistemas lineares correspondentes.
• Eigen3 é uma biblioteca C++ que contém vários solucionadores de matrizes esparsas. No entanto, nenhum deles é paralelizado.
• MUMPS (MUltifrontal Massively Parallel sparse direct Solver), escrito em Fortran90, é um solucionador frontal.
• deal.II, uma biblioteca de elementos finitos que também tem uma sub-biblioteca para sistemas lineares esparsos e sua solução.
• DUNE, outra biblioteca de elementos finitos que também tem uma sub-biblioteca para sistemas lineares esparsos e sua solução.
• Armadillo fornece um wrapper C++ amigável para BLAS e LAPACK.
• SciPy fornece suporte para vários formatos de matriz esparsa, álgebra linear e solucionadores.
• ALGLIB é uma biblioteca C++ e C# com suporte a álgebra linear esparsa
• ARPACK biblioteca Fortran 77 para diagonalização e manipulação de matrizes esparsas, usando o algoritmo de Arnoldi
• SLEPc Biblioteca para solução de sistemas lineares de grande escala e matrizes esparsas
• scikit-learn, uma biblioteca Python para aprendizado de máquina, fornece suporte para matrizes esparsas e solucionadores
• SparseArrays é uma biblioteca padrão do Julia.
• PSBLAS, kit de ferramentas de software para resolver sistemas lineares esparsos suportando múltiplos formatos também em GPU.

O termo matriz esparsa foi possivelmente cunhado por Harry Markowitz que iniciou alguns trabalhos pioneiros, mas depois deixou o campo.^[13]