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

Разреженная матрица получается при использовании метода конечных элементов в двух измерениях. На картинке ненулевые элементы показаны черным.

Разреженная матрица — это матрица с преимущественно нулевыми элементами.

Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разреженной. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов:

• есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
• в каждой строке не превышает 10 в типичном случае;
• ограничено $n^{1+\gamma}$, где $\gamma < 1$.
• таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей.

По существу, разреженность соответствует системам со слабыми связями. Можно представить линию шариков, соединенных один за другим пружинками — это пример разреженной системы. Для контраста, если эти же шарики будут соединены пружинками каждый с каждым, то такая система будет представлять собой плотную матрицу. Термин разреженности используется также в комбинаторике и таких прикладных областях как сетевой анализ, при определении малой плотности значимых данных или соединений.

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

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

Представление

Один из возможных вариантов хранения — по строкам. В каждой строке — список ненулевых элементов и список их индексов.

Расход памяти на 1 элемент — размер элемента + 4 байта на индекс (на 32-разрядной архитектуре). Недостаток — доступ к произвольному элементу строки за O(log(N)), где N — максимальное количество элементов в строке. Такая скорость достигается бинарным поиском по индексу.

Библиотеки программ

Для вычислений с разреженными матрицами создано несколько библиотек:

• SparseLib++ (C++)
• uBLAS (C++, в составе Boost)
• SPARSPAK (Fortran)
• CSparse (C)

и другие.

Литература

• Reginald P. Tewarson Sparse Matrices. — Academic Press, 1973. — 160 с. — ISBN 0126856508 перевод: Тьюарсон Р. Разреженные матрицы = Sparse Matrices. — М.: Мир, 1977. — 191 с.
• Писсанецки С. Технология разреженных матриц = Sparse Matrix Technology. — М.: Мир, 1988. — 410 с. — ISBN 5-03-000960-4
• Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М.: Мир, 1984. — 333 с.