right|thumb|Uma matriz esparsa obtida ao resolver um problema de elementos finitos em duas dimensões. Os elementos não nulos são mostrados em preto.
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. 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. 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, pois são comuns no campo do aprendizado de máquina. 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.
Casos especiais
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 é o menor número tal que a entrada se anula sempre que . Similarmente, a largura de banda superior é o menor número tal que sempre que . Por exemplo, uma matriz tridiagonal tem largura de banda inferior e largura de banda superior . 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.
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 , pode ser possível obter uma matriz com uma largura de banda menor. Vários algoritmos são projetados para minimização de largura de banda.
Diagonal 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 requer apenas entradas em memória.
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 tem a forma
onde é uma matriz quadrada para todo .
Fundamentação em Ciência de Dados e Medicina
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 é 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.
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 () é muito inferior ao número de variáveis totais do sistema (). Este cenário, comum em exames de Ressonância Magnética (RM), é modelado pelo sistema linear:
Onde: representa o vetor de medições adquiridas no k-space; é a matriz de amostragem (ou matriz de medição); é a imagem a ser reconstruída; 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 , 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 , que, ao contrário da norma , 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.
Uso
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 , onde a matriz é esparsa. O uso de precondicionadores pode acelerar significativamente a convergência de tais métodos iterativos.
Armazenamento
Uma matriz é tipicamente armazenada como um array bidimensional. Cada entrada no array representa um elemento da matriz e é acessada pelos dois índices e . Convencionalmente, é o índice da linha, numerado de cima para baixo, e é o índice da coluna, numerado da esquerda para a direita. Para uma matriz , a quantidade de memória necessária para armazenar a matriz neste formato é proporcional a (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).
Dicionário de chaves (DOK)
DOK consiste em um dicionário que mapeia pares 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.Veja scipy.sparse.dok_matrix
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.Veja scipy.sparse.lil_matrix
Lista de coordenadas (COO)
COO armazena uma lista de tuplas . 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.Veja scipy.sparse.coo_matrix
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 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 (). 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 na forma de linha usando três arrays (unidimensionais) . Seja o número de entradas não nulas em . (Observe que índices baseados em zero serão usados aqui.)
Os arrays e têm comprimento e contêm os valores não nulos e os índices de coluna desses valores, respectivamente. contém a coluna na qual a entrada correspondente está localizada. O array tem comprimento e codifica o índice em e onde a linha dada começa. Isso é equivalente a codificando o número total de não nulos acima da linha . O último elemento é , ou seja, o índice fictício em imediatamente após o último índice válido .
Por exemplo, a matriz
é uma matriz com 4 elementos não nulos, portanto V = [ 5 8 3 6 ]