Regra geral para armazenamento em matriz esparsa vs densa

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\%$

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.

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.

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.