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

В численном анализе и научных вычислениях разреженная матрица или разреженный массив — это матрица , в которой большинство элементов равны нулю. ^[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. Обратите внимание, что нули для ясности представлены точками.

{\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 \times 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 i, j$ матрицы и доступна по двум индексам $i$ и $j$ . Обычно $i$ — это индекс строки, нумерованный сверху вниз, а $j$ — индекс столбца, нумерованный слева направо. Для матрицы $m \times n$ объем памяти, необходимый для хранения матрицы в этом формате, пропорционален $m \times n$ (не учитывая тот факт, что размеры матрицы также необходимо сохранять).

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

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

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

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

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

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

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

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

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

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

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

Формат CSR хранит разреженную матрицу $M \times 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]

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

{\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}

4 \times 4

В = [ 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=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 \times 6

В = [ 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$ в один массив и обрабатывает диагональ матрицы отдельно. ^[9]

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

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

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

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

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

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

SuiteSparse — набор алгоритмов разреженной матрицы, предназначенный для прямого решения разреженных линейных систем.
PETSc , большая библиотека C, содержащая множество различных решателей матриц для различных форматов хранения матриц.
Trilinos — большая библиотека C++ с подбиблиотеками, предназначенными для хранения плотных и разреженных матриц и решения соответствующих линейных систем.
Eigen3 — это библиотека C++, содержащая несколько решателей разреженных матриц. Однако ни один из них не распараллелен .
MUMPS ( MU ltifrontal Massively Parallel Sparse Direct Solver ), написанный на Fortran90, представляет собой фронтальный решатель .
Deal.II — библиотека конечных элементов, которая также имеет подбиблиотеку для разреженных линейных систем и их решений.
DUNE , еще одна библиотека конечных элементов, которая также имеет подбиблиотеку для разреженных линейных систем и их решений.
ПаСтикс.
СуперЛУ.
Armadillo предоставляет удобную оболочку C++ для BLAS и LAPACK.
SciPy обеспечивает поддержку нескольких форматов разреженных матриц, линейной алгебры и решателей.
SPArse Matrix (спам) Пакет R и Python для разреженных матриц.
Инструменты Wolfram Language для работы с разреженными массивами
ALGLIB — это библиотека C++ и C# с поддержкой разреженной линейной алгебры.
Библиотека ARPACK Fortran 77 для диагонализации и манипулирования разреженной матрицей с использованием алгоритма Арнольди.
SPARSE Reference (старый) пакет NIST для (реальной или комплексной) диагонализации разреженной матрицы
Библиотека SLEPc для решения крупномасштабных линейных систем и разреженных матриц.
Sympiler — генератор кода для конкретной предметной области и библиотека для решения линейных систем и задач квадратичного программирования.
scikit-learn , библиотека Python для машинного обучения , обеспечивает поддержку разреженных матриц и решателей.
sprs реализует разреженные матричные структуры данных и алгоритмы линейной алгебры на чистом Rust.
Базовая библиотека матриц (bml) поддерживает несколько форматов разреженных матриц и алгоритмы линейной алгебры с привязками для C, C++ и Fortran.
SPARSKIT Базовый набор инструментов для вычислений с разреженными матрицами от Университета Миннесоты.

История

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

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

Примечания

^ Аб Ян, Ди; Ву, Тао; Лю, Ин; Гао, Ян (2017). «Эффективное умножение разреженной матрицы в многоядерной системе». 17-я Международная конференция по коммуникационным технологиям (ICCT), IEEE, 2017 г. IEEE. стр. 1880–1883. дои : 10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. Вычислительное ядро DNN представляет собой умножение больших разреженных матриц. В области численного анализа разреженная матрица — это матрица, заполненная в основном нулями в качестве элементов таблицы. Напротив, если количество ненулевых элементов в матрице относительно велико, то ее обычно считают плотной матрицей. Доля нулевых элементов (ненулевых элементов) в матрице называется разреженностью (плотностью). Операции с использованием стандартных структур и алгоритмов плотной матрицы выполняются относительно медленно и потребляют большие объемы памяти при применении к большим разреженным матрицам.
^ «Cerebras Systems представляет первый в отрасли транзисторный чип на триллион» . www.businesswire.com . 19 августа 2019 г. Проверено 2 декабря 2019 г. WSE содержит 400 000 вычислительных ядер, оптимизированных для искусственного интеллекта. Вычислительные ядра, получившие название SLAC™ для разреженных ядер линейной алгебры, являются гибкими, программируемыми и оптимизированы для разреженной линейной алгебры, лежащей в основе всех вычислений нейронных сетей.
^ «Аргоннская национальная лаборатория внедряет Cerebras CS-1, самый быстрый в мире компьютер с искусственным интеллектом | Аргоннская национальная лаборатория» . www.anl.gov (пресс-релиз) . Проверено 2 декабря 2019 г. WSE — самый большой чип из когда-либо созданных, его площадь составляет 46 225 квадратных миллиметров, что в 56,7 раз больше, чем самый большой графический процессор. Он содержит в 78 раз больше вычислительных ядер, оптимизированных для искусственного интеллекта, в 3000 раз больше высокоскоростной встроенной памяти, в 10 000 раз большую пропускную способность памяти и в 33 000 раз большую пропускную способность связи.
^ См. scipy.sparse.dok_matrix.
^ См. scipy.sparse.lil_matrix.
^ См. scipy.sparse.coo_matrix.
^ Булуч, Айдын; Файнман, Джереми Т.; Фриго, Маттео; Гилберт, Джон Р.; Лейзерсон, Чарльз Э. (2009). Параллельное умножение разреженной матрицы-вектора и матрица-транспонирование-вектор с использованием сжатых разреженных блоков (PDF) . ACM симп. о параллелизме в алгоритмах и архитектурах. CiteSeerX 10.1.1.211.5256 .
^ Саад, Юсеф (2003). Итерационные методы для разреженных линейных систем . СИАМ.
^ Банк, Рэндольф Э.; Дуглас, Крейг К. (1993), «Пакет умножения разреженных матриц (SMMP)» (PDF) , Достижения в области вычислительной математики , 1 : 127–137, doi : 10.1007/BF02070824, S2CID 6412241
^ Айзенштат, Южная Каролина; Гурски, MC; Шульц, Миннесота; Шерман, AH (апрель 1977 г.). «Пакет Йельского университета с разреженной матрицей» (PDF) . Архивировано (PDF) из оригинала 6 апреля 2019 г. Проверено 6 апреля 2019 г.
^ Устное историческое интервью с Гарри М. Марковицем, стр. 9, 10.

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

Гиббс, Норман Э.; Пул, Уильям Г.; Стокмейер, Пол К. (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).

^ Саад, Юсеф (2003). Итерационные методы для разреженных линейных систем . СИАМ.