Разреженная матрица¶

Разреженная матрица — это матрица, в которой большинство элементов равны нулю. Противоположностью является плотная (заполненная) матрица, где нулевых элементов мало или нет. Понятие разреженности относительно: не существует строгого порога, но обычно матрица считается разреженной, если доля ненулевых элементов (так называемая «плотность») составляет менее 10–30 % от общего числа элементов. Разреженные матрицы широко встречаются в научных вычислениях, инженерных расчётах, машинном обучении, обработке сигналов и графовых задачах, где большие системы уравнений или данных содержат множество нулевых связей.

¶История

Интерес к разреженным матрицам возник в середине XX века с развитием численных методов решения систем линейных уравнений, возникающих в механике, гидродинамике и электротехнике. Первые работы по хранению и обработке разреженных матриц относятся к 1950–1960-м годам. В 1963 году американский математик Джеймс Уилкинсон в своей книге «Rounding Errors in Algebraic Processes» описал основные алгоритмы для разреженных систем. В 1970-е годы были разработаны первые эффективные форматы хранения, такие как CSR (Compressed Sparse Row) и CSC (Compressed Sparse Column), а также методы прямого и итерационного решения. С развитием вычислительной техники и появлением больших данных (Big Data) в 2000-х годах разреженные матрицы стали ключевым инструментом в рекомендательных системах, обработке естественного языка и анализе социальных сетей.

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

Хранение разреженной матрицы в виде двумерного массива (полный формат) неэффективно по памяти и времени. Для экономии ресурсов используются специальные форматы, которые хранят только ненулевые элементы и их индексы.

¶Список координат (COO)

Самый простой формат: хранятся три массива — значения ненулевых элементов, номера строк и номера столбцов. Каждый элемент представлен тройкой (строка, столбец, значение). Формат удобен для построения матрицы, но неэффективен для операций.

¶Сжатая строчная матрица (CSR)

Один из наиболее распространённых форматов. Используются три массива:

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

Формат CSR эффективен для умножения матрицы на вектор и для операций, требующих доступа по строкам.

¶Сжатая столбцовая матрица (CSC)

Аналог CSR, но сжатие по столбцам. Хранятся значения, номера строк и указатели на начало столбцов. CSC удобен для операций, где требуется доступ по столбцам.

¶Разреженный диагональный формат (DIA)

Используется для матриц с диагональной структурой (например, ленточных). Хранятся диагонали матрицы в виде плотных массивов. Эффективен для матриц с регулярной структурой.

¶Другие форматы

• ELLPACK (ELL) — хранит фиксированное число ненулевых элементов на строку, подходит для матриц с равномерной плотностью.
• HYB (Hybrid) — комбинация ELL и COO для обработки выбросов.
• Skyline (профильный) — хранит элементы от первого ненулевого до последнего в каждой строке.

¶Алгоритмы и операции

Работа с разреженными матрицами требует специальных алгоритмов, учитывающих их структуру.

¶Умножение матрицы на вектор (SpMV)

Базовая операция, используемая в итерационных методах. Для формата CSR выполняется за O(nnz) операций, где nnz — число ненулевых элементов. Оптимизация SpMV — ключевая задача для высокопроизводительных вычислений, поскольку она часто является узким местом.

¶Решение систем линейных уравнений

Для разреженных систем используются два основных подхода:

• Прямые методы — факторизация матрицы (например, LU-разложение) с учётом разреженности. Требуют переупорядочивания строк и столбцов для минимизации заполнения (fill-in) — появления новых ненулевых элементов в процессе факторизации. Популярные алгоритмы переупорядочивания: Cuthill-McKee, минимальной степени (minimum degree), вложенное сечение (nested dissection).
• Итерационные методы — не требуют факторизации, используют только матрично-векторные произведения. Примеры: метод сопряжённых градиентов (CG) для симметричных положительно определённых матриц, GMRES, BiCGSTAB для несимметричных. Итерационные методы часто эффективнее прямых для очень больших разреженных систем.

¶Переупорядочивание (ordering)

Процесс перестановки строк и столбцов матрицы для улучшения её структуры: уменьшения ширины ленты, снижения заполнения при факторизации или ускорения сходимости итерационных методов. Примеры: обратное переупорядочивание Cuthill-McKee (RCM), переупорядочивание по методу минимальной степени.

¶Применение

Разреженные матрицы используются в областях, где возникают большие системы с локальными связями.

¶Численное решение дифференциальных уравнений

Метод конечных элементов (МКЭ) и метод конечных разностей (МКР) приводят к разреженным матрицам, так как каждый узел сетки связан только с соседними узлами. Например, в расчётах прочности конструкций, теплопроводности, аэродинамики.

¶Машинное обучение и анализ данных

• Рекомендательные системы: матрица «пользователь-товар» (user-item) — разреженная, так как каждый пользователь взаимодействует с малым числом товаров. Используются методы матричной факторизации (SVD, ALS).
• Обработка естественного языка: матрица «документ-термин» (term-document) — разреженная, так как каждый документ содержит лишь малую часть словаря.
• Графовые нейронные сети: матрица смежности графа — разреженная, особенно для больших разреженных графов (социальные сети, графы знаний).

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

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

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

В сжатом зондировании (compressed sensing) и вейвлет-преобразованиях используются разреженные представления сигналов. Матрицы преобразований (например, дискретное косинусное преобразование) могут быть разрежены после пороговой обработки.

¶Программные реализации

Существует множество библиотек для работы с разреженными матрицами:

• SciPy (Python) — модуль scipy.sparse поддерживает форматы CSR, CSC, COO, DIA, ELL, а также операции SpMV, факторизацию и итерационные решатели.
• Eigen (C++) — библиотека линейной алгебры с поддержкой разреженных матриц.
• SuiteSparse — набор библиотек для разреженных матриц, включающий CHOLMOD (факторизация Холецкого), UMFPACK (LU-факторизация), SPQR (QR-факторизация).
• PETSc — библиотека для параллельного решения разреженных систем.
• cuSPARSE (NVIDIA) — библиотека для GPU-ускорения операций с разреженными матрицами.
• Intel MKL — содержит оптимизированные функции для разреженных матриц.

¶Критика и ограничения

• Заполнение (fill-in) — при прямых методах факторизации количество ненулевых элементов может резко возрасти, что снижает эффективность.
• Сложность реализации — алгоритмы для разреженных матриц сложнее, чем для плотных, требуют тщательного управления памятью и индексацией.
• Производительность на GPU — разреженные операции плохо параллелизуются из-за нерегулярного доступа к памяти, хотя существуют оптимизированные форматы (например, blocked CSR).
• Выбор формата — не существует универсального формата; эффективность зависит от структуры матрицы и выполняемых операций.

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

• Разреженные матрицы используются в моделировании климата, где системы уравнений содержат миллиарды неизвестных, но плотность матрицы может быть менее 0,001 %.
• Алгоритм PageRank, лежащий в основе поисковой системы Google, основан на итерационном решении разреженной системы уравнений, где матрица — это модифицированная матрица смежности веб-графа.
• В 2020-х годах с развитием больших языковых моделей (LLM) разреженные матрицы стали применяться для сжатия весов нейронных сетей (pruning), что позволяет уменьшить размер модели без значительной потери точности.