Разреженная матрица получается при использовании
метода конечных элементов в двух измерениях. На картинке ненулевые элементы показаны черным.
Разреженная матрица — это матрица с преимущественно нулевыми элементами.
По существу, разреженность соответствует системам со слабыми связями. Можно представить линию шариков, соединенных один за другим пружинками - это пример разреженной системы. Для контраста, если эти же шарики будут соединены пружинками каждый с каждым, то такая система будет представлять собой плотную матрицу. Термин разреженности используется также в комбинаторике и таких прикладных областях как сетевой анализ, при определении малой плотности значимых данных или соединений.
Огромные разреженные матрицы часто имеют место при решении таких задач, как дифференциальное уравнение в частных производных.
Представление
Алгоритмы
Применение
Библиотеки программ
Для вычислений с разреженными матрицами создано несколько библиотек:
и другие.
Примечания
- SparseLib++
- uBLAS / Boost
- A brief description of SPARSPAK Waterloo sparse linear equations package (англ.) // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 1984. — N.Y, 1984. — С. 17-20. — 10.1145/1057931.1057933
- T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, September 2006
Литература
- 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 с.