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

Матрица, в которой большинство элементов равны нулю

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

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

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

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

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

Полосчатый

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

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

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

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

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

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

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

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

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

Хранилище

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

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

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

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

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

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

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

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

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

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

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

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

Формат CSR хранит разреженную матрицу M размером m × n в строковой форме с использованием трех (одномерных) массивов (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. [ ^8]

Например, матрица имеет размер 4 × 4 и содержит 4 ненулевых элемента, следовательно, $${\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}}$$

В = [ 5 8 3 6 ]COL_INDEX = [ 0 1 2 1 ]СТРОКА_ИНДЕКС = [ 0 1 2 3 4 ]

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

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

row_start = ROW_INDEX[строка]row_end = ROW_INDEX[строка + 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 .

Другой пример: матрица имеет размер 4 × 6 (24 элемента) с 8 ненулевыми элементами, поэтому $${\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}}}$$

В = [ 10 20 30 40 50 60 70 80 ]COL_INDEX = [ 0 1 1 3 2 3 4 5 ] СТРОКА_ИНДЕКС = [ 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 в один массив и обрабатывает диагональ матрицы отдельно. ^[9]

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

Вероятно, он известен как Йельский формат, поскольку был предложен в докладе 1977 года «Yale Sparse Matrix Package» кафедры компьютерных наук Йельского университета. ^[10]

Сжатый разреженный столбец (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 Massively Parallel sparse direct Solver ), написанный на Fortran90, представляет собой фронтальный решатель .
• deal.II — библиотека конечных элементов, которая также имеет подбиблиотеку для разреженных линейных систем и их решений.
• DUNE — еще одна библиотека конечных элементов, которая также имеет подбиблиотеку для разреженных линейных систем и их решений.
• Armadillo предоставляет удобную в использовании оболочку C++ для BLAS и LAPACK.
• SciPy обеспечивает поддержку нескольких форматов разреженных матриц, линейной алгебры и решателей.
• ALGLIB — библиотека C++ и C# с поддержкой разреженной линейной алгебры.
• Библиотека ARPACK Fortran 77 для диагонализации и обработки разреженных матриц с использованием алгоритма Арнольди
• Библиотека SLEPc для решения линейных систем больших размеров и разреженных матриц
• scikit-learn , библиотека Python для машинного обучения , обеспечивает поддержку разреженных матриц и решателей.

История

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

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

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

Примечания

1. Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). "Эффективное умножение разреженных и плотных матриц в многоядерной системе". 2017 IEEE 17-я Международная конференция по коммуникационным технологиям (ICCT) . IEEE. стр. 1880–3. doi :10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. Вычислительным ядром DNN является умножение больших разреженных и плотных матриц. В области численного анализа разреженная матрица — это матрица, заполненная в основном нулями в качестве элементов таблицы. Напротив, если количество ненулевых элементов в матрице относительно велико, то ее обычно считают плотной матрицей. Доля нулевых элементов (ненулевых элементов) в матрице называется разреженностью (плотностью). Операции с использованием стандартных структур и алгоритмов плотных матриц относительно медленные и потребляют большие объемы памяти при применении к большим разреженным матрицам.
2. "Cerebras Systems представляет первый в отрасли чип на триллион транзисторов". www.businesswire.com . 2019-08-19 . Получено 2019-12-02 . WSE содержит 400 000 вычислительных ядер, оптимизированных для ИИ. Вычислительные ядра, называемые SLAC™ (Sparse Linear Algebra Cores), являются гибкими, программируемыми и оптимизированными для разреженной линейной алгебры, которая лежит в основе всех вычислений нейронных сетей.
3. "Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory". www.anl.gov (Пресс-релиз) . Получено 2019-12-02 . WSE — самый большой чип из когда-либо созданных, его площадь составляет 46 225 квадратных миллиметров, он в 56,7 раза больше самого большого графического процессора. Он содержит в 78 раз больше вычислительных ядер, оптимизированных для ИИ, в 3000 раз больше высокоскоростной памяти на кристалле, в 10 000 раз больше пропускной способности памяти и в 33 000 раз больше пропускной способности связи.
4. См. scipy.sparse.dok_matrix
5. См. scipy.sparse.lil_matrix
6. См. scipy.sparse.coo_matrix
7. Булуч, Айдын; Файнман, Джереми Т.; Фриго, Маттео; Гилберт, Джон Р.; Лейзерсон, Чарльз Э. (2009). Параллельное умножение разреженной матрицы на вектор и матрицы на транспонированный вектор с использованием сжатых разреженных блоков (PDF) . Симптом ACM по параллелизму в алгоритмах и архитектурах. CiteSeerX 10.1.1.211.5256 . 
8. Саад 2003
9. Банк, Рэндольф Э.; Дуглас, Крейг К. (1993), "Пакет умножения разреженных матриц (SMMP)" (PDF) , Достижения в области вычислительной математики , 1 : 127–137, doi :10.1007/BF02070824, S2CID  6412241
10. Eisenstat, SC; Gursky, MC; Schultz, MH; Sherman, AH (апрель 1977 г.). "Yale Sparse Matrix Package" (PDF) . Архивировано (PDF) из оригинала 6 апреля 2019 г. . Получено 6 апреля 2019 г. .
11. Устное историческое интервью с Гарри М. Марковицем, стр. 9, 10.

Ссылки

• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Университет Джонса Хопкинса. ISBN 978-0-8018-5414-9.
• Stoer, Josef; Bulirsch, Roland (2002). Введение в численный анализ (3-е изд.). Springer. doi :10.1007/978-0-387-21738-3. ISBN 978-0-387-95452-3.
• Тьюарсон, Реджинальд П. (1973). Разреженные матрицы. Математика в науке и технике. Т. 99. Academic Press. ISBN 0-12-685650-8. OCLC  316552948.(Эта книга, написанная профессором издательства Stony Book в Университете штата Нью-Йорк, стала первой книгой, полностью посвященной разреженным матрицам. В начале 1980-х годов в этом университете предлагались курсы повышения квалификации с использованием этой книги в качестве учебника).
• Банк, Рэндольф Э.; Дуглас, Крейг К. «Пакет умножения разреженных матриц» (PDF) .
• Писсанецки, Серджио (1984). Технология разреженных матриц . Academic Press. ISBN 978-0-12-557580-5. OCLC  680489638.
• Сней, Ричард А. (1976). «Уменьшение профиля разреженных симметричных матриц». Bulletin Géodésique . 50 (4): 341–352. Bibcode :1976BGeod..50..341S. doi :10.1007/BF02521587. hdl : 2027/uc1.31210024848523 . S2CID  123079384.Также Технический меморандум NOAA NOS NGS-4, Национальная геодезическая служба, Роквилл, Мэриленд. Ссылка на Saad 2003.
• Скотт, Дженнифер; Тума, Мирослав (2023). Алгоритмы для разреженных линейных систем . Биркхаузер. doi :10.1007/978-3-031-25820-6.(Открытый доступ)

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

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