CSR (Compressed Sparse Row)

O formato CSR (Compressed Sparse Row) é uma estrutura para representar matrizes esparsas de forma eficiente, armazenando apenas os elementos não nulos. Ele organiza os valores por linha, permitindo um acesso mais rápido e operações eficientes, como multiplicação de matrizes e resolução de sistemas lineares.

Contexto

O formato CSR é amplamente utilizado em computação científica, aprendizado de máquina e simulações numéricas, onde o trabalho com matrizes esparsas é comum. Diferente do formato COO, que armazena coordenadas explicitamente para cada valor, o CSR comprime essas informações, reduzindo ainda mais o uso de memória e melhorando o desempenho em operações que envolvem varredura por linhas.

Aplicabilidade

CSR é útil em aplicações que lidam com matrizes esparsas de grandes dimensões, como:

• Simulações de equações diferenciais parciais;
• Redes neurais profundas (em especial em camadas esparsas);
• Sistemas de recomendação que usam matriz de similaridade esparsa;
• Grafos e algoritmos relacionados a redes.

Exemplos Práticos

Vamos aprofundar e ampliar a seção Exemplos Práticos para explicar melhor como a CSR é formada, detalhando a construção dos arrays e como eles se relacionam com a matriz original.

Exemplos Práticos

Vamos considerar a seguinte matriz esparsa de 5×5 como exemplo:

[0, 0, 3, 0, 0]
[22, 0, 0, 0, 17]
[0, 5, 0, 0, 0]
[0, 0, 0, 8, 0]
[0, 0, 6, 0, 0]

Na matriz acima, a maioria dos elementos são zeros, e temos apenas seis elementos não nulos: 3, 22, 17, 5, 8 e 6. A estrutura CSR armazena esses elementos de forma compacta, utilizando três arrays principais: Data, Col_indices, e Row_ptr.

Passo a Passo para Construir a CSR

1. Data: Este array armazena os valores não nulos na ordem em que eles aparecem, varrendo a matriz linha por linha. Para a matriz acima, o array Data ficaria assim:

   Data = [3, 22, 17, 5, 8, 6]

2. Col_indices: Este array armazena as colunas correspondentes a cada valor não nulo presente no array Data. Assim, ele indica em qual coluna de cada linha esses valores estão localizados. A matriz acima possui os seguintes índices de coluna:

   Col_indices = [2, 0, 4, 1, 3, 2]

Explicação:

• O valor 3 está na linha 0, coluna 2.
• O valor 22 está na linha 1, coluna 0, e 17 está na mesma linha, coluna 4.
• O valor 5 está na linha 2, coluna 1.
• O valor 8 está na linha 3, coluna 3.
• O valor 6 está na linha 4, coluna 2.

1. Row_ptr: Este array armazena os índices que marcam o início e o fim dos elementos de cada linha no array Data. Ele possui n+1 elementos (onde n é o número de linhas da matriz), e a última posição sempre aponta para o total de elementos em Data. O array Row_ptr para nossa matriz seria:

   Row_ptr = [0, 1, 3, 4, 5, 6]

Explicação:

• Row_ptr[0] = 0: Indica que a primeira linha (linha 0) começa no índice 0 do array Data (onde está o valor 3).
• Row_ptr[1] = 1: A linha 1 começa no índice 1 do array Data (onde está o valor 22) e termina no índice 3 (exclusivo), que é onde começa a linha 2.
• Row_ptr[2] = 3: A linha 2 começa no índice 3 (onde está o valor 5).
• Row_ptr[3] = 4: A linha 3 começa no índice 4 (onde está o valor 8).
• Row_ptr[4] = 5: A linha 4 começa no índice 5 (onde está o valor 6).
• Row_ptr[5] = 6: O último valor indica o fim da matriz, correspondendo ao comprimento total do array Data (6 elementos).

Como a CSR Compacta a Informação

Com esses três arrays (Data, Col_indices e Row_ptr), conseguimos armazenar todos os elementos não nulos da matriz e suas posições de forma compacta. Assim, evitamos armazenar todos os zeros da matriz original, economizando memória e permitindo operações eficientes, especialmente quando é preciso acessar elementos por linha.

• Por exemplo, se quisermos acessar todos os elementos da linha 2 (índice 1):
• Olhamos para Row_ptr[1] e Row_ptr[2], que indicam que os valores da linha 2 estão entre os índices 1 e 3 do array Data.
• Consultamos Data[1] e Data[2], que são 22 e 17, e Col_indices[1] e Col_indices[2], que são 0 e 4, respectivamente.

Isso mostra como o CSR facilita o acesso e manipulação eficiente das linhas da matriz esparsa, aproveitando os três arrays de forma integrada.

Visualizando a CSR

Em resumo, a matriz esparsa acima é representada no formato CSR pelos seguintes arrays:

• Data: [3, 22, 17, 5, 8, 6]
• Col_indices: [2, 0, 4, 1, 3, 2]
• Row_ptr: [0, 1, 3, 4, 5, 6]

Com essa estrutura, conseguimos otimizar o armazenamento e acessar os valores de forma eficiente, especialmente em operações matemáticas que envolvem varredura de linhas.

Implementação em Python

Abaixo, apresento uma implementação simples de uma matriz esparsa usando o formato CSR (Compressed Sparse Row) em Python. Esta implementação mostra como armazenar os valores não nulos e suas respectivas posições de maneira compacta e como acessar elementos e visualizar a matriz.

