Compressed Sparse Row

Compressed Sparse Row (CSR, сжатое разреженное строковое представление) — это один из наиболее распространённых форматов хранения разреженных матриц в памяти компьютера, предназначенный для эффективного выполнения операций линейной алгебры над матрицами, содержащими преимущественно нулевые элементы. Формат основан на представлении ненулевых элементов матрицы в виде трёх одномерных массивов, что позволяет значительно сократить объём используемой памяти по сравнению с хранением всей матрицы целиком, особенно при высокой степени разреженности (доля ненулевых элементов менее 5–10 %). CSR широко применяется в численных методах, машинном обучении, обработке графов и при решении систем линейных уравнений с разреженными матрицами.

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

Разреженные матрицы возникли как естественная модель для задач, где связи между элементами системы редки: например, в методе конечных элементов для расчёта конструкций, в электрических цепях, в задачах сетевого анализа. Прямое хранение матрицы размером \(n \times n\) в виде двумерного массива требует \(O(n^2)\) памяти, что при больших \(n\) (сотни тысяч или миллионы) становится недопустимым. В 1960–1970-х годах, с развитием вычислительной техники, были разработаны первые компактные схемы хранения: координатный формат (COO), строчно-ориентированные форматы (CSR, CSC) и ленточные форматы. Формат CSR, предложенный в 1970-х годах (в частности, в работах по разреженным матрицам из библиотеки SPARSKIT), стал стандартом de facto благодаря балансу между компактностью и скоростью доступа к строкам.

Описание формата

CSR представляет матрицу \(A\) размером \(m \times n\) с \(nnz\) ненулевыми элементами с помощью трёх массивов:

• values — массив длины \(nnz\), содержащий значения ненулевых элементов в порядке обхода по строкам слева направо.
• col_indices — массив длины \(nnz\), содержащий номера столбцов для каждого элемента из values.
• row_ptr — массив длины \(m+1\), где \(row\_ptr[i]\) указывает индекс в массивах values и col_indices, с которого начинается описание строки \(i\). Последний элемент \(row\_ptr[m]\) равен \(nnz\) (или общему числу ненулевых элементов).

Пример

Пусть дана матрица \(A\): \[ A = \begin{pmatrix} 1 & 0 & 0 & 2 \\ 0 & 3 & 4 & 0 \\ 0 & 0 & 0 & 5 \end{pmatrix} \] Здесь \(m=3\), \(n=4\), \(nnz=5\). В формате CSR:

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

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

Характеристики и преимущества

• Экономия памяти: вместо \(O(m \times n)\) требуется \(O(nnz + m + 1)\) ячеек. Для разреженных матриц (например, с 1 % ненулевых элементов) экономия составляет два порядка.
• Быстрый доступ к строке: для получения всех ненулевых элементов строки \(i\) достаточно прочитать значения от \(row\_ptr[i]\) до \(row\_ptr[i+1]-1\) — операция \(O(k)\), где \(k\) — число ненулевых элементов в строке.
• Эффективное умножение матрицы на вектор: операция \(y = A \cdot x\) выполняется за \(O(nnz)\) операций, что оптимально для разреженных матриц.
• Простота реализации: формат легко реализуется на языках C, C++, Python (библиотеки SciPy, NumPy), Fortran.

Недостатки

• Медленная модификация: вставка или удаление ненулевого элемента требует перестройки массивов values и col_indices, а также обновления row_ptr — операция \(O(nnz)\) в худшем случае. Для частых изменений предпочтительнее использовать координатный формат (COO) или динамические структуры.
• Неэффективность для плотных матриц: если доля ненулевых элементов превышает 20–30 %, накладные расходы на хранение индексов могут превысить выгоду от сжатия.
• Параллельные вычисления: хотя CSR допускает параллельное умножение по строкам, распределение неравномерного числа ненулевых элементов по строкам может привести к дисбалансу нагрузки.

Разновидности формата

