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

Пример разреженной матрицы${ displaystyle left ({ begin {smallmatrix} 11 & 22 & 0 & 0 & 0 & 0 & 0 0 & 33 & 44 & 0 & 0 & 0 & 0 0 & 0 & 55 & 66 & 77 & 0 & 0 0 & 0 & 0 & 0 & 0 & 88 & 0 0 & 0 & 0 & 0 & 0 & 0 & 0 & 99 } end {small)$

Вышеупомянутая разреженная матрица содержит только 9 ненулевых элементов с 26 нулевыми элементами. Его разреженность составляет 74%, а плотность - 26%.

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

В числовой анализ и научные вычисления, а разреженная матрица или же разреженный массив это матрица в котором большинство элементов равны нулю. Нет строгого определения, сколько элементов должно быть нулевым, чтобы матрица рассматривалась. редкий но общий критерий состоит в том, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов отличны от нуля, матрица считается плотный. Количество элементов с нулевым знаком, деленное на общее количество элементов (например, m × n для матрицы m × n), иногда называют редкость матрицы.

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

При хранении и работе с разреженными матрицами на компьютер, полезно и часто необходимо использовать специализированные алгоритмы и структуры данных которые используют разреженную структуру матрицы. Для разреженных матриц изготовлены специализированные ЭВМ,^[1] поскольку они распространены в области машинного обучения.^[2] Операции, использующие стандартные структуры и алгоритмы с плотной матрицей, медленные и неэффективные при применении к большим разреженным матрицам в качестве обработки и объем памяти тратятся на нули. Редкие данные по своей природе легче сжатый и, следовательно, требует значительно меньше место хранения. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов плотных матриц.

Хранение разреженной матрицы

Матрица обычно хранится как двумерный массив. Каждая запись в массиве представляет собой элемент а_я,j матрицы, и к нему обращаются два индексы я и j. Обычно я это индекс строки, пронумерованный сверху вниз, и j - это индекс столбца, пронумерованный слева направо. Для м × п матрица, объем памяти, необходимый для хранения матрицы в этом формате, пропорционален м × п (без учета того, что размеры матрицы тоже нужно сохранить).

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

Форматы можно разделить на две группы:

• Те, которые поддерживают эффективную модификацию, например DOK (Словарь ключей), LIL (Список списков) или COO (Список координат). Обычно они используются для построения матриц.
• Те, которые поддерживают эффективный доступ и матричные операции, такие как CSR (сжатая разреженная строка) или CSC (сжатый разреженный столбец).

Словарь ключей (ДОК)

ДОК состоит из толковый словарь что отображает (строка столбец)-пары к значению элементов. Элементы, отсутствующие в словаре, считаются равными нулю. Формат хорош для пошагового построения разреженной матрицы в случайном порядке, но плохой для итерации ненулевых значений в лексикографическом порядке. Обычно в этом формате создается матрица, а затем преобразуется в другой, более эффективный формат для обработки.^[3]

Список списков (LIL)

LIL хранит по одному списку для каждой строки, каждая запись содержит индекс столбца и значение. Обычно эти записи отсортированы по индексу столбца для более быстрого поиска. Это еще один формат, подходящий для построения инкрементальной матрицы.^[4]

Список координат (COO)

COO хранит список (строка, столбец, значение) кортежи. В идеале записи сортируются сначала по индексу строки, а затем по индексу столбца, чтобы сократить время произвольного доступа. Это еще один формат, который подходит для построения инкрементальной матрицы.^[5]

Сжатая разреженная строка (формат CSR, CRS или Yale)

В сжатый разреженный ряд (CSR) или сжатое хранилище строк (CRS) или формат Йеля представляет собой матрицу M тремя (одномерными) массивами, которые соответственно содержат ненулевые значения, экстенты строк и индексы столбцов. Он похож на COO, но сжимает индексы строк, отсюда и название. Этот формат обеспечивает быстрый доступ к строке и умножение матрицы на вектор (MИкс). Формат CSR используется по крайней мере с середины 1960-х годов, а первое полное описание появилось в 1967 году.^[6]

Формат CSR хранит разреженные м × п матрица M в виде строк с использованием трех (одномерных) массивов (V; COL_INDEX; ROW_INDEX). Позволять NNZ обозначим количество ненулевых записей в M. (Обратите внимание, что индексы с отсчетом от нуля будет использоваться здесь.)

• Массивы V и COL_INDEX имеют длину NNZ, и содержат ненулевые значения и индексы столбцов этих значений соответственно.

• Массив ROW_INDEX имеет длину м + 1 и кодирует индекс в V и COL_INDEX где начинается данная строка. Последний элемент NNZ , т.е. фиктивный индекс в V сразу после последнего действительного индекса ННЗ - 1. ^[7]

Например, матрица

${ displaystyle { begin {pmatrix} 5 & 0 & 0 & 0 0 & 8 & 0 & 0 0 & 0 & 3 & 0 0 & 6 & 0 & 0 end {pmatrix}}}$

это 4 × 4 матрица с 4 ненулевыми элементами, поэтому

   V = [5 8 3 6] COL_INDEX = [0 1 2 1] ROW_INDEX = [0 1 2 3 4] 

предполагая язык с нулевым индексом.

Чтобы извлечь строку, мы сначала определяем:

   row_start = ROW_INDEX [строка] row_end = ROW_INDEX [строка + 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 <(м (п − 1) − 1) / 2Другой пример, матрица

${ displaystyle { begin {pmatrix} 10 & 20 & 0 & 0 & 0 & 0 0 & 30 & 0 & 40 & 0 & 0 0 & 0 & 50 & 60 & 70 & 0 0 & 0 & 0 & 0 & 0 & 80 end {pmatrix}}}$

это 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 запись.

• ROW_INDEX разбивает массив V в ряды: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX выравнивает значения в столбцах: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Обратите внимание, что в этом формате первое значение ROW_INDEX всегда равен нулю, а последний всегда NNZ, поэтому они в некотором смысле избыточны (хотя в языках программирования, где длина массива должна быть явно сохранена, NNZ не будет лишним). Тем не менее, это позволяет избежать необходимости обрабатывать исключительный случай при вычислении длины каждой строки, поскольку это гарантирует формулу ROW_INDEX [я + 1] - ROW_INDEX [я] работает для любой строки я. Более того, стоимость памяти этого избыточного хранилища, вероятно, незначительна для достаточно большой матрицы.

Форматы разреженных матриц Йельского университета (старые и новые) являются экземплярами схемы CSR. Старый формат Йельского университета работает точно так же, как описано выше, с тремя массивами; новый формат объединяет ROW_INDEX и COL_INDEX в единый массив и обрабатывает диагональ матрицы отдельно.^[8]

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

Он, вероятно, известен как Йельский формат, потому что он был предложен в отчете о пакете разреженных матриц Йельского университета 1977 года, подготовленном факультетом компьютерных наук Йельского университета.^[9]

Сжатый разреженный столбец (CSC или CCS)

CSC аналогичен CSR, за исключением того, что значения сначала считываются по столбцу, для каждого значения сохраняется индекс строки и сохраняются указатели столбцов. Например, CSC - это (val, row_ind, col_ptr), куда вал - это массив ненулевых значений матрицы (сверху вниз, затем слева направо); row_ind - индексы строк, соответствующие значениям; и, col_ptr это список вал индексы, с которых начинается каждый столбец. Название основано на том факте, что информация индекса столбца сжимается относительно формата COO. Обычно для построения используется другой формат (LIL, DOK, COO). Этот формат эффективен для арифметических операций, разделения столбцов и произведений матрица-вектор. Видеть scipy.sparse.csc_matrix. Это традиционный формат для указания разреженной матрицы в MATLAB (через редкий функция).

Специальная структура

Полосатая

Важным специальным типом разреженных матриц является ленточная матрица, определяемый следующим образом. В меньшая пропускная способность матрицы А это наименьшее число п так что запись а_я,j исчезает всякий раз, когда я > j + п. Точно так же верхняя полоса пропускания это наименьшее число п такой, что а_я,j = 0 в любое время я < j − п (Голуб и Ван Лоан 1996, §1.2.1). Например, трехдиагональная матрица имеет меньшую пропускную способность 1 и верхняя полоса пропускания 1. В качестве другого примера следующая разреженная матрица имеет нижнюю и верхнюю полосы пропускания равные 3. Обратите внимание, что для ясности нули представлены точками.

${ displaystyle left ({ begin {smallmatrix} X & X & X & cdot & cdot & cdot & cdot & X & X & cdot & X & X & cdot & cdot & X & cdot & X & cdot & X & cdot & cdot & cdot & X & cdot & X & cdot & X & cdot & cdot & X & X & cdot & X & X & X & cdot & cdot & cdot & X & X & X & cdot & cdot & cdot & cdot & cdot cdot & X & cdot & X & end {smallmatrix}} right)}$

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

Переставляя строки и столбцы матрицы А может быть возможно получить матрицу А′ с меньшей пропускной способностью. Ряд алгоритмов разработан для минимизация полосы пропускания.

Диагональ

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

Симметричный

Симметричная разреженная матрица возникает как матрица смежности из неориентированный граф; его можно эффективно хранить как список смежности.

Диагональ блока

А блочно-диагональная матрица состоит из подматриц по диагональным блокам. Блочно-диагональная матрица А имеет форму

${ displaystyle mathbf {A} = { begin {bmatrix} mathbf {A} _ {1} & 0 & cdots & 0 0 & mathbf {A} _ {2} & cdots & 0 vdots & vdots & ddots & vdots 0 & 0 & cdots & mathbf {A} _ {n} end {bmatrix}},}$

куда А_k квадратная матрица для всех k = 1, ..., п.

Уменьшение заполнения

В заполните матрицы - это те элементы, которые изменяются от начального нуля до ненулевого значения во время выполнения алгоритма. Чтобы уменьшить требования к памяти и количество арифметических операций, используемых во время алгоритма, полезно минимизировать заполнение путем переключения строк и столбцов в матрице. В символическое разложение Холецкого можно использовать для расчета наихудшего возможного заполнения перед выполнением фактического Разложение Холецкого.

Есть и другие методы, кроме Разложение Холецкого в использовании. Методы ортогонализации (такие как QR-факторизация) распространены, например, при решении задач методом наименьших квадратов. Хотя теоретическая подстановка остается прежней, с практической точки зрения «ложные ненулевые значения» могут быть разными для разных методов. И символические версии этих алгоритмов могут использоваться таким же образом, как и символические версии Холецкого, для вычисления заполнения наихудшего случая.

Решение разреженных матричных уравнений

Обе итеративный и существуют прямые методы для решения разреженных матриц.

Итерационные методы, такие как сопряженный градиент метод и GMRES использовать быстрые вычисления матрично-векторных произведений ${ displaystyle Ax_ {i}}$, где матрица ${ displaystyle A}$ редко. Использование предварительные кондиционеры может значительно ускорить сходимость таких итерационных методов.

Программного обеспечения

Многие программные библиотеки поддерживают разреженные матрицы и предоставляют средства решения для разреженных матричных уравнений. Следующие программы с открытым исходным кодом:

• SuiteSparse, набор алгоритмов разреженных матриц, направленных на прямое решение разреженных линейных систем.
• PETSc, большая библиотека C, содержащая множество различных решателей матриц для различных форматов хранения матриц.
• Трилинос, большая библиотека C ++ с под-библиотеками, предназначенными для хранения плотных и разреженных матриц и решения соответствующих линейных систем.
• Eigen3 - это библиотека C ++, которая содержит несколько решателей разреженных матриц. Однако ни один из них не распараллеленный.
• МАМПЫ (MUлифронтальный Mусердно ппараллельные разреженные прямые Solver), написанный на Fortran90, является фронтальный решатель.
• ДЮНА, библиотека конечных элементов, в которой также есть подбиблиотека для разреженных линейных систем и их решений.
• PaStix.
• SuperLU.
• Armadillo предоставляет удобную оболочку C ++ для BLAS и LAPACK.
• SciPy обеспечивает поддержку нескольких форматов разреженных матриц, линейной алгебры и решателей.
• SPArse Matrix (спам) Пакет R для разреженных матриц.
• Язык Wolfram Language Инструменты для работы с разреженными массивами
• АЛГЛИБ это библиотека C ++ и C # с поддержкой разреженной линейной алгебры
• ARPACK Библиотека Fortran 77 для диагонализации и управления разреженными матрицами с использованием алгоритма Арнольди
• РЕДКО Ссылка (старая) NIST пакет для диагонализации (реальной или сложной) разреженной матрицы
• SLEPc Библиотека для решения больших линейных систем и разреженных матриц
• Sympiler, генератор кода для конкретной предметной области и библиотека для решения линейных систем и задач квадратичного программирования.

История

Период, термин разреженная матрица возможно был придуман Гарри Марковиц который начал новаторскую работу, но затем ушел с поля.^[10]

Смотрите также

Примечания

Рекомендации

• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Джонс Хопкинс. ISBN  978-0-8018-5414-9.CS1 maint: ref = harv (связь)
• Стоер, Йозеф; Булирш, Роланд (2002). Введение в численный анализ (3-е изд.). Берлин, Нью-Йорк: Springer-Verlag. ISBN  978-0-387-95452-3.
• Тьюарсон, Реджинальд П. (май 1973 г.). Разреженные матрицы (часть серии «Математика в науке и технике»). Academic Press Inc. (Эта книга, написанная профессором Университета штата Нью-Йорк в Stony Book, была первой книгой, посвященной исключительно разреженным матрицам. В начале 1980-х в этом университете были предложены курсы для аспирантов, использующие ее в качестве учебника).
• Bank, Randolph E .; Дуглас, Крейг С. "Пакет умножения разреженных матриц" (PDF).
• Писсанецки, Серджио (1984). Технология разреженной матрицы. Академическая пресса.
• Снай, Ричард А. (1976). «Уменьшение профиля разреженных симметричных матриц». Бюллетень Géodésique. 50 (4): 341. Дои:10.1007 / BF02521587. HDL:2027 / uc1.31210024848523. Также NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.^[1]

дальнейшее чтение

• Гиббс, Норман Э .; Пул, Уильям Дж .; Штокмейер, Пол К. (1976). «Сравнение нескольких алгоритмов сокращения пропускной способности и профиля». Транзакции ACM на математическом ПО. 2 (4): 322–330. Дои:10.1145/355705.355707.
• Гилберт, Джон Р .; Молер, Клив; Шрайбер, Роберт (1992). «Разреженные матрицы в MATLAB: разработка и реализация». Журнал SIAM по матричному анализу и приложениям. 13 (1): 333–356. CiteSeerX  10.1.1.470.1054. Дои:10.1137/0613024.
• Исследование алгоритмов разреженной матрицы в Техасском университете A&M.
• SuiteSparse Matrix Коллекция
• МАЛЕНЬКИЙ проект Финансируемый ЕС проект по разреженным моделям, алгоритмам и изучению словарей для крупномасштабных данных.