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

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

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

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

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

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

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

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

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

Этот раздел ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться раздел, посвящённый представлению разреженных матриц. Вы можете помочь проекту, написав этот раздел.

Алгоритмы

Этот раздел ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться раздел, посвящённый алгоритмам с разреженными матрицами. Вы можете помочь проекту, написав этот раздел.

Применение

Этот раздел ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться раздел, посвящённый применению разреженных матриц. Вы можете помочь проекту, написав этот раздел.

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

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

• SparseLib++ (C++)^[2]
• uBLAS (C++, в составе Boost)^[3]
• SPARSPAK (Fortran)^[4]
• CSparse (C)^[5]

и другие.

Примечания

1. ↑ ^{1 2} Писсанецки, 1988, Введение
2. ↑ SparseLib++
3. ↑ uBLAS / Boost
4. ↑ Alan George, Esmond Ng A brief description of SPARSPAK Waterloo sparse linear equations package (англ.) // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 1984. — N.Y, 1984. — С. 17-20. — ISBN 978-1-4503-0245-6. — DOI:10.1145/1057931.1057933
5. ↑ 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 с.

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.