• Compressed Sparse Column (CSC): аналог CSR, но сжатие по столбцам. Используется, когда требуется быстрый доступ к столбцам (например, в решателях систем с разреженной матрицей). В CSC массивы называются values, row_indices, col_ptr.
• Block Compressed Sparse Row (BSR): расширение CSR для блочных матриц, где ненулевые элементы группируются в блоки фиксированного размера (например, \(2 \times 2\) или \(4 \times 4\)). Позволяет ускорить операции за счёт векторизации.
• ELLPACK (ELL): формат, хранящий для каждой строки фиксированное число ненулевых элементов; удобен для GPU, но неэффективен при сильно различающейся длине строк.
• Hybrid (HYB): комбинация ELL и COO для обработки выбросов — строк с аномально большим числом ненулевых элементов.

Применение

Численные методы

CSR является основным форматом для хранения матриц в библиотеках разреженной линейной алгебры: SPARSKIT, SuiteSparse, PETSc, Trilinos. Используется в решателях систем линейных уравнений (методы сопряжённых градиентов, GMRES, LU-разложение) и в задачах на собственные значения (ARPACK).

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

В библиотеках для машинного обучения (Scikit-learn, XGBoost, LightGBM) CSR применяется для хранения разреженных признаковых матриц, где большинство признаков равны нулю (например, в one-hot-кодировании, текстовых данных в формате «мешок слов»). Операции умножения матрицы на вектор в CSR лежат в основе градиентного спуска для линейных моделей.

Обработка графов

Разреженные матрицы смежности графов (с числом вершин до миллионов) хранятся в CSR. Алгоритмы поиска в ширину, PageRank, кластеризации графов реализуются через матрично-векторные произведения. Например, библиотека GraphBLAS использует CSR для представления графов.

Вычислительная физика и инженерия

В методе конечных элементов (МКЭ) глобальная матрица жёсткости является разреженной; её хранение в CSR позволяет решать задачи с миллионами степеней свободы на персональных компьютерах.

Реализации

• SciPy (Python): модуль scipy.sparse предоставляет класс csr_matrix с методами умножения, транспонирования, преобразования в другие форматы.
• Eigen (C++): библиотека линейной алгебры включает шаблонный класс SparseMatrix с поддержкой CSR.
• cuSPARSE (NVIDIA): библиотека для GPU, оптимизированная под CSR для ускорения операций на видеокартах.
• Intel MKL: содержит функции для разреженных матриц в формате CSR, включая разреженное умножение матриц (sparse BLAS).

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

• Формат CSR иногда называют «Yale format» по названию Йельского университета, где в 1970-х годах разрабатывались первые алгоритмы для разреженных матриц.
• В стандарте BLAS (Basic Linear Algebra Subprograms) с 1990-х годов существует расширение для разреженных операций (sparse BLAS), где CSR является одним из поддерживаемых форматов.
• Для матриц с симметричной структурой (например, в задачах МКЭ) используется вариант CSR, хранящий только верхний или нижний треугольник, что вдвое сокращает объём памяти.

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

Основной недостаток CSR — неэффективность при частых модификациях. В таких случаях применяют координатный формат (COO), где каждый ненулевой элемент хранится как тройка (строка, столбец, значение), или динамические структуры (например, сжатые разреженные строки с блочным выделением памяти). Для матриц с равномерным распределением ненулевых элементов по строкам (например, в некоторых задачах обработки изображений) формат ELLPACK может быть быстрее на GPU. Тем не менее, CSR остаётся стандартом для статичных разреженных матриц благодаря простоте и высокой производительности базовых операций.

Источники

• Saad Y. Iterative Methods for Sparse Linear Systems. — 2nd ed. — SIAM, 2003. — Глава 3.
• Davis T. A. Direct Methods for Sparse Linear Systems. — SIAM, 2006. — Глава 2.
• Документация SciPy: scipy.sparse.csr_matrix.
• Barrett R. et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. — SIAM, 1994.