Matriz esparsa - Sparse matrix

Exemplo de matriz esparsa ${\ displaystyle \ left ({\ begin {smallmatrix} 11 & 22 & 0 & 0 & 0 & 0 \\ 0 & 33 & 44 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 55 & 66 & 77 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 88 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 55 & 66 & 77 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 88 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & right \\\ end {smallmatrix} end {smallmatrix}$
A matriz esparsa acima contém apenas 9 elementos diferentes de zero, com 26 elementos zero. Sua dispersão é de 74% e sua densidade é de 26%.

Uma matriz esparsa obtida ao resolver um problema de elementos finitos em duas dimensões. Os elementos diferentes de zero são mostrados em preto.

Em análise numérica e computação científica , uma matriz esparsa ou matriz esparsa é uma matriz em que a maioria dos elementos é zero. Não há uma definição estrita com relação à proporção de elementos de valor zero para uma matriz se qualificar como esparsa, mas um critério comum é que o número de elementos diferentes de zero seja aproximadamente igual ao número de linhas ou colunas. Em contraste, se a maioria dos elementos for diferente de zero, a matriz é considerada densa . O número de elementos com valor zero dividido pelo número total de elementos (por exemplo, m × n para uma matriz m × n) é algumas vezes referido como a dispersão da matriz.

Conceitualmente, esparsidade corresponde a sistemas com poucas interações entre pares. Por exemplo, considere uma linha de bolas conectadas por molas de uma para a outra: este é um sistema esparso, pois apenas bolas adjacentes são acopladas. Em contraste, se a mesma linha de bolas tivesse molas conectando cada bola a todas as outras bolas, o sistema corresponderia a uma matriz densa. O conceito de dispersão é útil em áreas combinatórias e de aplicação, como teoria de redes e análise numérica , que normalmente têm uma baixa densidade de dados ou conexões significativas. Grandes matrizes esparsas freqüentemente 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 muitas vezes necessário usar algoritmos especializados e estruturas de dados 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. As operações que usam algoritmos e estruturas 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. Os dados esparsos são, por natureza, mais facilmente compactados e, portanto, requerem muito menos armazenamento . Algumas matrizes esparsas muito grandes são inviáveis de manipular usando algoritmos de matriz densa padrão.

Armazenando uma matriz esparsa

Uma matriz é normalmente armazenada como uma matriz bidimensional. Cada entrada na matriz 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, $ej$ é o índice da coluna, numerado da esquerda para a direita. Para uma matriz $m \times n$ , a quantidade de memória necessária para armazenar a matriz neste formato é proporcional a $m \times 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 de requisitos de memória podem ser realizadas armazenando apenas as entradas diferentes de zero. Dependendo do número e da distribuição das entradas diferentes de zero, diferentes estruturas de dados podem ser usadas e geram uma grande economia de memória quando comparadas à abordagem básica. A desvantagem é que acessar os elementos individuais se torna mais complexo e estruturas adicionais são necessárias para ser capaz de recuperar a matriz original sem ambigüidades.

Os formatos podem ser divididos em dois grupos:

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

Dicionário de chaves (DOK)

O DOK consiste em um dicionário que mapeia $(linha, coluna)$ - pares com o valor dos elementos. Os elementos que faltam no dicionário são considerados zero. O formato é bom para construir de forma incremental uma matriz esparsa em ordem aleatória, mas ruim para iterar sobre valores diferentes de zero em ordem lexicográfica. Normalmente, constrói-se uma matriz neste formato e depois converte 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 classificadas por índice de coluna para uma pesquisa mais rápida. Este é outro formato bom para construção de matriz incremental.

Lista de coordenadas (COO)

O COO armazena uma lista de tuplas $(linha, coluna, valor)$ . Idealmente, as entradas são classificadas primeiro por índice de linha e, em seguida, 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 compactada (formato CSR, CRS ou Yale)

O formato de linha esparsa compactada (CSR) ou armazenamento de linha compactada (CRS) ou Yale representa uma matriz $M$ por matrizes tridimensionais (unidimensionais), que contêm respectivamente valores diferentes de zero, as extensões das linhas e os índices das colunas. É semelhante ao COO, mas compacta os índices de linha, daí o nome. Este formato permite acesso rápido à linha e multiplicações de vetores de matriz ( $M x$ ). O formato CSR está em uso desde pelo menos meados da década de 1960, com a primeira descrição completa aparecendo em 1967.

O formato CSR armazena uma matriz esparsa $m \times n$ $M$ em forma de linha usando três matrizes $($ unidimensionais) $(V, COL_INDEX, ROW_INDEX)$ . Let $NNZ$ denotam o número de entradas diferentes de zero em $H$ . (Observe que os índices baseados em zero devem ser usados aqui.)

As matrizes $V$ e $COL_INDEX$ têm comprimento $NNZ$ e contêm os valores diferentes de zero e os índices de coluna desses valores, respectivamente.

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] que$ codifica o número total de valores diferentes de zero 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 \times 4$ com 4 elementos diferentes de zero, portanto

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

assumindo um idioma com índice zero.

Para extrair uma linha, primeiro definimos:

   row_start = ROW_INDEX[row]
   row_end   = ROW_INDEX[row + 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=1e row_end=2. Depois 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, em comparação com 16 na matriz original. O formato CSR é $salvo$ na 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 & 0 & 0 \\ 0 & 0 & 0 & 50 & 60 & 70 & 0 \\ 0 & 0 & 0 & 0 & 0 & 80 \\\ end {pmatrix}}}

é uma matriz $4 \times 6$ (24 entradas) com 8 elementos diferentes de zero, então

   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.

$ROW_INDEX$ divide a matriz $V$ em linhas: (10, 20) (30, 40) (50, 60, 70) (80);
$COL_INDEX$ valores alinha 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$ , portanto, eles são, em certo sentido, redundantes (embora em linguagens de programação em que o comprimento do array precise ser armazenado explicitamente, $NNZ$ não seria redundante). No entanto, isso evita a necessidade de tratar 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 desse armazenamento redundante é provavelmente insignificante para uma matriz suficientemente grande.

Os (antigos e novos) formatos de matriz esparsa de Yale são instâncias do esquema CSR. O antigo formato de 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 lógicas de adjacência , a matriz de dados pode ser omitida, pois a existência de uma entrada na matriz de linha é suficiente para modelar uma relação de adjacência binária.

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

Coluna esparsa compactada (CSC ou CCS)

CSC é semelhante a 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 de valores diferentes de zero (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 as informações do índice da coluna são compactadas em relação ao formato COO. Normalmente, usa-se outro formato (LIL, DOK, COO) para construção. Esse formato é eficiente para operações aritméticas, divisão de coluna e produtos de vetor de matriz. Veja scipy.sparse.csc_matrix . Este é o formato tradicional para especificar uma matriz esparsa no MATLAB (por meio da sparsefunção).

Estrutura especial

Unido

Um tipo especial importante de matrizes esparsas é a matriz de banda , definida a seguir. A menor largura de banda de uma matriz $A$ é o menor número $p$ tal que a entrada $a i, j$ desaparece sempre que $i > j + p$ . Da mesma forma, 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 iguais a 3. Observe que zeros são representados com pontos para maior clareza.

{\ displaystyle \ left ({\ begin {smallmatrix} 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 {smallmatrix}} \ right)}

Matrizes com larguras de banda superior e inferior razoavelmente pequenas são conhecidas como matrizes de banda e freqüentemente se prestam a algoritmos mais simples do que matrizes esparsas gerais; ou pode-se às vezes aplicar algoritmos de matriz densa e ganhar eficiência simplesmente fazendo um loop sobre um número reduzido de índices.

Ao reorganizar 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 minimizar a largura de banda .

Diagonal

Uma estrutura muito eficiente para um caso extremo de matrizes de banda, a matriz diagonal , é armazenar apenas as entradas na diagonal principal como uma matriz unidimensional , portanto, uma matriz diagonal $n \times n$ requer apenas $n$ entradas.

Simétrico

Uma matriz esparsa simétrica surge como a matriz de adjacência de um grafo não direcionado ; ele pode ser armazenado de forma eficiente como uma lista de adjacências .

Bloco diagonal

Uma matriz de bloco diagonal consiste em submatrizes ao longo de seus blocos diagonais. Uma matriz de bloco diagonal- 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 .

Reduzindo preenchimento

O preenchimento de uma matriz são as entradas que mudam de um valor inicial zero para um valor diferente de zero 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 fazer a decomposição de Cholesky real .

Existem outros métodos em uso além da decomposição de Cholesky . Métodos de ortogonalização (como 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 métodos diferentes. E as versões simbólicas desses algoritmos podem ser usadas da mesma maneira que o Cholesky simbólico para calcular o preenchimento do pior caso.

Resolvendo equações de matriz esparsa

Ambos os iterativos existem métodos e diretas para a resolução de matriz esparsa.

Os métodos iterativos, como o método do gradiente conjugado e GMRES, utilizam cálculos rápidos de produtos de matriz-vetor , em que a matriz é esparsa. O uso de pré-condicionadores pode acelerar significativamente a convergência de tais métodos iterativos. ${\ displaystyle Ax_ {i}}$ ${\ displaystyle A}$

Programas

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

SuiteSparse , um conjunto de algoritmos de matriz esparsa, voltado para a solução direta de sistemas lineares esparsos.
PETSc , uma grande biblioteca C, contendo muitos solvers de matriz 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 matriz esparsa. No entanto, nenhum deles é paralelizado .
MUMPS ( MU ltifrontal M assively P arallel sparse direct S olver), escrito em Fortran90, é um solver frontal .
DUNE , uma biblioteca de elementos finitos que também possui uma sub-biblioteca para sistemas lineares esparsos e sua solução.
PaStix .
SuperLU .
Armadillo fornece um invólucro C ++ amigável para BLAS e LAPACK.
SciPy fornece suporte para vários formatos de matriz esparsa, álgebra linear e solucionadores.
Pacote SPArse Matrix (spam) R e Python para matrizes esparsas.
Wolfram Language Tools para lidar com matrizes esparsas
ALGLIB é uma biblioteca C ++ e C # com suporte para álgebra linear esparso
Biblioteca ARPACK Fortran 77 para diagonalização e manipulação de matrizes esparsas, usando o algoritmo de Arnoldi
Referência SPARSE (antigo) Pacote NIST para diagonalização de matriz esparsa (real ou complexa)
Biblioteca SLEPc para solução de sistemas lineares de grande escala e matrizes esparsas
Sympiler , um gerador de código específico de domínio e biblioteca para resolver sistemas lineares e problemas de programação quadrática.
Scikit-learn Um pacote Python para análise de dados, incluindo matrizes esparsas.

História

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

Veja também

Notas

Referências

Golub, Gene H .; Van Loan, Charles F. (1996). Matrix Computations (3ª ed.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
Stoer, Josef; Bulirsch, Roland (2002). Introdução à Análise Numérica (3ª ed.). Berlim, Nova York: Springer-Verlag . ISBN 978-0-387-95452-3.
Tewarson, Reginald P. (maio de 1973). Matrizes esparsas (parte da série Mathematics in Science & Engineering) . Academic Press Inc. (Este livro, de um professor da Universidade Estadual de Nova York em Stony Book, foi o primeiro livro dedicado exclusivamente a Matrizes esparsas. Cursos de pós-graduação usando isso como livro-texto foram oferecidos naquela universidade no início dos anos 1980).
Bank, Randolph E .; Douglas, Craig C. "Sparse Matrix Multiplication Package" (PDF) .
Pissanetzky, Sergio (1984). Tecnologia de matriz esparsa . Academic Press.
Snay, Richard A. (1976). "Reduzindo o perfil de matrizes simétricas esparsas". Bulletin Géodésique . 50 (4): 341–352. Bibcode : 1976BGeod..50..341S . doi : 10.1007 / BF02521587 . hdl : 2027 / uc1.31210024848523 . S2CID 123079384 . Também NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

Leitura adicional

Gibbs, Norman E .; Poole, William G .; Stockmeyer, Paul K. (1976). "Uma comparação de vários algoritmos de redução de largura de banda e perfil" . Transações ACM em software matemático . 2 (4): 322–330. doi : 10.1145 / 355705.355707 . S2CID 14494429 .
Gilbert, John R .; Moler, Cleve; Schreiber, Robert (1992). "Matrizes esparsas em MATLAB: Design e implementação" . SIAM Journal on Matrix Analysis and Applications . 13 (1): 333–356. CiteSeerX 10.1.1.470.1054 . doi : 10.1137 / 0613024 .
Pesquisa de algoritmos de matriz esparsa na Texas A&M University.
SuiteSparse Matrix Collection
Projeto PEQUENO Um projeto financiado pela UE em modelos esparsos, algoritmos e aprendizagem de dicionário para dados em grande escala.

^ Saad, Yousef (2003). Métodos iterativos para sistemas lineares esparsos . SIAM.

[12] Saad, Yousef (2003). Métodos iterativos para sistemas lineares esparsos . SIAM.

Languages

In other projects