Войти
 |
Разреженная матрица, полученная при решении задачи конечных элементов в двух измерениях. Ненулевые элементы показаны черным. В численном анализе и научных вычислениях, разреженная матрица или разреженный массив представляет собой матрицу , в которой большинство элементов равны нулю. Не существует строгого определения того, сколько элементов должно быть нулевым, чтобы матрица считалась разреженной, но общий критерий состоит в том, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов отличны от нуля, матрица считается плотной . Количество элементов с нулевым знаком, деленное на общее количество элементов (например, m × n для матрицы m × n), иногда называют разреженностью матрицы.
Концептуально разреженность соответствует системам с небольшим количеством парных взаимодействий. Например, рассмотрим линию шаров, соединенных пружинами от одного к другому: это разреженная система, поскольку связаны только соседние шары. Напротив, если бы одна и та же линия шаров имела пружины, соединяющие каждый шар со всеми другими шарами, система соответствовала бы плотной матрице. Концепция разреженности полезна в комбинаторике и таких прикладных областях, как теория сетей и численный анализ, которые обычно имеют низкую плотность важных данных или соединений. Большие разреженные матрицы часто появляются в научных или инженерных приложениях при решении уравнений в частных производных.
. При хранении разреженных матриц и манипулировании ими на компьютере это Полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют разреженную структуру матрицы. Специализированные компьютеры были созданы для разреженных матриц, поскольку они распространены в области машинного обучения. Операции с использованием стандартных структур и алгоритмов с плотной матрицей медленны и неэффективны при применении к большим разреженным матрицам, поскольку обработка и память тратятся на нули. Разреженные данные по своей природе легче сжимать и, следовательно, требуют значительно меньше памяти. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов плотных матриц.
Матрица обычно хранится как двумерный массив. Каждая запись в массиве представляет собой элемент a i, j матрицы, и к нему обращаются два индекса i и j. Обычно i - это индекс строки, пронумерованный сверху вниз, а j - индекс столбца, пронумерованный слева направо. Для матрицы размера m × n объем памяти, необходимый для хранения матрицы в этом формате, пропорционален m × n (без учета того факта, что размеры матрицы также должны быть сохранены).
В случае разреженной матрицы существенное сокращение требований к памяти может быть реализовано путем сохранения только ненулевых элементов. В зависимости от количества и распределения ненулевых записей могут использоваться разные структуры данных, что дает огромную экономию памяти по сравнению с базовым подходом. Компромисс заключается в том, что доступ к отдельным элементам становится более сложным и необходимы дополнительные структуры, чтобы иметь возможность однозначно восстановить исходную матрицу.
Форматы можно разделить на две группы:
DOK состоит из словаря, который отображает (строка, столбец) - пары на значения элементов. Элементы, отсутствующие в словаре, считаются равными нулю. Формат хорош для пошагового построения разреженной матрицы в случайном порядке, но плохой для итерации ненулевых значений в лексикографическом порядке. Обычно матрица создается в этом формате, а затем преобразуется в другой, более эффективный формат для обработки.
LIL хранит по одному списку на строку, причем каждая запись содержит столбец индекс и значение. Обычно эти записи отсортированы по индексу столбца для более быстрого поиска. Это еще один формат, подходящий для построения инкрементальной матрицы.
COO хранит список кортежей (строка, столбец, значение). В идеале записи сортируются сначала по индексу строки, а затем по индексу столбца, чтобы сократить время произвольного доступа. Это еще один формат, который подходит для построения инкрементной матрицы.
Сжатая разреженная строка (CSR) или сжатое хранилище строк (CRS) или Йельский формат представляет собой матрицу M тремя (одномерными) массивами, которые соответственно содержат ненулевые значения, экстенты строк и индексы столбцов. Он похож на COO, но сжимает индексы строк, отсюда и название. Этот формат обеспечивает быстрый доступ к строке и умножение матрицы на вектор (M x). Формат CSR используется по крайней мере с середины 1960-х годов, первое полное описание появилось в 1967 году.
Формат CSR хранит разреженную матрицу m × n M в виде строки с использованием трех (одномерных) массивов (V, COL_INDEX, ROW_INDEX). Пусть NNZ обозначает количество ненулевых записей в M . (Обратите внимание, что здесь должны использоваться отсчитываемые от нуля индексы.)
Например, матрица
- это матрица 4 × 4 с 4 ненулевыми элементами, поэтому
V = [5 8 3 6 ] COL_INDEX = [0 1 2 1] ROW_INDEX = [0 0 2 3 4]
при условии, что язык с нулевым индексом.
Чтобы извлечь строку, мы сначала определяем:
row_start = ROW_INDEX [row] row_end = ROW_INDEX [row + 1]
Затем мы берем срезы из V и COL_INDEX, начиная с в row_start и заканчивая row_end.
Чтобы извлечь строку 1 (вторая строка) этой матрицы, мы устанавливаем row_start = 0и row_end = 2. Затем мы делаем срезы V [0: 2] = [5, 8]и COL_INDEX [0: 2] = [0, 1]. Теперь мы знаем, что в строке 1 у нас есть два элемента в столбцах 0 и 1 со значениями 5 и 8.
В этом случае представление CSR содержит 13 элементов по сравнению с 16 в исходной матрице. Формат CSR сохраняет память только тогда, когда NNZ < (m (n − 1) − 1) / 2. Another example, the matrix
- это матрица 4 × 6 (24 элемента) с 8 ненулевыми элементами, поэтому
V = [10 20 30 40 50 60 70 80] COL_INDEX = [0 1 1 3 2 3 4 5] ROW_INDEX = [0 2 4 7 8]
. Всего сохраняется как 21 запись.
(10, 20) (30, 40) (50, 60, 70) (80);(10, 20,...) (0, 30, 0, 40,...) (0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).Обратите внимание, что в В этом формате первое значение ROW_INDEX всегда равно нулю, а последнее - всегда NNZ, поэтому они в некотором смысле избыточны (хотя в языках программирования, где длина массива должна быть явно сохранена, NNZ не будет избыточным). Тем не менее, это позволяет избежать необходимости обрабатывать исключительный случай при вычислении длины каждой строки, поскольку это гарантирует, что формула ROW_INDEX [i + 1] - ROW_INDEX [i] работает для любой строки i. Более того, стоимость памяти этого избыточного хранилища, вероятно, незначительна для достаточно большой матрицы.
(старый и новый) форматы разреженных матриц Йельского университета являются экземплярами схемы CSR. Старый формат Йельского университета работает точно так же, как описано выше, с тремя массивами; новый формат объединяет ROW_INDEX и COL_INDEX в один массив и обрабатывает диагональ матрицы отдельно.
Для логических матриц смежности массив данных можно опустить, поскольку наличие записи в массиве строк достаточно для моделирования двоичного отношения смежности.
Вероятно, он известен как формат Йельского университета, потому что он был предложен в отчете о пакете разреженных матриц Йельского университета 1977 г., подготовленном факультетом компьютерных наук Йельского университета.
CSC аналогичен CSR, за исключением того, что значения считываются сначала по столбцу, индекс строки сохраняется для каждого значения, а указатели столбцов сохраняются. Например, CSC - это (val, row_ind, col_ptr), где val - это массив ненулевых значений матрицы (сверху вниз, затем слева направо); row_ind - это индексы строк, соответствующие значениям; и col_ptr - это список индексов val, с которых начинается каждый столбец. Название основано на том факте, что информация индекса столбца сжимается относительно формата COO. Обычно для построения используется другой формат (LIL, DOK, COO). Этот формат эффективен для арифметических операций, разделения столбцов и произведений матрица-вектор. См. scipy.sparse.csc_matrix. Это традиционный формат для указания разреженной матрицы в MATLAB (через функцию sparse ).
Важным специальным типом разреженных матриц является матрица с полосами, определяемая следующим образом. Нижняя полоса матрицы A- это наименьшее число p, такое что запись a i, j исчезает всякий раз, когда i>j + p. Аналогично, верхняя полоса пропускания - это наименьшее число p, такое что a i, j = 0 всякий раз, когда i < j − p (Golub Van Loan 1996, §1.2.1). Например, трехдиагональная матрица имеет нижнюю полосу пропускания 1 и верхнюю полосу пропускания 1. В качестве другого примера следующая разреженная матрица имеет нижнюю и верхнюю полосы пропускания, равные 3. Обратите внимание, что для ясности нули представлены точками.
Матрицы с достаточно малой верхней и нижней полосой пропускания известны как матрицы каналов и часто поддаются более простым алгоритмам, чем обычные разреженные матрицы; или иногда можно применить алгоритмы плотной матрицы и повысить эффективность, просто перебирая уменьшенное количество индексов.
Посредством переупорядочивания строк и столбцов матрицы A можно получить матрицу A 'с меньшей полосой пропускания. Для минимизации полосы пропускания разработан ряд алгоритмов.
Очень эффективная структура для крайнего случая полосовых матриц, диагональная матрица, заключается в хранении только записей в главной диагонали как одномерный массив, поэтому для диагональной матрицы размера n × n требуется только n элементов.
Симметричная разреженная матрица возникает как матрица смежности неориентированного графа ; его можно эффективно сохранить как список смежности.
A , блочно-диагональная матрица состоит из подматриц вдоль своих диагональных блоков. Блочно-диагональная матрица A имеет вид
где Ak- квадратная матрица для всех k = 1,..., n.
Заполнение матрицы - это те элементы, которые изменяются с начального нуля на ненулевое значение во время выполнения алгоритма. Чтобы уменьшить требования к памяти и количество арифметических операций, используемых во время алгоритма, полезно минимизировать заполнение путем переключения строк и столбцов в матрице. символическое разложение Холецкого можно использовать для вычисления наихудшего возможного заполнения перед выполнением фактического разложения Холецкого.
. Существуют и другие методы, кроме разложения Холецкого. Методы ортогонализации (такие как QR-факторизация) распространены, например, при решении задач методом наименьших квадратов. Хотя теоретическая подстановка остается прежней, с практической точки зрения «ложные ненулевые значения» могут быть разными для разных методов. И символические версии этих алгоритмов могут использоваться таким же образом, как и символические версии Холецкого, для вычисления заполнения наихудшего случая.
Для решения разреженных матриц существуют как итерационные, так и прямые методы.
Итерационные методы, такие как метод сопряженного градиента и GMRES, используют быстрые вычисления произведений матрица-вектор 
Многие программные библиотеки поддерживают разреженные матрицы и предоставляют средства решения для разреженных матричных уравнений. Следующие компоненты имеют открытый исходный код:
Термин разреженная матрица, возможно, был придуман Гарри Марковиц, который инициировал некоторые новаторские работы, но затем покинул поле.
