Участник:ZhenyaNikishkina - История изменений

ZhenyaNikishkina: Полностью удалено содержимое страницы

2023-10-28T22:09:14Z

Полностью удалено содержимое страницы

ZhenyaNikishkina в 21:16, 28 октября 2023

2023-10-28T21:16:46Z

← Предыдущая версия		Версия от 21:16, 28 октября 2023
Строка 111:		Строка 111:
	\end{pmatrix}</math>		\end{pmatrix}</math>

	Здесь ''indices'' - двумерный массив, в котором каждая строка содержит индексы столбцов ненулевых элементов соответствующей строки матрицы <math>A</math>. Если количество ненулевых элементов в строке меньше, чем максимальное количество для других строк, то оставшиеся значения дополняются специальным индексом(обычно -1). ''values''- двумерный массив такой же структуры, как и массив ''indices'', но он содержит сами ненулевые значения элементов матрицы <math>A</math>. Если строка содержит менее максимального количества ненулевых элементов, то оставшиеся значения в строке дополняются нулями.		Здесь ''indices'' - двумерный массив, в котором каждая строка содержит индексы столбцов ненулевых элементов соответствующей строки матрицы <math>A</math>. Если количество ненулевых элементов в строке меньше, чем максимальное количество для других строк, то оставшиеся значения дополняются специальным индексом(обычно -1). ''values'' - двумерный массив такой же структуры, как и массив ''indices'', но он содержит сами ненулевые значения элементов матрицы <math>A</math>. Если строка содержит менее максимального количества ненулевых элементов, то оставшиеся значения в строке дополняются нулями.

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

ZhenyaNikishkina в 21:15, 28 октября 2023

2023-10-28T21:15:35Z

← Предыдущая версия		Версия от 21:15, 28 октября 2023
Строка 75:		Строка 75:
	</source>		</source>

	'''diagonals''' =		''diagonals'' =
	<math display="block">\begin{pmatrix}		<math display="block">\begin{pmatrix}
	* & * & 0 & * \\		* & * & 0 & * \\
Строка 83:		Строка 83:
	\end{pmatrix}</math>		\end{pmatrix}</math>

	'''offsets''' =		''offsets'' =
	<math display="block">\begin{pmatrix}		<math display="block">\begin{pmatrix}
	-2 & -1 & 0 & 1		-2 & -1 & 0 & 1
Строка 120:		Строка 120:

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
			Формулы для перемножения матриц не зависят от их форматов, и операция умножения матриц всегда основана на стандартной формуле умножения матриц.
	Исходные данные: разреженная матрица <math>A</math> (элементы <math>a_{ij}</math>), разреженная матрица <math>B</math> (элементы <math>b_{ij}</math>).		Исходные данные: разреженная матрица <math>A</math> (элементы <math>a_{ij}</math>), разреженная матрица <math>B</math> (элементы <math>b_{ij}</math>).

Строка 130:		Строка 131:
	\end{align}		\end{align}
	</math>		</math>

	~~Существует также блочная версия метода, однако в данном описании разобран только точечный метод.~~

	== Литература ==		== Литература ==
	<references />		<references />

ZhenyaNikishkina: /* Свойства и структура алгоритмов */

2023-10-28T21:12:33Z

Свойства и структура алгоритмов

← Предыдущая версия		Версия от 21:12, 28 октября 2023
Строка 67:		Строка 67:

	DIA (Diagonal Storage) представление:		DIA (Diagonal Storage) представление:
	Поскольку матрица A содержит 4 диагонали с ненулевыми элементами, DIA представление будет включать только их:		Поскольку матрица A содержит 4 диагонали с ненулевыми элементами, DIA представление будет включать только их:
	Диагональ с индексом 1 (диагональ выше главной): [6, 0, 0];		<source lang="python">
	Диагональ с индексом 0 (главная диагональ): [0, 0, 2, 1];		Диагональ с индексом 1 (диагональ выше главной): [6, 0, 0];
	Диагональ с индексом -1 (диагональ ниже главной): [4, 0, 0];		Диагональ с индексом 0 (главная диагональ): [0, 0, 2, 1];
	Диагональ с индексом -2 (диагональ ниже главной): [0, 7]		Диагональ с индексом -1 (диагональ ниже главной): [4, 0, 0];
			Диагональ с индексом -2 (диагональ ниже главной): [0, 7].
			</source>

	~~<math>~~diagonals~~</math>~~ =		'''diagonals''' =
	<math display="block">\begin{pmatrix}		<math display="block">\begin{pmatrix}
	* & * & 0 & * \\		* & * & 0 & * \\
