Algoritmo de Matrices Dispersas (Sparse) en Python: Conceptos, Formatos y Ejemplos Prácticos

Introducción

En ciencia de datos, aprendizaje automático y simulaciones numéricas, es frecuente trabajar con matrices que contienen muy pocos valores diferentes de cero. Almacenar esas matrices como estructuras densas (listas o numpy.ndarray) resulta ineficiente tanto en memoria como en tiempo de cómputo. Las matrices dispersas (sparse matrices) ofrecen una solución al representar únicamente los elementos no nulos.

¿Qué es una matriz dispersa?

Una matriz se considera dispersa cuando el número de elementos no nulos nnz es mucho menor que el total de elementos n_rows × n_cols. El objetivo del algoritmo sparse es:

• Reducir la huella de memoria.
• Acelerar operaciones lineales (multiplicación, factorización, solución de sistemas).

Formatos de almacenamiento más usados

Existen varios formatos que equilibran velocidad de acceso, facilidad de construcción y consumo de memoria. Los más populares en el ecosistema Python son:

• COO (Coordinate): lista de tuplas (row, col, data). Ideal para construir matrices a partir de datos sin orden.
• CSR (Compressed Sparse Row): almacena datos por filas, excelente para multiplicación matriz‑vector y acceso rápido a filas.
• CSC (Compressed Sparse Column): versión columna‑orientada, útil para operaciones que requieren acceso a columnas (p.ej., factorizaciones LU).
• DOK (Dictionary of Keys): diccionario Python {(i,j): value}. Muy flexible para inserciones dinámicas.
• LIL (List of Lists): lista de listas por fila, fácil de modificar pero menos eficiente para cálculos intensivos.

Comparativa rápida (dos columnas)

Ejemplos prácticos en Python

Usaremos SciPy, la biblioteca de facto para sparse matrices, y PyData/Sparse para tensores de mayor dimensión.

1️⃣ Creación de una matriz COO a partir de datos

import numpy as np
from scipy.sparse import coo_matrix

# Definimos coordenadas y valores
row  = np.array([0, 0, 1, 3, 4])
col  = np.array([0, 2, 2, 1, 4])
data = np.array([10, 20, 30, 40, 50])

# Construimos la matriz 5x5
A_coo = coo_matrix((data, (row, col)), shape=(5, 5))
print(A_coo.toarray())

Salida:

[[10  0 20  0  0]
 [ 0  0 30  0  0]
 [ 0  0  0  0  0]
 [ 0 40  0  0  0]
 [ 0  0  0  0 50]]

2️⃣ Conversión a CSR y multiplicación matriz‑vector

from scipy.sparse import csr_matrix

# Conversión rápida
A_csr = A_coo.tocsr()

# Vector denso
x = np.arange(5)

# Multiplicación eficiente
y = A_csr.dot(x)
print('Resultado:', y)

Resultado: Resultado: [ 20 60 0 40 250]

3️⃣ Uso de DOK para inserciones dinámicas

from scipy.sparse import dok_matrix

D = dok_matrix((1000, 1000), dtype=np.float64)
# Insertamos 5 valores aleatorios
for _ in range(5):
    i, j = np.random.randint(0, 1000, size=2)
    D[i, j] = np.random.rand()

print('nnz =', D.nnz)
# Convertir a CSR para cálculos posteriores
D_csr = D.tocsr()

Buenas prácticas y optimización

• Elija el formato correcto: Si su algoritmo accede mayormente por filas, use CSR; por columnas, CSC.
• Evite conversiones repetidas: Cada .tocsr() o .tocsc() implica una copia de datos.
• Pre‑alocación de capacidad: Cuando sepa nnz de antemano, construya la matriz directamente en CSR/CSC usando scipy.sparse.csr_matrix((data, indices, indptr), shape).
• Uso de tipos de dato adecuados: Para modelos de machine‑learning, float32 reduce la mitad de la memoria sin pérdida significativa de precisión.
• Benchmarking: Utilice timeit o perf_counter para comparar csr_matrix.dot vs numpy.dot en matrices densas.

Resolución de problemas comunes (troubleshooting)

⚠️ Error "matrix dimensions do not match"

Este error suele aparecer al intentar multiplicar matrices con dimensiones incompatibles. Verifique siempre que A.shape[1] == x.shape[0]. En el caso de matrices sparse, .shape sigue siendo una tupla.

⚠️ Memoria excesiva al convertir a densa

Evite .toarray() o .todense() en matrices con nnz grande. Si necesita inspeccionar solo una sub‑matriz, use A[0:10, 0:10].toarray() o A.tocsr().data directamente.

⚠️ Rendimiento bajo en inserciones masivas

Construya primero una lista de coordenadas y valores, cree una matriz COO y conviértala a CSR/CSC. Insertar elemento a elemento en un CSR existente es O(nnz) y muy costoso.

Comparación con tecnologías emergentes

En entornos de GPU, cuSPARSE de NVIDIA ofrece versiones GPU‑aceleradas de CSR/CSC. En Python, CuPy expone cupyx.scipy.sparse con una API idéntica a SciPy, permitiendo migrar código con cambios mínimos.

Para tensores dispersos de orden superior, PyData/Sparse implementa el formato COO extendido, compatible con numpy y dask para procesamiento distribuido.

Caso de uso real: Recomendación de productos

Un motor de recomendación colaborativa representa usuarios y artículos como una matriz usuario × producto extremadamente dispersa (solo <≈1 % de interacciones son no nulas). El pipeline típico:

1. Cargar datos CSV a coo_matrix (filas = usuarios, columnas = productos).
2. Convertir a csr_matrix para cálculos de similitud por filas (coseno).
3. Multiplicar U_csr · V_csr.T para obtener una matriz de puntuaciones parciales.
4. Aplicar top‑k por usuario usando np.argpartition sobre la fila resultante.

Este enfoque permite escalar a millones de usuarios sin exceder la memoria RAM de una máquina típica.

Conclusión

Las matrices dispersas son una herramienta esencial para cualquier profesional que trabaje con datos de gran escala o modelos numéricos. Elegir el formato correcto, seguir buenas prácticas de construcción y aprovechar bibliotecas optimizadas como SciPy, CuPy o PyData/Sparse garantiza eficiencia, escalabilidad y mantenibilidad del código.