Сжатые разреженные матрицы

Сжатые разреженные матрицы (англ. compressed sparse row, CSR, или compressed row storage, CRS) — это один из наиболее распространённых форматов хранения разреженных матриц в памяти компьютера, предназначенный для эффективного представления матриц, большинство элементов которых равны нулю. Основная идея формата заключается в том, чтобы хранить только ненулевые элементы и их координаты, избегая выделения памяти под нулевые значения. Это позволяет существенно сократить объём используемой оперативной памяти и ускорить выполнение матричных операций, особенно в задачах вычислительной математики, машинного обучения и обработки больших данных.

История и предпосылки появления

Разреженные матрицы возникают во многих областях науки и техники: при решении систем линейных уравнений методом конечных элементов, в графовых алгоритмах, в задачах обработки естественного языка (например, в матрицах «терм-документ») и в рекомендательных системах. Хранение таких матриц в плотном (full) формате, где каждый элемент, включая нулевые, занимает ячейку памяти, приводит к нерациональному расходу ресурсов. Например, матрица размером 10⁶ × 10⁶ с плотностью 0,001 % (то есть 10⁴ ненулевых элементов) в плотном формате double (8 байт на элемент) потребовала бы около 8 терабайт памяти, что непрактично.

Первые алгоритмы для работы с разреженными матрицами появились в 1960-х годах, а форматы хранения, такие как CSR, были формализованы в 1970–1980-х годах. Развитие вычислительной техники и рост объёмов данных стимулировали разработку эффективных структур данных, среди которых CSR стал стандартом де-факто благодаря балансу между компактностью и скоростью доступа.

Основные форматы сжатых разреженных матриц

Существует несколько вариантов сжатого хранения, различающихся порядком обхода элементов и способом кодирования столбцов/строк. Наиболее распространённые:

Формат CSR (Compressed Sparse Row)

CSR хранит матрицу в виде трёх массивов:

• values — массив ненулевых значений, расположенных в порядке обхода по строкам (слева направо, сверху вниз).
• col_indices — массив индексов столбцов для каждого значения из values.
• row_ptr — массив указателей на начало каждой строки в массивах values и col_indices. Длина row_ptr равна числу строк + 1, где последний элемент равен общему числу ненулевых элементов.

Пример для матрицы 3×3: `` [1 0 2] [0 3 0] [4 0 5] `` Ненулевые элементы: 1, 2, 3, 4, 5.

• values = [1, 2, 3, 4, 5]
• col_indices = [0, 2, 1, 0, 2]
• row_ptr = [0, 2, 3, 5]

Пояснение: строка 0 содержит элементы с индексами 0 и 2 (values[0:2] = [1,2]), строка 1 — элемент с индексом 1 (values[2:3] = [3]), строка 2 — элементы с индексами 0 и 2 (values[3:5] = [4,5]).

Формат CSC (Compressed Sparse Column)

CSC является транспонированным аналогом CSR: обход выполняется по столбцам, а массивы называются values, row_indices и col_ptr. Этот формат удобен для операций, требующих доступа по столбцам, например, при умножении матрицы на вектор-столбец.

Формат COO (Coordinate List)

COO — простейший формат, хранящий тройки (строка, столбец, значение) для каждого ненулевого элемента. Он не требует сжатия указателей, но менее эффективен для матричных операций, чем CSR/CSC. Однако COO удобен для построения матрицы из списка данных.

Устройство и характеристики

Компактность

CSR требует хранения трёх массивов: values (число элементов = nnz, где nnz — количество ненулевых элементов), col_indices (nnz целых чисел) и row_ptr (n+1 целых чисел, где n — число строк). Для матрицы с nnz ≪ n·m (где m — число столбцов) экономия памяти по сравнению с плотным форматом может достигать нескольких порядков. Например, для матрицы 10⁶×10⁶ с nnz = 10⁶ при использовании 8-байтовых чисел с плавающей точкой и 4-байтовых целых: плотный формат — 8·10¹² байт (8 ТБ), CSR — 8·10⁶ + 4·10⁶ + 4·(10⁶+1) ≈ 12·10⁶ + 4 ≈ 12 МБ.

Скорость операций

