Введение
Матрица, в которой большинство элементов равны нулю.
Пример разреженной матрицы.
В численном анализе и научных вычислениях разреженная матрица или разреженный массив — это матрица, в которой большинство элементов равны нулю. Строгого определения относительно пропорции нулевых элементов, при которой матрица считается разреженной, нет, но распространенным критерием является то, что количество ненулевых элементов примерно равно количеству строк или столбцов. В отличие от этого, если большинство элементов ненулевые, матрица считается плотной, что часто встречается в машинном обучении. Операции, использующие стандартные структуры и алгоритмы для плотных матриц, оказываются медленными и неэффективными при работе с большими разреженными матрицами, поскольку вычислительные ресурсы и память расходуются на обработку нулей. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньше места для хранения. Некоторые очень большие разреженные матрицы невозможно обработать с помощью стандартных алгоритмов для плотных матриц.
С полосками
Важным особым типом разреженных матриц является матрица с полосой, определяемая следующим образом. Нижняя ширина полосы матрицы 'A' – это наименьшее число p, такое что элемент ai,j равен нулю, когда i > j + p. Аналогично, верхняя ширина полосы – это наименьшее число p, такое что ai,j = 0, когда i < j − p. Например, трехдиагональная матрица имеет нижнюю ширину полосы 1 и верхнюю ширину полосы 1. В качестве другого примера, следующая разреженная матрица имеет нижнюю и верхнюю ширину полосы, обе равные 3. Обратите внимание, что нули представлены точками для наглядности. Матрицы с относительно небольшой верхней и нижней шириной полосы известны как матрицы с полосой и часто позволяют использовать более простые алгоритмы, чем для общих разреженных матриц; или иногда можно применять алгоритмы для плотных матриц и добиться эффективности, просто перебирая меньшее количество индексов. Переупорядочивая строки и столбцы матрицы 'A', можно получить матрицу 'A'′ с меньшей шириной полосы. Существует ряд алгоритмов, предназначенных для минимизации ширины полосы.
Диагональ
Эффективная структура для частного случая матриц с полосой, диагональной матрицы, заключается в хранении только элементов главной диагонали в виде одномерного массива, таким образом, диагональная матрица размера n × n требует только n элементов.
Симметричный
Симметричная разреженная матрица возникает как матрица смежности неориентированного графа; её можно эффективно хранить в виде списка смежности.
Диагональ блока
Блочно-диагональная матрица состоит из подматриц вдоль её диагональных блоков. Блочно-диагональная матрица 'A' имеет вид
где 'A'k является квадратной матрицей для всех 1 ≤ k ≤ n.
Сокращение заполнения
Заполнение матрицы — это те элементы, которые изменяются от начального нуля к ненулевому значению в процессе выполнения алгоритма. Чтобы снизить требования к памяти и количество арифметических операций, используемых в алгоритме, полезно минимизировать заполнение путем перестановки строк и столбцов в матрице. Символическое разложение Холецкого можно использовать для вычисления наихудшего возможного заполнения перед выполнением фактического разложения Холецкого. Существуют и другие методы, помимо разложения Холецкого. Методы ортогонализации (например, QR-факторизация) часто используются, в частности, при решении задач методом наименьших квадратов. Хотя теоретическое заполнение остаётся одинаковым, на практике "ложные ненулевые элементы" могут различаться для разных методов. И символические версии этих алгоритмов можно использовать аналогичным образом, как и символическое разложение Холецкого, для вычисления наихудшего заполнения.
Решение уравнений с разреженной матрицей
Итеративные и прямые методы существуют для решения разреженных матриц. Итеративные методы, такие как метод сопряжённых градиентов и GMRES, используют быстрые вычисления произведений матрицы на вектор, где матрица является разреженной. Применение предварительных решателей может значительно ускорить сходимость таких итеративных методов.
Словарь ключей (DOK)
DOK состоит из словаря, который связывает пары (строка, столбец) со значениями элементов. Элементы, отсутствующие в словаре, считаются равными нулю. Этот формат удобен для постепенного построения разреженной матрицы в произвольном порядке, но неэффективен для перебора ненулевых элементов в лексикографическом порядке. Как правило, матрицу сначала строят в этом формате, а затем преобразуют в другой, более производительный формат для дальнейшей обработки.
Список списков (LIL)
LIL хранит один список в каждой строке, где каждая запись содержит индекс столбца и значение. Как правило, эти записи сортируются по индексу столбца для ускорения поиска. Это еще один формат, удобный для инкрементного построения матрицы.
Список координат (COO)
COO хранит список кортежей (строка, столбец, значение). В идеале записи сортируются сначала по индексу строки, а затем по индексу столбца, для повышения скорости произвольного доступа. Это еще один формат, который хорошо подходит для постепенного построения матрицы.
Сжатая редкая колонка (CSC или CCS)
CSC аналогичен CSR, за исключением того, что значения считываются сначала по столбцам, для каждого значения сохраняется индекс строки и хранятся указатели столбцов. Например, CSC представляется как (val, row ind, col ptr), где val – массив ненулевых значений матрицы, расположенных сверху вниз и слева направо; row ind – индексы строк, соответствующие этим значениям; а col ptr – список индексов в val, указывающих начало каждого столбца. Название обусловлено тем, что информация об индексах столбцов сжата по сравнению с форматом COO. Обычно для построения используется другой формат (LIL, DOK, COO). Этот формат эффективен для арифметических операций, извлечения столбцов и матрично-векторного произведения. Это традиционный формат для задания разреженной матрицы в MATLAB (с помощью функции sparse).
История
Термин "разреженная матрица", возможно, был введен Гарри Марковицем, который начал ряд новаторских работ, но затем перестал заниматься этой областью.