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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Разреженная матрица получается при использовании метода конечных элементов в двух измерениях. На картинке ненулевые элементы показаны черным.

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

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

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

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

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

Представление[править | править вики-текст]

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

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

Алгоритмы[править | править вики-текст]

Применение[править | править вики-текст]

Библиотеки программ[править | править вики-текст]

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

и другие.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

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