Introdução às Matriezs Esparsas

Em computação científica e aprendizado de máquina, é comum lidar com estruturas matriciais de grandes dimensões. Quando a maioria dos elementos é zero, utilizar arrays densos tradicionais consome memória desnecessária e degrada o desempenho computacional. Matrizes esparsas resolvem esse problema armazenando apenas os valores diferentes de zero e suas respectivas coordenadas, reduzindo drasticamente a pegada de memória e acelerando operações algébricas.

O módulo scipy.sparse oferece sete implementações principais, cada uma otimizada para padrões de acesso e construção específicos. A escolha do formato adequado depende diretamente do fluxo de trabalho: construção incremental, fatiamento, operações aritméticas ou armazenamento em disco.

Atributos e Métodos Compartilhados

Independentemente do formato escolhido, todas as classes herdam de uma base comum e expõem propriedades padronizadas:

import scipy.sparse as sp

# Atributos universais
mat.shape          # Dimensões (linhas, colunas)
mat.dtype          # Tipo numérico dos elementos
mat.nnz            # Quantidade de valores não nulos
mat.data           # Array 1D contendo os valores armazenados

# Conversões de formato
mat.toarray()      # Retorna numpy.ndarray denso
mat.tocsr()        # Converte para CSR
mat.tocsc()        # Converte para CSC
mat.tocoo()        # Converte para COO
mat.asformat('lil')# Conversão genérica por string

# Verificação e operações básicas
sp.issparse(mat)   # Retorna True se for esparsa
mat.dot(vetor)     # Produto matriz-vetor otimizado
mat.transpose()    # Transposição eficiente

Formatos de Armazenamento

COO (Coordinate Format)

O formato COO utiliza três arrays paralelos: row, col e data. Cada posição k define um elemento na matriz através da relação mat[row[k], col[k]] = data[k]. É ampalmente utilizado como estágio intermediário de construção, pois aceita índices duplicados (que são somados automaticamente durante a conversão para outros formatos). Não suporta fatiamento nem operações aritméticas diretas.

import numpy as np
from scipy import sparse

lin_idx = np.array([0, 1, 2, 0])
col_idx = np.array([1, 2, 0, 3])
valores = np.array([10, 20, 30, 40])

coo = sparse.coo_matrix((valores, (lin_idx, col_idx)), shape=(3, 4))
print(coo.toarray())
# Saída:
# [[ 0 10  0 40]
#  [ 0  0 20  0]
#  [30  0  0  0]]

CSR (Compressed Sparse Row)

O CSR comprime a matriz por linhas utilizando três vetores: data (valores), indices (colunas dos valores) e indptr (ponteiros de início/fim de cada linha). Para a linha i, os índices das colunas estão em indices[indptr[i]:indptr[i+1]] e os valores correspondentes em data[indptr[i]:indptr[i+1]]. É extremamente eficiente para produtos matriz-vetor, aritmética esparsa e fatiamento horizontal. A inserção de novos elementos ou fatiamento vertical é custosa.

ptr_lin = np.array([0, 2, 3, 5])
idx_col = np.array([0, 2, 1, 0, 2])
vals = np.array([5, 8, 3, 1, 9])

csr = sparse.csr_matrix((vals, idx_col, ptr_lin), shape=(3, 3))
print(csr.toarray())
# Saída:
# [[5 0 8]
#  [0 3 0]
#  [1 0 9]]

CSC (Compressed Sparse Column)

Estruturalmente idêntico ao CSR, mas orientado a colunas. O vetor indptr agora delimita os intervalos por coluna, e indices armazena as linhas. Ideal quando o algoritmo requer acesso rápido a colunas inteiras ou operações de fatiamento vertical. Assim como o CSR, a modificação estrutural pós-criação é desencorajada.

ptr_col = np.array([0, 1, 3, 4])
idx_lin = np.array([1, 0, 2, 1])
vals_c = np.array([7, 4, 6, 2])

csc = sparse.csc_matrix((vals_c, idx_lin, ptr_col), shape=(3, 3))
print(csc.toarray())
# Saída:
# [[0 4 0]
#  [7 0 2]
#  [0 6 0]]

BSR (Block Sparse Row)