CSR обеспечивает эффективный доступ к строкам: для получения всех ненулевых элементов i-й строки достаточно прочитать значения от row_ptr[i] до row_ptr[i+1] и соответствующие col_indices. Это делает CSR идеальным для умножения разреженной матрицы на плотный вектор (SpMV — sparse matrix-vector multiplication) — ключевой операции в итерационных решателях. Однако доступ к отдельному элементу (например, поиск A[i][j]) требует бинарного поиска в строке, что медленнее, чем в плотном формате.

Ограничения

• CSR неэффективен для частого добавления или удаления ненулевых элементов, так как это требует перестройки массивов.
• Для матриц с очень неравномерным распределением ненулевых элементов (например, с сильно различающейся длиной строк) может потребоваться дополнительная балансировка.
• Формат не поддерживает прямую индексацию по столбцам; для операций по столбцам предпочтительнее CSC.

Применение

Вычислительная математика

CSR широко используется в решателях систем линейных уравнений с разреженными матрицами, таких как метод сопряжённых градиентов, GMRES и многосеточные методы. Библиотеки, такие как SuiteSparse, PETSc, Trilinos, реализуют операции с CSR. В России эти методы применяются в программных комплексах для моделирования физических процессов (например, в пакетах LOGOS, FlowVision, разработанных в РФ).

Машинное обучение

В задачах обработки текстов (например, в методе «мешка слов» — bag-of-words) матрицы «терм-документ» имеют разреженность до 99 %. CSR используется в библиотеках scikit-learn, TensorFlow, PyTorch для хранения таких матриц. В рекомендательных системах (например, матрицы «пользователь-товар») также применяется CSR.

Графовые алгоритмы

Матрица смежности графа часто является разреженной. CSR позволяет эффективно хранить графы с миллионами вершин и рёбер. Алгоритмы поиска в ширину, PageRank и вычисления центральности используют CSR.

Обработка изображений и сигналов

В задачах сжатия изображений (например, JPEG) и вейвлет-преобразований разреженные представления могут быть реализованы через CSR.

Примеры реализации

В языках программирования

• Python: библиотека scipy.sparse предоставляет классы csr_matrix, csc_matrix, coo_matrix. Например:

``python from scipy.sparse import csr_matrix A = csr_matrix([[1, 0, 2], [0, 3, 0], [4, 0, 5]]) print(A.toarray()) # преобразование в плотную матрицу ``

• C++: библиотека Eigen поддерживает формат SparseMatrix с режимом RowMajor (CSR) и ColMajor (CSC). В Boost uBLAS также есть разреженные матрицы.
• Julia: встроенный тип SparseMatrixCSC (по умолчанию CSC) и SparseMatrixCSR (через пакет SparseArrays). В России Julia используется в научных расчётах, например, в Институте вычислительной математики РАН.

В промышленных системах

• Базы данных: системы управления графами (например, Neo4j) используют разреженные матрицы для хранения связей.
• Поисковые системы: алгоритмы ранжирования (PageRank) оперируют разреженными матрицами в формате CSR.

Интересные факты

• Формат CSR является основой для многих специализированных форматов, таких как ELLPACK (для матриц с равномерной длиной строк) и HYB (гибридный формат, сочетающий ELL и COO).
• В суперкомпьютерных тестах производительности (например, HPCG — High Performance Conjugate Gradients) операции с CSR являются ключевым бенчмарком.
• В России разработка эффективных реализаций CSR ведётся в рамках проектов по созданию отечественных суперкомпьютерных технологий, таких как «Эльбрус» и «Ангара».

Критика и альтернативы

Несмотря на популярность, CSR не всегда оптимален. Для матриц с очень большим числом строк (например, 10⁹) массив row_ptr может занимать значительный объём памяти. Альтернативы включают:

• Blocked CSR (BCSR) — разбиение матрицы на блоки для улучшения кэш-локальности.
• CSR5 — формат, оптимизированный для графических процессоров (GPU), с использованием битовых масок.
• Paged CSR — хранение row_ptr в виде страниц для работы с памятью большого объёма.

Источники

1. Saad Y. Iterative Methods for Sparse Linear Systems. — 2nd ed. — SIAM, 2003.
2. Davis T. A. Direct Methods for Sparse Linear Systems. — SIAM, 2006.
3. Документация SciPy: Sparse matrices (scipy.sparse). — SciPy.org.
4. Barrett R. et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. — SIAM, 1994.
5. Bell N., Garland M. Efficient Sparse Matrix-Vector Multiplication on CUDA. — NVIDIA Technical Report, 2008.