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

«Разреженность» перенаправляется сюда. Чтобы узнать о других значениях, см. Разреженный (значения) .

Пример разреженной матрицы $\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&99\\\end{smallmatrix}}\right)$

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

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

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

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

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

Особые случаи

полосатый

Основная статья: Ленточная матрица

Важным специальным типом разреженных матриц является ленточная матрица , определенная следующим образом. Нижняя полоса пропускания матрицы 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. Обратите внимание, что нули для ясности представлены точками. $${\begin{bmatrix}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 &X&\cdot &X&\\\end{bmatrix}}$$

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

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

Диагональ

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

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

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

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

Блочно -диагональная матрица состоит из подматриц вдоль ее диагональных блоков. Блочно-диагональная матрица A имеет вид $$\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}},$$

где A _k — квадратная матрица для всех k = 1,..., n .

Использовать

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

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

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

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

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

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

Хранилище

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

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

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

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

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

DOK состоит из словаря , который отображает строка, столбец) ( пары на значения элементов. Элементы, отсутствующие в словаре, принимаются равными нулю. Этот формат хорош для постепенного построения разреженной матрицы в случайном порядке, но не подходит для перебора ненулевых значений в лексикографическом порядке. Обычно в этом формате создается матрица, а затем преобразуется в другой, более эффективный формат для обработки.

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

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

Координационный список (COO)

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

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

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

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

• Массивы V и COL_INDEX имеют длину NNZ и содержат ненулевые значения и индексы столбцов этих значений соответственно.
• COL_INDEX содержит столбец, в котором соответствующая запись V. находится
• Массив ROW_INDEX имеет длину m + 1 и кодирует индекс в V и COL_INDEX , где начинается данная строка. Это эквивалентно ROW_INDEX[j], кодирующему общее количество ненулевых значений над строкой j . Последний элемент — это NNZ , т. е. фиктивный индекс в V сразу после последнего действительного индекса NNZ − 1 .

Например, матрица $${\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]
row_end   = ROW_INDEX[row + 1]

Затем мы берем фрагменты из V и COL_INDEX, начиная с row_start и заканчивая row_end.

Чтобы извлечь строку 1 (вторую строку) этой матрицы, мы устанавливаем row_start=1 и row_end=2. Затем делаем ломтики V[1:2] = [8] и COL_INDEX[1:2] = [1]. Теперь мы знаем, что в строке 1 у нас есть один элемент в столбце 1 со значением 8.

В этом случае представление CSR содержит 13 записей по сравнению с 16 в исходной матрице. Формат CSR экономит память только тогда, когда NNZ < ( m ( n − 1) − 1) / 2 .

Другой пример, матрица $${\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 записи: 8 в V , 8 в COL_INDEX и 5 в ROW_INDEX .

• ROW_INDEX разбивает массив V на строки: (10, 20) (30, 40) (50, 60, 70) (80), указывающий индекс V (и COL_INDEX ), где начинается и заканчивается каждая строка;
• 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[ i + 1] − ROW_INDEX[ i ] работает для любой строки i . Более того, стоимость памяти этого избыточного хранилища, вероятно, незначительна для достаточно большой матрицы.

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

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

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

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

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

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

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

• PETSc , большая библиотека C, содержащая множество различных решателей матриц для различных форматов хранения матриц.
• Trilinos — большая библиотека C++ с подбиблиотеками, предназначенными для хранения плотных и разреженных матриц и решения соответствующих линейных систем.
• Eigen3 — это библиотека C++, содержащая несколько решателей разреженных матриц. Однако ни один из них не распараллелен .
• MUMPS ( MU ltifrontal Parallel Massively Sparse Direct Solver ), написанный на Fortran90, представляет собой фронтальный решатель .
• Deal.II — библиотека конечных элементов, которая также имеет подбиблиотеку для разреженных линейных систем и их решений.
• DUNE , еще одна библиотека конечных элементов, которая также имеет подбиблиотеку для разреженных линейных систем и их решений.
• Armadillo предоставляет удобную оболочку C++ для BLAS и LAPACK.
• SciPy обеспечивает поддержку нескольких форматов разреженных матриц, линейной алгебры и решателей.
• ALGLIB — это библиотека C++ и C# с поддержкой разреженной линейной алгебры.
• Библиотека ARPACK Fortran 77 для диагонализации и манипулирования разреженной матрицей с использованием алгоритма Арнольди.
• Библиотека SLEPc для решения крупномасштабных линейных систем и разреженных матриц.
• scikit-learn , библиотека Python для машинного обучения , обеспечивает поддержку разреженных матриц и решателей.

История

Термин «разреженная матрица», возможно, был придуман Гарри Марковицем , который начал некоторые новаторские работы, но затем оставил эту область.

См. также

• Матричное представление
• Принцип Парето
• Рваная матрица
• Однозаходная матрица
• Матрица горизонта
• Код разреженного графа
• Разреженный файл
• Формат файла Харвелл-Боинг
• Форматы обмена Matrix Market

Ссылки

• Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Джонс Хопкинс. ISBN  978-0-8018-5414-9 .
• Стер, Йозеф; Булирш, Роланд (2002). Введение в численный анализ (3-е изд.). Берлин, Нью-Йорк: Springer Verlag . ISBN  978-0-387-95452-3 .
• Теварсон, Реджинальд П. (май 1973 г.). Разреженные матрицы (часть серии «Математика в науке и технике») . Academic Press Inc. (Эта книга профессора Государственного университета Нью-Йорка из Stony Book была первой книгой, посвященной исключительно разреженным матрицам. В начале 1980-х годов в этом университете предлагались курсы для аспирантов, использующие ее в качестве учебника).
• Банк, Рэндольф Э.; Дуглас, Крейг К. «Пакет умножения разреженной матрицы» (PDF) .
• Писанецкий, Серджио (1984). Технология разреженной матрицы . Академическая пресса. ISBN  9780125575805 .
• Сней, Ричард А. (1976). «Уменьшение профиля разреженных симметричных матриц». Бюллетень геодезии . 50 (4): 341–352. Бибкод : 1976БГеод..50..341С . дои : 10.1007/BF02521587 . hdl : 2027/uc1.31210024848523 . S2CID   123079384 . Также Технический меморандум NOAA NOS NGS-4, Национальная геодезическая служба, Роквилл, Мэриленд.
• Дженнифер Скотт и Мирослав Тума: «Алгоритмы для разреженных линейных систем», Биркхаузер, (2023), DOI: https://doi.org/10.1007/978-3-031-25820-6 (книга с открытым доступом)

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

• Гиббс, Норман Э.; Пул, Уильям Г.; Стокмейер, Пол К. (1976). «Сравнение нескольких алгоритмов уменьшения пропускной способности и профиля» . Транзакции ACM в математическом программном обеспечении . 2 (4): 322–330. дои : 10.1145/355705.355707 . S2CID   14494429 .
• Гилберт, Джон Р.; Молер, Клив; Шрайбер, Роберт (1992). «Разреженные матрицы в MATLAB: Проектирование и реализация» . Журнал SIAM по матричному анализу и приложениям . 13 (1): 333–356. CiteSeerX   10.1.1.470.1054 . дои : 10.1137/0613024 .
• Исследование алгоритмов разреженной матрицы в Техасском университете A&M.
• Коллекция SuiteSparse Matrix
• SMALL project Проект, финансируемый ЕС, по разреженным моделям, алгоритмам и изучению словарей для крупномасштабных данных.
• Вольфганг Хакбуш: Итеративное решение больших разреженных систем уравнений , Springer, (1994).
• Юсеф Саад: Итеративные методы для разреженных линейных систем , SIAM, ISBN 978-0-89871-534-7 (2003).
• Тимоти А. Дэвис: Прямые методы для разреженных линейных систем , SIAM, ISBN 978-0-89871-613-9 (2006).