Variação do CSR que armazena submatrizes densas (blocos) em vez de escalares. Útil quando os dados não nulos aparecem agrupados em padrões regulares. O parâmetro blocksize=(R, C) deve dividir exatamente as dimensões da matriz. Em problemas de elementos finitos ou PDEs, o BSR frequentemente supera CSR/CSC em velocidade e compactação.

ptr_b = np.array([0, 1, 2])
col_b = np.array([0, 1])
blocos = np.array([[[1, 2], [3, 4]], 
                   [[5, 6], [7, 8]]])

bsr = sparse.bsr_matrix((blocos, col_b, ptr_b), shape=(4, 4))
print(bsr.toarray())
# Saída:
# [[1 2 0 0]
#  [3 4 0 0]
#  [0 0 5 6]
#  [0 0 7 8]]

DOK (Dictionary of Keys)

Utiliza um dicionário Python onde as chaves são tuplas (linha, coluna) e os valores são os elementos da matriz. Permite acesso e atualização em tempo O(1), sendo a escolha natural para construção incremental elemento a elemento. Não aceita chaves duplicadas e deve ser convertido para CSR/CSC antes de operações algébricas pesadas.

dok = sparse.dok_matrix((4, 4), dtype=np.float64)
for r in range(4):
    dok[r, r] = r * 1.5
    dok[r, (r + 1) % 4] = -1.0

print(dok.toarray())
# Saída:
# [[ 0.  -1.   0.   0. ]
#  [ 0.   1.5 -1.   0. ]
#  [ 0.   0.   3.  -1. ]
#  [-1.   0.   0.   4.5]]

LIL (List of Lists)

Armazena duas listas por linha: uma para os índices das colunas e outra para os valores. Excelente para construção linha a linha e suporta fatiamento flexível. A inserção desordenada pode degradar o desempenho para O(N), portanto, recomenda-se preencher os índices em ordem crescente. Assim como o DOK, deve ser convertido para formatos comprimidos antes de cálculos intensivos.

lil = sparse.lil_matrix((5, 5), dtype=int)
lil[0, 1] = 10
lil[2, :] = [0, 0, 5, 0, 0]
lil.setdiag(9)

print(lil.toarray())
# Saída:
# [[ 9 10  0  0  0]
#  [ 0  9  0  0  0]
#  [ 0  0  5  0  0]
#  [ 0  0  0  9  0]
#  [ 0  0  0  0  9]]

DIA (Diagonal Storage)

Projetado especificamente para matrizes com estrutura diagonal. Utiliza um array 2D data e um vetor offsets. Cada linha de data corresponde a uma diagonal, e offsets indica o deslocamento em relação à diagonal principal (0 = principal, positivo = acima, negativo = abaixo). Elementos que "sobram" fora dos limites da matriz são ignorados. Extremamente compacto para operadores diferenciais e matrizes tridiagonais.

diag_vals = np.array([[1, 2, 3, 4], 
                      [10, 20, 30, 40], 
                      [100, 200, 300, 400]])
desloc = np.array([0, -1, 2])

dia = sparse.dia_matrix((diag_vals, desloc), shape=(4, 4))
print(dia.toarray())
# Saída:
# [[  1   0 300   0]
#  [ 10   2   0 400]
#  [  0  20   3   0]
#  [  0   0  30   4]]

Comparativo de Formatos

Persistência e Armazenamento em Disco

Para salvar e carregar matrizes esparsas sem converter para formato denso, o SciPy disponibiliza funções nativas baseadas no padrão NPZ. A compressão é recomendada para reduzir o tamanho em disco, especialmente quando os índices possuem padrões repetitivos.

import numpy as np
from scipy import sparse

# Simulação de dados esparsos
base = np.random.rand(500, 500)
base[base < 0.92] = 0
mat_esparsa = sparse.csr_matrix(base)

# Salvamento com compressão
sparse.save_npz('dados_esparsos.npz', mat_esparsa, compressed=True)

# Leitura posterior
mat_recuperada = sparse.load_npz('dados_esparsos.npz')

# Verificação de integridade
assert np.allclose(mat_esparsa.toarray(), mat_recuperada.toarray())

Internamente, um arquivo NPZ de matriz CSR contém arrays separados para data.npy, indices.npy, indptr.npy, shape.npy e metadados de formato. Essa separação permite que o NumPy carregue apenas os componentes necessários, mantendo a eficiência de I/O mesmo em datasets massivos.