Участник:ZhenyaNikishkina
| Умножение разреженных матриц |
Основные авторы описания: Е.Г.Никишкина
В численном анализе и научных вычислениях разреженная матрица - это матрица, в которой большинство элементов равны нулю.[1] Не существует строгого определения доли элементов с нулевым значением для того, чтобы матрица считалась разреженной, но общим критерием является то, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов ненулевые, матрица считается плотной.[1] Число элементов с нулевым значением, деленное на общее количество элементов (например, m × n для матрицы m × n), иногда называют разреженностью матрицы.
Концептуально разреженность соответствует системам с небольшим количеством попарных взаимодействий. Например, рассмотрим линию шариков, соединенных пружинами от одного к другому: это разреженная система, поскольку соединены только соседние шарики. Напротив, если бы одна и та же линия шариков имела пружины, соединяющие каждый шарик со всеми остальными шариками, система соответствовала бы плотной матрице. Концепция разреженности полезна в комбинаторике и прикладных областях, таких как теория сетей и численный анализ, которые обычно имеют низкую плотность значимых данных или соединений. Большие разреженные матрицы часто появляются в научных или инженерных приложениях при решении уравнений в частных производных. Разреженные матрицы встречаются при решении многих важных практических задач: структурного анализа, в теории графов, теории электрических сетей и энергосистем распределения энергии[2], при численном решении дифференциальных уравнений, математической физики, строительной механики, механики конструкций летательных и иных аппаратов; при прогнозировании метеорологических и гидрогеологических процессов[3]; при обеспечении работы графических процессоров[4], а также при изучении статического равновесия физических, технических, биологических, производственно-экономических и других типов систем.[5]
При хранении разреженных матриц и манипулировании ими на компьютере полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют преимущества разреженной структуры матрицы. Для разреженных матриц были созданы специализированные компьютеры[6], поскольку они широко распространены в области машинного обучения.[7] Операции, использующие стандартные структуры и алгоритмы с плотной матрицей, являются медленными и неэффективными при применении к большим разреженным матрицам, поскольку обработка и память тратятся впустую на нули. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньшего объема памяти. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов с плотной матрицей.
Содержание
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Перемножение разреженных матриц - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. Здесь мы рассмотрим умножение [math]C = AB[/math] разреженных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения[8].
1.2 Математическое описание алгоритма
Исходные данные: плотная матрица [math]A[/math] (элементы [math]a_{ij}[/math]), плотная матрица [math]B[/math] (элементы [math]b_{ij}[/math]).
Вычисляемые данные: плотная матрица [math]C[/math] (элементы [math]c_{ij}[/math]).
Формулы метода:
- [math] \begin{align} c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad j \in [1, l]. \end{align} [/math]
Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
2 Литература
- ↑ 1,0 1,1 Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). "An efficient sparse-dense matrix multiplication on a multicore system". 2017 IEEE 17th International Conference on Communication Technology (ICCT). IEEE. pp. 1880–1883. doi:10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9.
- ↑ Тьюарсон Р. Разреженные матрицы. — М.: Мир, 1977.
- ↑ Брумштейн Ю. М, Использование псеводогидродинамической постановки в задачах фильтрации со свободной поверхностью // Естественные науки. Астрахань: Издательский дом «Астраханский университет». — 2004. — № 8. — С.125–128.
- ↑ Dehnavi M. M., Fernández D. M., Giannacopoulos D. Finite-element sparse matrix vector multiplication on graphic processing units // IEEE Transactions on Magnetics. — 2010. — Vol.46, № 8. — P.2982–2985.
- ↑ Солнцева М. О., Кухаренко Б. Г. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики // Труды МФТИ. — 2013. — Т.5, № 3(19). — С.75–83.
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite press release
- ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