Строка 81:		Строка 83:
	\end{pmatrix}</math>		\end{pmatrix}</math>

	~~<math>~~offsets</math> ~~= [~~-2 -1 0 1]		'''offsets''' =
			<math display="block">\begin{pmatrix}
			-2 & -1 & 0 & 1
			\end{pmatrix}</math>

	Здесь ~~<math>~~diagonals~~</math>~~ - двумерный массив значений диагоналей матрицы <math> A</math> . Порядок следования диагоналей в массиве выбирается произвольно. ~~<math>~~offsets~~</math>~~ - одномерный массив, который указывает смещение каждой диагонали относительно главной диагонали. Положительные значения указывают на диагонали, расположенные выше главной, отрицательные значения - ниже главной.		Здесь ''diagonals'' - двумерный массив значений диагоналей матрицы <math> A</math> . Порядок следования диагоналей в массиве выбирается произвольно. ''offsets'' - одномерный массив, который указывает смещение каждой диагонали относительно главной диагонали. Положительные значения указывают на диагонали, расположенные выше главной, отрицательные значения - ниже главной.


Строка 90:		Строка 95:
	ELLPACK / ITPACK (ELL) представление определяется с использованием фиксированной длины массивов для строк матрицы. В данной матрице максимальное количество ненулевых элементов в строках равно 2 (для строки 4). Будем использовать массивы длины 2.		ELLPACK / ITPACK (ELL) представление определяется с использованием фиксированной длины массивов для строк матрицы. В данной матрице максимальное количество ненулевых элементов в строках равно 2 (для строки 4). Будем использовать массивы длины 2.

	~~<math>~~indices~~</math>~~ =		''indices'' =
	<math display="block">\begin{pmatrix}		<math display="block">\begin{pmatrix}
	1 & -1 \\		1 & -1 \\
Строка 98:		Строка 103:
	\end{pmatrix}</math>		\end{pmatrix}</math>

	~~<math>~~values~~</math>~~ =		''values'' =
	<math display="block">\begin{pmatrix}		<math display="block">\begin{pmatrix}
	6 & 0 \\		6 & 0 \\
Строка 106:		Строка 111:
	\end{pmatrix}</math>		\end{pmatrix}</math>

	Здесь ~~<math>~~indices~~</math>~~ - двумерный массив, в котором каждая строка содержит индексы столбцов ненулевых элементов соответствующей строки матрицы <math>A</math>. Если количество ненулевых элементов в строке меньше, чем максимальное количество для других строк, то оставшиеся значения дополняются специальным индексом(обычно -1). ~~<math>~~values~~</math>~~ - двумерный массив такой же структуры, как и массив ~~<math>~~indices~~</math>~~, но он содержит сами ненулевые значения элементов матрицы <math>A</math>. Если строка содержит менее максимального количества ненулевых элементов, то оставшиеся значения в строке дополняются нулями.		Здесь ''indices'' - двумерный массив, в котором каждая строка содержит индексы столбцов ненулевых элементов соответствующей строки матрицы <math>A</math>. Если количество ненулевых элементов в строке меньше, чем максимальное количество для других строк, то оставшиеся значения дополняются специальным индексом(обычно -1). ''values''- двумерный массив такой же структуры, как и массив ''indices'', но он содержит сами ненулевые значения элементов матрицы <math>A</math>. Если строка содержит менее максимального количества ненулевых элементов, то оставшиеся значения в строке дополняются нулями.

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


	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	'''Перемножение разреженных матриц''' - одна из задач в алгоритмах линейной алгебры, широко применяющаяся в различных методах.		'''Перемножение разреженных матриц''' - одна из задач в алгоритмах линейной алгебры, широко применяющаяся в различных методах.
	Здесь мы рассмотрим умножение <math>C = AB</math>  разреженных матриц (последовательный вещественный вариант)~~, в~~ реализации алгоритма ~~перемножения существенно будет использовано представление матрицы~~.		Здесь мы рассмотрим умножение <math>C = AB</math>  разреженных матриц (последовательный вещественный вариант). В реализации алгоритма умножения матриц, формат хранения разреженных матриц играет существенное значение для обеспечения эффективной производительности и оптимального использования ресурсов.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	Исходные данные: разреженная матрица <math>A</math> (элементы <math>a_{ij}</math>), разреженная матрица <math>B</math> (элементы <math>b_{ij}</math>).		Исходные данные: разреженная матрица <math>A</math> (элементы <math>a_{ij}</math>), разреженная матрица <math>B</math> (элементы <math>b_{ij}</math>).

	Вычисляемые данные: ~~плотная~~ матрица <math>C</math> (элементы <math>c_{ij}</math>).		Вычисляемые данные: разреженная матрица <math>C</math> (элементы <math>c_{ij}</math>).

	Формулы метода:		Формулы метода:
