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

Пример разреженной матрицы $\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%.

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

Хранение [ править ]

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

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

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

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

Словарь ключей (DOK) [ править ]

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

с 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

(24 элемента) с 8 ненулевыми элементами, поэтому

В = [ 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 функция).

Программное обеспечение [ править ]

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

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]

См. также [ править ]

Примечания [ править ]

^ Перейти обратно: ^а ^б Ян, Ди; Ву, Тао; Лю, Ин; Гао, Ян (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.

Ссылки [ править ]

Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (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, Национальная геодезическая служба, Роквилл, Мэриленд. ^[1]
Дженнифер Скотт и Мирослав Тума: «Алгоритмы для разреженных линейных систем», Биркхаузер, (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).

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

[Yan_Wu_Liu_Gao_2017_p.-1] Перейти обратно: ^а ^б Ян, Ди; Ву, Тао; Лю, Ин; Гао, Ян (2017). «Эффективное умножение разреженной матрицы в многоядерной системе». 17-я Международная конференция по коммуникационным технологиям (ICCT) , IEEE, 2017 г. IEEE. стр. 1880–1883. дои : 10.1109/icct.2017.8359956 . ISBN 978-1-5090-3944-9 . Вычислительное ядро DNN представляет собой умножение больших разреженных матриц. В области численного анализа разреженная матрица — это матрица, заполненная в основном нулями в качестве элементов таблицы. Напротив, если количество ненулевых элементов в матрице относительно велико, то ее обычно считают плотной матрицей. Доля нулевых элементов (ненулевых элементов) в матрице называется разреженностью (плотностью). Операции с использованием стандартных структур и алгоритмов плотной матрицы выполняются относительно медленно и потребляют большие объемы памяти при применении к большим разреженным матрицам.

[2] «Cerebras Systems представляет первый в отрасли транзисторный чип-триллион» . www.businesswire.com . 19 августа 2019 г. Проверено 2 декабря 2019 г. WSE содержит 400 000 вычислительных ядер, оптимизированных для искусственного интеллекта. Вычислительные ядра, получившие название SLAC™ для разреженных ядер линейной алгебры, являются гибкими, программируемыми и оптимизированы для разреженной линейной алгебры, лежащей в основе всех вычислений нейронных сетей.

[3] «Аргоннская национальная лаборатория внедряет Cerebras CS-1, самый быстрый в мире компьютер с искусственным интеллектом | Аргоннская национальная лаборатория» . www.anl.gov (пресс-релиз) . Проверено 2 декабря 2019 г. 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] Айзенштат, Южная Каролина; Гурски, MC; Шульц, Миннесота; Шерман, AH (апрель 1977 г.). «Пакет Йельского университета с разреженной матрицей» (PDF) . Архивировано (PDF) из оригинала 6 апреля 2019 г. Проверено 6 апреля 2019 г.

[11] Устное историческое интервью с Гарри М. Марковицем , стр. 9, 10.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[1]

v т Это Структуры данных
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

v т Это Матричные классы
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Carleman Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
Mathematics portal List of matrices Category:Matrices

v т Это Численная линейная алгебра
Key concepts	Floating point Numerical stability
Problems	System of linear equations Matrix decompositions Matrix multiplication (algorithms) Matrix splitting Sparse problems
Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing
Software	ATLAS MATLAB Basic Linear Algebra Subprograms (BLAS) LAPACK Specialized libraries General purpose software