Разрежённая матрица — это матрица с преимущественно нулевыми элементами. В противном случае, если бо́льшая часть элементов матрицы ненулевые, матрица считается плотной.
Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разрежённой. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов[1]:
Огромные разрежённые матрицы часто возникают при решении таких задач, как дифференциальное уравнение в частных производных.
При хранении и преобразовании разрежённых матриц в компьютере бывает полезно, а часто и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разрежённую структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, применительно к большим разрежённым матрицам работают относительно медленно и требуют значительных объёмов памяти. Однако разрежённые матрицы могут быть легко сжаты путём записи только своих ненулевых элементов, что снижает требования к компьютерной памяти.
Один из возможных вариантов хранения — по строкам. В каждой строке — список ненулевых элементов и список их индексов.
Расход памяти на один ненулевой элемент равен размеру элемента + 4 байта на индекс (на 32-разрядной архитектуре). Недостаток — доступ к произвольному элементу строки за O(log(N)), где N — максимальное количество элементов в строке. Такая скорость достигается бинарным поиском по индексу.
Для вычислений с разрежёнными матрицами создан ряд библиотек для различных языков программирования, среди них:
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .