Regra geral para armazenamento em matriz esparsa vs densa

9

Suponha que eu conheça a esparsidade esperada de uma matriz (ou seja, o número de não-zeros / número total possível de não-zeros). Existe uma regra prática (talvez aproximada) para decidir se o armazenamento de matriz esparsa deve ser usado (especificamente, armazenamento de linhas compactadas) versus armazenado como uma matriz densa?

  1. A velocidade é mais importante na minha aplicação do que a memória. Mas, por curiosidade geral, estou interessado em respostas da perspectiva da velocidade e da memória.
  2. Depois de gerar a matriz, só aplico operações de adição e multiplicação.
  3. Eu só consegui encontrar respostas qualitativas, por exemplo, esta e esta pergunta, mas estou procurando algo como

... se a dispersão for superior a aproximadamente , use armazenamento denso.x%

EM_IE
fonte

Respostas:

8

Todas as operações da matriz são ligadas à memória (e não à computação) nos processadores atuais. Então, basicamente, você deve perguntar qual formato armazena menos bytes. É fácil calcular:

  • Para uma matriz completa, você armazena 8 bytes (um duplo) por entrada
  • Para uma matriz esparsa, você armazena 12 bytes por entrada (um dobro para o valor e um inteiro para o índice da coluna da entrada).

Em outras palavras, se sua escassez for inferior a 67% - ou seja, para quase qualquer matriz que qualquer pessoa razoável chamaria de esparsa -, o formato da matriz esparsa não apenas produzirá melhor uso de memória, mas também melhor tempo de computação.

Wolfgang Bangerth
fonte
Gostaria de saber por que alguém rebaixou esta resposta. É qualitativo, quantitativo e fornece uma boa regra de ouro. Se eu pudesse votar duas vezes, eu faria.
Charles
3
Você precisará de um pouco mais de armazenamento que isso - você também deve acompanhar as linhas. Um bit por linha é suficiente.
Brian Borchers
3
A multiplicação matriz-matriz de matrizes densas é um local em que você obtém reutilização de cache suficiente para chegar muito perto do pico de FLOPS. Concordo que a multiplicação do vetor de matriz terá uma largura de banda de memória limitada.
precisa saber é o seguinte
1
67%, na verdade, está muito longe do ponto em que os cálculos se beneficiariam da escarsidade. A multiplicação densa de vetores de matrizes pode se beneficiar significativamente do cache. (Você precisa de acesso muito irregular à memória para multiplicação esparsa de vetores matriciais.) Se se trata de resolver sistemas lineares com um solucionador direto, as pessoas às vezes dizem que uma matriz é esparsa se tiver menos de 0,1% de valores diferentes de zero. Mas, na prática, a conectividade real das entradas da matriz é muito mais importante que o número de não-zeros.
Henrik Schumacher
1
@WolfgangBangerth: Sua definição de esparsa ("Esparsa" significa que o número de entradas diferentes de zero por linha é independente do tamanho de um conjunto de matrizes que crescem cada vez maiores.), Difere bastante da definição de trabalho informal de JH Wilkinson. : "qualquer matriz com zeros suficientes que valha a pena aproveitá-los", o que é frequentemente citado na literatura. Eu prefiro a definição de Wilkinson.
wim
11

Pelo que vale a pena, para matrizes esparsas aleatórias de tamanho 10.000 por 10.000 vs. matrizes densas do mesmo tamanho, na minha estação de trabalho Xeon usando MATLAB e Intel MKL como o BLAS, a multiplicação de vetor de matriz esparsa foi mais rápida para densidades de 15% ou menos. Em 67% (como proposto por outra resposta ), a densa multiplicação matriz-vetor foi cerca de três vezes mais rápida.

Brian Borchers
fonte
Interessante, obrigado. Algumas de minhas matrizes são de 30 a 40% esparsas (inconvenientemente entre as estimativas de 15% e 67%); portanto, provavelmente eu deveria realizar testes semelhantes aos seus (para as operações em que estou interessado) para ver se a memória as vantagens valem a desaceleração.
EM_IE 15/09
3
Depende muito do hardware e software que você está usando. Minha máquina possui memória de canal quádruplo, portanto, possui mais largura de banda de memória do que um sistema típico de canal duplo. MKL é um BLAS muito bom e as estruturas de dados de matriz esparsa do MATLAB podem não ser perfeitamente otimizadas para isso.
Brian Borchers
1
Um problema com o armazenamento de linha compactado (ou armazenamento de coluna compactado) é que as entradas geralmente são armazenadas em uma área diferente na memória das informações do índice. Essa falta de localidade pode prejudicar o desempenho. Em comparação, no armazenamento de matriz densa convencional (por linhas (C) ou colunas (Fortran)), é possível carregar entradas da matriz consecutivamente da memória de uma maneira mais eficiente.
Brian Borchers
1
Nos últimos anos, houve pesquisas sobre novos formatos de armazenamento para matrizes esparsas, que permitem desempenho aprimorado para multiplicação esparsa de vetores matriciais em processadores mutlcore, máquinas com instruções SIMD e GPUs. Veja, por exemplo: pdfs.semanticscholar.org/041b/…
Brian Borchers
5

Mesmo que uma matriz seja muito esparsa, seu produto da matriz consigo mesmo pode ser denso. Pegue, por exemplo, uma matriz diagonal e preencha sua primeira linha e coluna com entradas diferentes de zero; seu produto em si será completamente denso. Essa matriz pode surgir, por exemplo, como gráfico Laplaciano de um gráfico no qual existe um vértice que está conectado a todos os outros vértices. Na prática, basta se houver poucos vértices com conectividade bastante alta ao restante da rede. Para a multiplicação de vetores de matriz, esse fenômeno é menos relevante, embora possa levar a desequilíbrios ao tentar paralelizar a multiplicação de vetores de matriz.

O que quero destacar: Depende realmente do padrão de escarsidade e do que você deseja fazer com a matriz. Portanto, a melhor definição de uma matriz esparsa que eu possa criar (que é bastante inútil ao mesmo tempo) é a seguinte:

Uma matriz é escassa se for vantajoso armazenar apenas seus valores diferentes de zero e suas posições e investir a sobrecarga adicional resultante do gerenciamento da estrutura de dados resultante.

A lição a aprender: Depende realmente do que você quer fazer com ele , qual algoritmo você usa e (como outros já apontaram) que hardware e software você usa se uma matriz é escassa ou não (leia-se como: se você deve usar uma estrutura de dados de matriz esparsa ou densa). Não pode haver uma regra puramente baseada em porcentagem se não se trata apenas de armazenar dados ou multiplicar vetores matriciais. A melhor maneira de descobrir se suas matrizes são esparsas é apenas tentar e comparar com métodos de matriz densa.

Henrik Schumacher
fonte
1
O famoso JH Wilkinson definiu uma matriz esparsa como: "qualquer matriz com zeros suficientes que vale a pena tirar proveito deles". Exatamente essa definição tem sido citada por outros com frequência. No entanto, sua definição também é bastante adequada.
wim
1
Agradável. Foi exatamente essa a definição que tentei imitar, mas não consegui lembrar a fonte.
Henrik Schumacher