Разреженные матрицы: когда почти всё — нули

Матрица миллион на миллион, но в ней лишь несколько ненулевых элементов в строке. Хранить все нули — безумие. Решение — разреженные матрицы.

Разреженная (sparse) матрица — матрица, у которой подавляющее большинство элементов равны нулю; её хранят, записывая только ненулевые элементы и их координаты.

Зачем это нужно

Разреженные матрицы повсюду, где есть «локальные связи». Граф социальной сети: миллионы пользователей, но у каждого лишь сотни друзей — матрица связей почти вся из нулей. Конечно-элементная сетка: узел связан только с соседями. Текстовая модель «мешок слов»: документ содержит сотни слов из словаря в миллион. Хранить такую матрицу плотно (все элементы подряд) — это терабайты нулей. Разреженный формат хранит только то, что есть.

Сколько экономим

Матрица 10000×10000 плотно — это 100 миллионов чисел (~800 МБ для double). Если ненулевых всего 50000 (0.05%), разреженно нужно ~50000 значений + их координаты — около мегабайта. Экономия в сотни раз, и операции тоже ускоряются: умножать на ноль не нужно.

Форматы хранения

Формат	Хранит	Хорош для
COO (координатный)	тройки (строка, столбец, значение)	построения матрицы
CSR (по строкам)	сжатые указатели строк	умножения на вектор, обхода по строкам
CSC (по столбцам)	сжатые указатели столбцов	обхода по столбцам, решения СЛАУ

Разреженность «руками»: словарь координат

Простейший разреженный формат — словарь {(строка, столбец): значение}. Реализуем умножение разреженной матрицы на вектор:

# Разреженная матрица 3x3, только 3 ненулевых элемента
sparse = {(0, 0): 2.0, (1, 2): 5.0, (2, 1): 3.0}

vector = [1.0, 2.0, 3.0]

result = [0.0, 0.0, 0.0]
for (i, j), val in sparse.items():
    result[i] += val * vector[j]   # умножаем только ненулевые!

print("Результат A*v =", result)
print("Хранили элементов:", len(sparse), "вместо 9")

Вывод:

Результат A*v = [2.0, 15.0, 6.0]
Хранили элементов: 3 вместо 9

Ключевая идея видна: в цикле мы пробегаем только по ненулевым элементам, а не по всей матрице. На матрице 10⁶×10⁶ это разница между «мгновенно» и «никогда».

А в SciPy — промышленные форматы

import numpy as np
from scipy.sparse import csr_matrix

data = np.array([2.0, 5.0, 3.0])
rows = np.array([0, 1, 2])
cols = np.array([0, 2, 1])
A = csr_matrix((data, (rows, cols)), shape=(3, 3))

v = np.array([1.0, 2.0, 3.0])
print(A.dot(v))        # [ 2. 15.  6.] — то же, но молниеносно
print(A.nnz)           # 3 — число ненулевых

Как работает под капотом

Формат CSR (Compressed Sparse Row) — самый ходовой. Он хранит три массива: data (ненулевые значения подряд), indices (номера столбцов этих значений) и indptr (для каждой строки — где в data она начинается). Чтобы умножить на вектор, для каждой строки берут её срез из data и indices и считают скалярное произведение только по ненулевым. Это даёт умножение за время O(число ненулевых), а не O(n²). Именно поэтому итеративные решатели СЛАУ (метод сопряжённых градиентов в scipy.sparse.linalg) могут работать с матрицами в миллиарды элементов.

Частые ошибки

Применять к плотным матрицам. Если нулей мало, разреженный формат только замедляет — overhead на координаты не окупается.
Менять CSR поэлементно. Вставка нового элемента в CSR дорогая; для построения берут COO или LIL, потом конвертируют в CSR.
Превращать в плотную случайно. Операция вроде A + 1 сделает все нули единицами и «взорвёт» память.

Итог

Разреженные матрицы хранят только ненулевые элементы — экономия памяти в сотни раз.
Возникают всюду, где связи локальны: графы, сетки, тексты.
Форматы: COO для построения, CSR/CSC для вычислений.
Операции идут за время ~числа ненулевых; это в scipy.sparse.