Matriz esparsa e o uso CSR (Compressed Sparse Row)

Uma matriz esparsa em termos simples é uma matriz na qual os elementos existentes são em sua grande maioria representados por zero. Esse tipo de representação é comum na computação científica e machine learning, sendo aplicada em dados de redes sociais, engenharia e física.

A grande vantagem que poderíamos ter para esse tipo de matriz é que para algumas operações podemos desconsiderar os valores zerados e focar nos elementos diferentes de zero. Como exemplo, se quisermos realizar a multiplicação dessa matriz por um vetor (SpMV), podemos entender que para os valores zerados não faz sentido realizar essa operação computacional, resultando em uma melhora no custo.

Com isso surgem algumas estruturas de dados para melhorar a representação dessas matrizes para que a realização de operações se tornem mais eficientes. Para o caso que estamos descrevendo, vamos detalhar o CSR (Compressed Sparse Row).

Basicamente, essa forma de representação de matrizes se divide em três etapas:

• Vetor Data: para representar os elementos não nulos.
• Vetor Colunas: para representar as colunas nas quais os elementos do Vetor Data se encontram na matriz esparsa.
• Vetor Linhas: para representar as linhas nas quais os elementos do Vetor Data se encontram, marcando seu início e fim no vetor data.

Exemplo Prático

Vamos supor um exemplo de uma matriz esparsa A:

Com isso, vamos encontrar o valor de cada vetor anterior para entender como seria essa nova estrutura usando o CSR. Vou tentar escrever um código em C/C++ para representar essa estrutura de dados:

#pragma once
#include <vector>

class CSRMatrix {
private:
    std::vector<double> data;
    std::vector<int> col;
    std::vector<int> row;
    int nRows;
    int nColumns;

public:
    CSRMatrix(int l, int c, int nnz);
    void setValues(const std::vector<double> &newData,
                   const std::vector<int> &newCol,
                   const std::vector<int> &newLine);

    void multiplyByVector(const CSRMatrix &matrix, const std::vector<double> &x,
                          std::vector<double> &y);

    const std::vector<double> &getData() const { return data; };
    const std::vector<int> &getCol() const { return col; };
    const std::vector<int> &getRow() const { return row; };

    int getNumberOfRows() const { return nRows; }
    int getNumberOfColumns() const { return nColumns; }
};

No nosso código C/C++, podemos ver a representação dos vetores que formam a estrutura de dados CSR:

• Vetor Data: representado no código como data, ele irá conter no nosso exemplo:
  data = [1.5, 3.2, 4.0, 5.1, 2.1, 1.0].
• Vetor Coluna: representado no código como col, ele irá conter no nosso exemplo:
  col = [0, 3, 1, 4, 1, 3]. O mapeamento ocorre da seguinte forma:
  • 1.5 → Coluna 0
  • 3.2 → Coluna 3
  • 4.0 → Coluna 1
  • 5.1 → Coluna 4
  • 2.1 → Coluna 1
  • 1.0 → Coluna 3
• Vetor Linha: representado no código como row. Como a matriz tem 5 linhas, o ponteiro terá 5 + 1 = 6 elementos:
  • Linha 0: Começa no índice 0.
  • Linha 1: Começa no índice 2 (já que a linha 0 usou os índices 0 e 1).
  • Linha 2: Começa no índice 3 (a linha 1 só tinha o 4.0).
  • Linha 3: Começa no índice 4 (a linha 2 só tinha o 5.1).
  • Linha 4: Começa no índice 6 (a linha 3 tinha o 2.1 e 1.0).
  • Fim da Matriz: Aponta para o índice 6 (pois a linha 4 é vazia, logo o ponteiro não se move).
  Resultando em:
  row = [0, 2, 3, 4, 6, 6].

Com isso podemos reduzir bastante o número de zeros dentro da estrutura, fazendo com que o tamanho da alocação de memória necessária para armazenar toda a matriz seja muito menor.

Quando utilizar o modelo CSR?

Quando devo de fato considerar que a minha matriz é esparsa ou densa e quando devo aplicar o CSR? Na matemática pura diretamente não encontrei algo relevante, pois o zero em uma matriz de ordem l × c realiza apenas transformações lineares, e o zero não tem nenhum valor mágico algebricamente para se levar em consideração.

Porém, no ponto de vista computacional, o tamanho dessa matriz importa, pois pode representar uma grande economia de memória. Para isso, podemos fazer uma conta para descobrir a densidade e a esparsidade (o percentual de números zeros) da matriz. Com isso podemos realizar um cálculo em relação ao espaço que cada estrutura ocuparia e verificar o consumo aproveitado se optarmos pelo CSR.

Consideremos uma matriz de ordem m × n:

• m: número de linhas
• n: número de colunas
• N = m × n: total de elementos
• NNZ: elementos não nulos
• D = NNZ / N: densidade da matriz (0 ≤ D ≤ 1)
• S_val: tamanho em bytes do valor (ex: double = 8)
• S_idx: tamanho em bytes do índice (ex: int = 4)

A conta do consumo de memória da matriz densa (M_dense), que armazena todos os elementos independentemente de serem zero ou não, pode ser descrita como:

Agora, olhando para a estrutura de dados CSR, teríamos a seguinte alocação:

1. Vetor val: NNZ × S_val
2. Vetor col: NNZ × S_idx
3. Vetor row: (m + 1) × S_idx

Somando as três partes e fatorando o termo NNZ:

Para considerar que o CSR seja menos custoso em memória que a matriz densa, devemos verificar que M_csr < M_dense. Resolvendo essa inequação e isolando a densidade (D), chegamos em:

Para matrizes quadradas grandes podemos considerar que m = n e N = m². Olhando para o número de linhas, quando cresce infinitamente, o termo correspondente se aproxima de zero e podemos descartá-lo:

Chegando então no limite da densidade:

Considerando a nossa estrutura definida em C/C++ onde o val é um double (8 bytes) e col e row são int (4 bytes). Adicionando na equação:

Conclusão Computacional

Com isso podemos concluir que a densidade da matriz para esse tipo de armazenamento double e int na memória com a estrutura de dados será algo como: D < 66,67%. Ou seja, se a matriz contiver mais de 33,33% de zeros, a estrutura CSR já consome menos bytes na memória do que a representação densa clássica.

Logo, o uso do CSR se torna importante computacionalmente quando temos matrizes muito grandes com uma quantidade considerável de zeros. Vale lembrar que o percentual calculado de densidade não é fixo, pois a mudança dos tipos que são armazenados (modificando os bytes de S_val e S_idx) iria modificar os limites que calculamos.