class SparseMatrixCSR:
  def init(self, rows, cols):
      """
      Inicializa uma matriz esparsa no formato CSR.
      Parâmetros:
      rows (int): Número de linhas da matriz.
      cols (int): Número de colunas da matriz.
      """
      self.rows = rows
      self.cols = cols
      self.data = []         # Armazena os valores não nulos
      self.col_indices = []  # Armazena os índices das colunas dos valores
      self.row_ptr = [0]     # Armazena os índices que apontam para o início de cada linha em 'data'
      
  def add_value(self, row, col, value):
      """
      Adiciona um valor à matriz na posição especificada.
  
      Parâmetros:
      row (int): Índice da linha onde o valor será adicionado.
      col (int): Índice da coluna onde o valor será adicionado.
      value (float): Valor a ser inserido.
      """
      if value != 0:
          self.data.append(value)
          self.col_indices.append(col)
  
          # Atualiza o ponteiro de linha se for um novo valor na linha
          while len(self.row_ptr) <= row + 1:
              self.row_ptr.append(len(self.data))
  
  def get_value(self, row, col):
      """
      Retorna o valor na posição especificada da matriz.
  
      Parâmetros:
      row (int): Índice da linha a ser consultada.
      col (int): Índice da coluna a ser consultada.
  
      Retorna:
      float: O valor na posição especificada ou 0 se não houver valor.
      """
      start = self.row_ptr[row]
      end = self.row_ptr[row + 1]
  
      for i in range(start, end):
          if self.col_indices[i] == col:
              return self.data[i]
      return 0
  
  def display(self):
      """
      Exibe a matriz completa com todos os valores (incluindo zeros) na forma densa.
      """
      for i in range(self.rows):
          row_values = []
          for j in range(self.cols):
              row_values.append(str(self.get_value(i, j)))
          print(" ".join(row_values))

Explicação da Implementação

1. Classe SparseMatrixCSR:
   Esta classe implementa a estrutura CSR, contendo:
   • data: uma lista que armazena os valores não nulos da matriz.
   • col_indices: uma lista que armazena as colunas correspondentes a cada valor presente em data.
   • row_ptr: uma lista que armazena os índices que apontam para o início de cada linha em data.
2. Método add_value:
   Este método adiciona um valor à matriz na posição especificada (linha e coluna) se o valor for diferente de zero. Ele também atualiza a lista row_ptr conforme necessário para garantir que cada linha da matriz seja corretamente referenciada.
3. Método get_value:
   Este método retorna o valor na posição especificada (linha, coluna). Ele utiliza os índices em row_ptr para localizar a faixa de elementos em data que correspondem à linha consultada e, em seguida, busca pelo índice de coluna correspondente.
4. Método display:
   Este método exibe a matriz como se fosse uma matriz densa, iterando sobre todas as posições (incluindo zeros) para facilitar a visualização.

Testando o Código

No exemplo fornecido:

• A matriz é inicializada com 5 linhas e 5 colunas.
• Valores são adicionados em posições específicas, como (0, 2), (1, 0), e assim por diante.
• O método display imprime a matriz em formato denso, mostrando todos os elementos, inclusive os zeros.

Observações

• Eficiência: Esta implementação é eficiente para matrizes esparsas que são acessadas e manipuladas por linha, aproveitando a estrutura CSR para armazenar e buscar valores de forma compacta.
• Flexibilidade: Embora CSR seja eficiente para operações de linha, ele não é ideal para inserções ou modificações frequentes, pois a estrutura dos arrays precisa ser reorganizada.

Essa implementação oferece uma visão simples e prática de como o formato CSR funciona e como ele pode ser utilizado para representar matrizes esparsas de maneira compacta e eficiente.

Analogias e Metáforas

Imagine que você possui um prédio onde a maioria dos apartamentos está vazia, mas você quer listar apenas os ocupados e em qual andar estão. Em vez de listar todos os apartamentos, você anota os ocupados (valores) e em quais andares e números de porta estão (índices), registrando também onde começa e termina cada andar (ponteiros de linha). Assim, você economiza muito espaço!

Importância

O CSR é essencial para otimizar operações matemáticas em matrizes esparsas, permitindo:

• Acesso eficiente aos elementos por linha;
• Implementação rápida de operações de multiplicação de matrizes esparsas;
• Redução significativa de memória, especialmente para grandes matrizes.

Essas características fazem dele o formato preferido em muitas bibliotecas científicas, como SciPy e MATLAB.

Limitações e Críticas

• Modificação de valores: Inserir ou alterar valores na matriz é menos eficiente, pois pode requerer o realinhamento dos arrays de ponteiros.
• Varredura por coluna: O CSR é otimizado para varredura por linha, mas operações que dependem de colunas (como multiplicações por vetor coluna) não são tão eficientes quanto no formato CSC (Compressed Sparse Column).

Comparação com Conceitos Similares

• COO (Coordinate List): No formato COO, cada elemento é representado por suas coordenadas, tornando-o mais simples, mas menos eficiente para grandes matrizes e operações lineares frequentes.
• CSC (Compressed Sparse Column): Similar ao CSR, mas organiza os valores por colunas em vez de por linhas. É útil em algoritmos que requerem acesso rápido a elementos em colunas específicas.

Perguntas Frequentes (FAQs)

1. Quando devo usar CSR em vez de COO ou CSC?
Use CSR quando a matriz esparsa for estática (não houver modificações frequentes) e quando for necessário fazer operações otimizadas por linha, como multiplicação de matriz por vetor.

2. O CSR é eficiente para matrizes densas?
Não, CSR é otimizado para matrizes esparsas, onde a maioria dos elementos são zeros. Em matrizes densas, é mais prático utilizar representações que armazenem todos os valores diretamente.

3. Como é feita a conversão de COO para CSR?
A conversão envolve organizar os elementos por linha, ordenar os índices de coluna e preencher os ponteiros que marcam o início e o fim de cada linha.

Recursos Adicionais

• SciPy Documentation on Sparse Matrices
• Livro: “Numerical Linear Algebra” de Lloyd N. Trefethen e David Bau III