Строка 128:		Строка 132:

	Существует также блочная версия метода, однако в данном описании разобран только точечный метод.		Существует также блочная версия метода, однако в данном описании разобран только точечный метод.


	== Литература ==		== Литература ==
	<references />		<references />

ZhenyaNikishkina в 21:05, 28 октября 2023

2023-10-28T21:05:10Z

Внесённые изменения

ZhenyaNikishkina в 18:47, 28 октября 2023

2023-10-28T18:47:53Z

← Предыдущая версия		Версия от 18:47, 28 октября 2023
Строка 13:		Строка 13:
	В численном анализе и научных вычислениях '''разреженная матрица''' - это матрица, в которой большинство элементов равны нулю.<ref name="Yan Wu Liu Gao 2017 p. ">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.</ref> Не существует строгого определения доли элементов с нулевым значением для того, чтобы матрица считалась разреженной, но общим критерием является то, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов ненулевые, матрица считается '''плотной'''.<ref name="Yan Wu Liu Gao 2017 p. "/> Число элементов с нулевым значением, деленное на общее количество элементов (например, ''m'' × ''n'' для матрицы ''m'' × ''n''), иногда называют '''разреженностью матрицы'''.		В численном анализе и научных вычислениях '''разреженная матрица''' - это матрица, в которой большинство элементов равны нулю.<ref name="Yan Wu Liu Gao 2017 p. ">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.</ref> Не существует строгого определения доли элементов с нулевым значением для того, чтобы матрица считалась разреженной, но общим критерием является то, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов ненулевые, матрица считается '''плотной'''.<ref name="Yan Wu Liu Gao 2017 p. "/> Число элементов с нулевым значением, деленное на общее количество элементов (например, ''m'' × ''n'' для матрицы ''m'' × ''n''), иногда называют '''разреженностью матрицы'''.

	Концептуально разреженность соответствует системам с небольшим количеством попарных взаимодействий. Например, рассмотрим линию шариков, соединенных пружинами от одного к другому: это разреженная система, поскольку соединены только соседние шарики. Напротив, если бы одна и та же линия шариков имела пружины, соединяющие каждый шарик со всеми остальными шариками, система соответствовала бы плотной матрице. Концепция разреженности полезна в комбинаторике и прикладных областях, таких как теория сетей и численный анализ, которые обычно имеют низкую плотность значимых данных или соединений. Большие разреженные матрицы часто появляются в научных или инженерных приложениях при решении уравнений в частных производных. Разреженные матрицы встречаются при решении многих важных практических задач: структурного анализа, в теории графов, теории электрических сетей и энергосистем распределения энергии<ref>Тьюарсон Р. Разреженные матрицы. — М.: Мир, 1977.</ref>, при численном решении дифференциальных уравнений, математической физики, строительной механики, механики конструкций летательных и иных аппаратов; при прогнозировании метеорологических и гидрогеологических процессов<ref>Брумштейн Ю. М, Использование псеводогидродинамической постановки в задачах фильтрации со свободной поверхностью // Естественные науки. Астрахань: Издательский дом «Астраханский университет». — 2004. — № 8. — С. 125–128.</ref>; при обеспечении работы графических процессоров<ref>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.</ref>, а также при изучении статического равновесия физических, технических, биологических, производственно-экономических и других типов систем.<ref>Солнцева М. О., Кухаренко Б. Г. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики // Труды МФТИ. — 2013. — Т. 5, № 3(19). — С. 75–83.</ref>		Концептуально разреженность соответствует системам с небольшим количеством попарных взаимодействий. Например, рассмотрим линию шариков, соединенных пружинами от одного к другому: это разреженная система, поскольку соединены только соседние шарики. Напротив, если бы одна и та же линия шариков имела пружины, соединяющие каждый шарик со всеми остальными шариками, система соответствовала бы плотной матрице. Концепция разреженности полезна в комбинаторике и прикладных областях, таких как теория сетей и численный анализ, которые обычно имеют низкую плотность значимых данных или соединений. Большие разреженные матрицы часто появляются в научных или инженерных приложениях при решении уравнений в частных производных. Разреженные матрицы встречаются при решении многих важных практических задач: структурного анализа, в теории графов, теории электрических сетей и энергосистем распределения энергии<ref>Тьюарсон Р. Разреженные матрицы. — М.: Мир, 1977.</ref>, при численном решении дифференциальных уравнений, математической физики, строительной механики, механики конструкций летательных и иных аппаратов; при прогнозировании метеорологических и гидрогеологических процессов<ref>Брумштейн Ю. М, Использование псеводогидродинамической постановки в задачах фильтрации со свободной поверхностью // Естественные науки. Астрахань: Издательский дом «Астраханский университет». — 2004. — № 8. — С. 125–128.</ref>; при обеспечении работы графических процессоров<ref>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.</ref>, а также при изучении статического равновесия физических, технических, биологических, производственно-экономических и других типов систем.<ref>Солнцева М. О., Кухаренко Б. Г. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики // Труды МФТИ. — 2013. — Т. 5, № 3 (19). — С. 75–83.</ref>

	При хранении разреженных матриц и манипулировании ими на компьютере полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют преимущества разреженной структуры матрицы. Для разреженных матриц были созданы специализированные компьютеры<ref>~~{{Cite web\|url=~~https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-~~Industry%E2%80%99s~~-Trillion-Transistor-Chip~~\|title=~~Cerebras Systems Unveils the Industry's First Trillion Transistor Chip\| quote=The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation\|date=2019-08-19 \|website=www.businesswire.com\|language=en\|access-date=2019-12-02}}</ref>, поскольку они широко распространены в области машинного обучения.<ref>~~{{Cite press release\|url=~~https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer~~\|title=~~Argonne ~~National Laboratory Deploys Cerebras CS-1,~~ the World's Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory\|quote=The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.\| website=www.anl.gov\|language=en\|access-date=2019-12-02}}</ref> Операции, использующие стандартные структуры и алгоритмы с плотной матрицей, являются медленными и неэффективными при применении к большим разреженным матрицам, поскольку обработка и память тратятся впустую на нули. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньшего объема памяти. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов с плотной матрицей.		При хранении разреженных матриц и манипулировании ими на компьютере полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют преимущества разреженной структуры матрицы. Для разреженных матриц были созданы специализированные компьютеры<ref> [https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-Industry’s-Trillion-Transistor-Chip. Cerebras Systems Unveils the Industry's First Trillion Transistor Chip]</ref>, поскольку они широко распространены в области машинного обучения.<ref>[https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer. Argonne national laboratory deploys cerebras cs1 the worlds fastest artificial intelligence computer]</ref> Операции, использующие стандартные структуры и алгоритмы с плотной матрицей, являются медленными и неэффективными при применении к большим разреженным матрицам, поскольку обработка и память тратятся впустую на нули. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньшего объема памяти. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов с плотной матрицей.

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

			1. '''Список списков''' (List of Lists, LIL): В этом представлении разреженной матрицы каждая строка матрицы хранится в виде списка, содержащего пары (индекс столбца, значение). Этот формат удобен для построения и модификации разреженных матриц, но может быть неэффективным для матричных операций.

			2. '''Сжатое представление по строкам''' (Compressed Sparse Row, CSR) / '''Сжатое представление по столбцам''' (Compressed Sparse Column, CSC): В CSR и CSC форматах разреженная матрица представляется с помощью трех одномерных массивов: значения (non-zero values), индексы столбцов (column indices) и указатели на начало каждой строки (row pointers) для CSR или указатели на начало каждого столбца (column pointers) для CSC. Эти форматы являются наиболее распространенными и эффективными для матричных операций, таких как сложение, умножение и транспонирование.

			3. '''Координатный формат''' (COO, Coordinate List): В координатном формате каждый ненулевой элемент матрицы представляется с помощью трех значений: индекс строки, индекс столбца и значение элемента. Этот формат удобен для добавления и изучения элементов, но менее эффективен для выполнения матричных операций по сравнению с CSR и CSC.

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

			5. '''ELLPACK / ITPACK представление''' (ELLPACK / ITPACK, ELL): В ELLPACK / ITPACK формате каждая строка матрицы представлена вектором фиксированной длины, содержащим значения и индексы столбцов L наиболее длинных строк, остальные элементы дополняются нулями. Это делает этот формат легко параллелизуемым на графических процессорах, но он может быть неэффективным, если разница в количестве ненулевых элементов между самой длинной и самой короткой строками слишком велика.

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

ZhenyaNikishkina в 18:35, 28 октября 2023

2023-10-28T18:35:15Z

← Предыдущая версия		Версия от 18:35, 28 октября 2023
Строка 13:		Строка 13:
	В численном анализе и научных вычислениях '''разреженная матрица''' - это матрица, в которой большинство элементов равны нулю.<ref name="Yan Wu Liu Gao 2017 p. ">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.</ref> Не существует строгого определения доли элементов с нулевым значением для того, чтобы матрица считалась разреженной, но общим критерием является то, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов ненулевые, матрица считается '''плотной'''.<ref name="Yan Wu Liu Gao 2017 p. "/> Число элементов с нулевым значением, деленное на общее количество элементов (например, ''m'' × ''n'' для матрицы ''m'' × ''n''), иногда называют '''разреженностью матрицы'''.		В численном анализе и научных вычислениях '''разреженная матрица''' - это матрица, в которой большинство элементов равны нулю.<ref name="Yan Wu Liu Gao 2017 p. ">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.</ref> Не существует строгого определения доли элементов с нулевым значением для того, чтобы матрица считалась разреженной, но общим критерием является то, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов ненулевые, матрица считается '''плотной'''.<ref name="Yan Wu Liu Gao 2017 p. "/> Число элементов с нулевым значением, деленное на общее количество элементов (например, ''m'' × ''n'' для матрицы ''m'' × ''n''), иногда называют '''разреженностью матрицы'''.

	Концептуально разреженность соответствует системам с небольшим количеством попарных взаимодействий. Например, рассмотрим линию шариков, соединенных пружинами от одного к другому: это разреженная система, поскольку соединены только соседние шарики. Напротив, если бы одна и та же линия шариков имела пружины, соединяющие каждый шарик со всеми остальными шариками, система соответствовала бы плотной матрице. Концепция разреженности полезна в комбинаторике и прикладных областях, таких как теория сетей и численный анализ, которые обычно имеют низкую плотность значимых данных или соединений. Большие разреженные матрицы часто появляются в научных или инженерных приложениях при решении уравнений в частных производных. Разреженные матрицы встречаются при решении многих важных практических задач: структурного анализа, в теории графов, теории электрических сетей и энергосистем распределения энергии<ref>Тьюарсон Р. Разреженные матрицы. — М.: Мир, 1977.</ref>, при численном решении дифференциальных уравнений, математической физики, строительной механики, механики конструкций летательных и иных аппаратов; при прогнозировании метеорологических и гидрогеологических процессов<ref>Брумштейн Ю. М, Использование псеводогидродинамической постановки в задачах фильтрации со свободной поверхностью // Естественные науки. Астрахань: Издательский дом «Астраханский университет». — 2004. — № 8. — С.125–128.</ref>; при обеспечении работы графических процессоров<ref>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.</ref>, а также при изучении статического равновесия физических, технических, биологических, производственно-экономических и других типов систем.<ref>Солнцева М. О., Кухаренко Б. Г. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики // Труды МФТИ. — 2013. — Т.5, № 3(19). — С.75–83.</ref>		Концептуально разреженность соответствует системам с небольшим количеством попарных взаимодействий. Например, рассмотрим линию шариков, соединенных пружинами от одного к другому: это разреженная система, поскольку соединены только соседние шарики. Напротив, если бы одна и та же линия шариков имела пружины, соединяющие каждый шарик со всеми остальными шариками, система соответствовала бы плотной матрице. Концепция разреженности полезна в комбинаторике и прикладных областях, таких как теория сетей и численный анализ, которые обычно имеют низкую плотность значимых данных или соединений. Большие разреженные матрицы часто появляются в научных или инженерных приложениях при решении уравнений в частных производных. Разреженные матрицы встречаются при решении многих важных практических задач: структурного анализа, в теории графов, теории электрических сетей и энергосистем распределения энергии<ref>Тьюарсон Р. Разреженные матрицы. — М.: Мир, 1977.</ref>, при численном решении дифференциальных уравнений, математической физики, строительной механики, механики конструкций летательных и иных аппаратов; при прогнозировании метеорологических и гидрогеологических процессов<ref>Брумштейн Ю. М, Использование псеводогидродинамической постановки в задачах фильтрации со свободной поверхностью // Естественные науки. Астрахань: Издательский дом «Астраханский университет». — 2004. — № 8. — С. 125–128.</ref>; при обеспечении работы графических процессоров<ref>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.</ref>, а также при изучении статического равновесия физических, технических, биологических, производственно-экономических и других типов систем.<ref>Солнцева М. О., Кухаренко Б. Г. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики // Труды МФТИ. — 2013. — Т. 5, № 3(19). — С. 75–83.</ref>

	При хранении разреженных матриц и манипулировании ими на компьютере полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют преимущества разреженной структуры матрицы. Для разреженных матриц были созданы специализированные компьютеры<ref>{{Cite web\|url=https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-Industry%E2%80%99s-Trillion-Transistor-Chip\|title=Cerebras Systems Unveils the Industry's First Trillion Transistor Chip\| quote=The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation\|date=2019-08-19 \|website=www.businesswire.com\|language=en\|access-date=2019-12-02}}</ref>, поскольку они широко распространены в области машинного обучения.<ref>{{Cite press release\|url=https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer\|title=Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory\|quote=The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.\| website=www.anl.gov\|language=en\|access-date=2019-12-02}}</ref> Операции, использующие стандартные структуры и алгоритмы с плотной матрицей, являются медленными и неэффективными при применении к большим разреженным матрицам, поскольку обработка и память тратятся впустую на нули. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньшего объема памяти. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов с плотной матрицей.		При хранении разреженных матриц и манипулировании ими на компьютере полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют преимущества разреженной структуры матрицы. Для разреженных матриц были созданы специализированные компьютеры<ref>{{Cite web\|url=https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-Industry%E2%80%99s-Trillion-Transistor-Chip\|title=Cerebras Systems Unveils the Industry's First Trillion Transistor Chip\| quote=The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation\|date=2019-08-19 \|website=www.businesswire.com\|language=en\|access-date=2019-12-02}}</ref>, поскольку они широко распространены в области машинного обучения.<ref>{{Cite press release\|url=https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer\|title=Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory\|quote=The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.\| website=www.anl.gov\|language=en\|access-date=2019-12-02}}</ref> Операции, использующие стандартные структуры и алгоритмы с плотной матрицей, являются медленными и неэффективными при применении к большим разреженным матрицам, поскольку обработка и память тратятся впустую на нули. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньшего объема памяти. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов с плотной матрицей.

ZhenyaNikishkina: Новая страница: «{{algorithm | name = Умножение разреженных матриц | serial_complexity = | pf_height = | pf_width = | in...»

2023-10-28T18:32:09Z

Новая страница: «{{algorithm | name = Умножение разреженных матриц | serial_complexity = | pf_height = | pf_width = | in...»

Новая страница

{{algorithm
| name = Умножение разреженных матриц
| serial_complexity =
| pf_height =
| pf_width =
| input_data =
| output_data =
}}

Основные авторы описания: [[Участник:ZhenyaNikishkina|Е.Г.Никишкина]]

В численном анализе и научных вычислениях '''разреженная матрица''' - это матрица, в которой большинство элементов равны нулю.<ref name="Yan Wu Liu Gao 2017 p. ">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.</ref> Не существует строгого определения доли элементов с нулевым значением для того, чтобы матрица считалась разреженной, но общим критерием является то, что количество ненулевых элементов примерно равно количеству строк или столбцов. Напротив, если большинство элементов ненулевые, матрица считается '''плотной'''.<ref name="Yan Wu Liu Gao 2017 p. "/> Число элементов с нулевым значением, деленное на общее количество элементов (например, ''m'' × ''n'' для матрицы ''m'' × ''n''), иногда называют '''разреженностью матрицы'''.

Концептуально разреженность соответствует системам с небольшим количеством попарных взаимодействий. Например, рассмотрим линию шариков, соединенных пружинами от одного к другому: это разреженная система, поскольку соединены только соседние шарики. Напротив, если бы одна и та же линия шариков имела пружины, соединяющие каждый шарик со всеми остальными шариками, система соответствовала бы плотной матрице. Концепция разреженности полезна в комбинаторике и прикладных областях, таких как теория сетей и численный анализ, которые обычно имеют низкую плотность значимых данных или соединений. Большие разреженные матрицы часто появляются в научных или инженерных приложениях при решении уравнений в частных производных. Разреженные матрицы встречаются при решении многих важных практических задач: структурного анализа, в теории графов, теории электрических сетей и энергосистем распределения энергии<ref>Тьюарсон Р. Разреженные матрицы. — М.: Мир, 1977.</ref>, при численном решении дифференциальных уравнений, математической физики, строительной механики, механики конструкций летательных и иных аппаратов; при прогнозировании метеорологических и гидрогеологических процессов<ref>Брумштейн Ю. М, Использование псеводогидродинамической постановки в задачах фильтрации со свободной поверхностью // Естественные науки. Астрахань: Издательский дом «Астраханский университет». — 2004. — № 8. — С.125–128.</ref>; при обеспечении работы графических процессоров<ref>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.</ref>, а также при изучении статического равновесия физических, технических, биологических, производственно-экономических и других типов систем.<ref>Солнцева М. О., Кухаренко Б. Г. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики // Труды МФТИ. — 2013. — Т.5, № 3(19). — С.75–83.</ref>

При хранении разреженных матриц и манипулировании ими на компьютере полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют преимущества разреженной структуры матрицы. Для разреженных матриц были созданы специализированные компьютеры<ref>{{Cite web|url=https://www.businesswire.com/news/home/20190819005148/en/Cerebras-Systems-Unveils-Industry%E2%80%99s-Trillion-Transistor-Chip|title=Cerebras Systems Unveils the Industry's First Trillion Transistor Chip| quote=The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation|date=2019-08-19 |website=www.businesswire.com|language=en|access-date=2019-12-02}}</ref>, поскольку они широко распространены в области машинного обучения.<ref>{{Cite press release|url=https://www.anl.gov/article/argonne-national-laboratory-deploys-cerebras-cs1-the-worlds-fastest-artificial-intelligence-computer|title=Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory|quote=The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.| website=www.anl.gov|language=en|access-date=2019-12-02}}</ref> Операции, использующие стандартные структуры и алгоритмы с плотной матрицей, являются медленными и неэффективными при применении к большим разреженным матрицам, поскольку обработка и память тратятся впустую на нули. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньшего объема памяти. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов с плотной матрицей.

== Свойства и структура алгоритмов ==

=== Общее описание алгоритма ===
'''Перемножение разреженных матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
Здесь мы рассмотрим умножение <math>C = AB</math>  разреженных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>.

=== Математическое описание алгоритма ===
Исходные данные: плотная матрица <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>

Существует также блочная версия метода, однако в данном описании разобран только точечный метод.

== Литература ==
<references />