WikiSort.ru - Не сортированное

Разрежённая матрица — это матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевые, матрица считается плотной.

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

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

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

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

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

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

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

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

Для вычислений с разрежёнными матрицами создан ряд библиотек для различных языков программирования, среди них:

• SparseLib++ (C++)^[2]
• uBLAS (C++, в составе Boost)^[3]
• SPARSPAK (Фортран)^[4]
• CSparse (Си)^[5]
• Модуль Sparse из библиотеки SciPy (Python)^[6][7].

Примечания

Литература

• 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 с.

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