Прямая подстановка (вещественный вариант) - История изменений

ASA в 06:48, 18 июля 2022

2022-07-18T06:48:49Z

← Предыдущая версия		Версия от 06:48, 18 июля 2022
Строка 8:		Строка 8:
	}}		}}

	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]]		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]].

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

ASA в 06:47, 18 июля 2022

2022-07-18T06:47:09Z

← Предыдущая версия		Версия от 06:47, 18 июля 2022
Строка 8:		Строка 8:
	}}		}}

	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]]

	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==
Строка 153:		Строка 153:
	</source>		</source>
	При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.		При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

	~~=== Локальность данных и вычислений ===~~
	~~==== Локальность реализации алгоритма ====~~
	~~===== Структура обращений в память и качественная оценка локальности =====~~

	~~===== Количественная оценка локальности =====~~

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== ~~Масштабируемость алгоритма и его реализации~~ ===		=== Результаты прогонов ===
	~~==== Масштабируемость алгоритма ====~~
	~~==== Масштабируемость реализации алгоритма ====~~

	~~=== Динамические характеристики и эффективность реализации алгоритма ===~~

	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

	~~=== Существующие реализации алгоритма ===~~

	== Литература ==		== Литература ==

Frolov в 11:10, 17 сентября 2015

2015-09-17T11:10:05Z

← Предыдущая версия		Версия от 11:10, 17 сентября 2015
Строка 1:		Строка 1:
			{{algorithm
			\| name = Прямая подстановка для нижней треугольной матрицы с единичной диагональю
			\| serial_complexity = <math>O(n^2)</math>
			\| pf_height = <math>O(n)</math>
			\| pf_width = <math>O(n)</math>
			\| input_data = <math>O(n^2)</math>
			\| output_data = <math>n</math>
			}}

	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])

Строка 5:		Строка 14:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	'''Прямая подстановка''' - решение СЛАУ <math>Lx = y</math> с ~~левой~~ треугольной матрицей <math>L</math>. Матрица <math>L</math> - одна из составляющих матрицы <math>A</math> и получается либо из <math>LU</math>-разложения последней каким-либо из многочисленных способов (например, простое разложение Гаусса, разложение Гаусса с выбором ведущего элемента, компактная схема Гаусса), либо из других разложений. В силу треугольности <math>L</math> решение СЛАУ является одной из модификаций общего метода подстановки и записывается простыми формулами.		'''Прямая подстановка''' - решение СЛАУ <math>Lx = y</math> с нижней треугольной матрицей <math>L</math>. Матрица <math>L</math> - одна из составляющих матрицы <math>A</math> и получается либо из <math>LU</math>-разложения последней каким-либо из многочисленных способов (например, простое разложение Гаусса, разложение Гаусса с выбором ведущего элемента, компактная схема Гаусса), либо из других разложений. В силу треугольности <math>L</math> решение СЛАУ является одной из модификаций общего метода подстановки и записывается простыми формулами.

	В<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984, стр. 182.</ref> метод решения СЛАУ с ''левой треугольной матрицей'' назван методом '''обратной подстановки'''. Там же отмечено, что в литературе иногда под ''обратной подстановкой'' имеют в виду, как и здесь, только решения СЛАУ с ''правой треугольной матрицей'', а решение ''левых'' треугольных систем называют прямой подстановкой. Такой же системы названий будем придерживаться и мы, во избежание одноимённого названия разных алгоритмов. Кроме того, [[Обратная подстановка (вещественный вариант)\|обратная подстановка]], представленная в этой энциклопедии алгоритмов, одновременно является частью '''метода Гаусса для решения СЛАУ''', а именно - его '''обратным ходом''', чего нельзя сказать про представленную здесь прямую подстановку.		В<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984, стр. 182.</ref> метод решения СЛАУ с ''левой треугольной матрицей'' назван методом '''обратной подстановки'''. Там же отмечено, что в литературе иногда под ''обратной подстановкой'' имеют в виду, как и здесь, только решения СЛАУ с ''правой треугольной матрицей'', а решение ''левых'' треугольных систем называют прямой подстановкой. Такой же системы названий будем придерживаться и мы, во избежание одноимённого названия разных алгоритмов. Кроме того, [[Обратная подстановка (вещественный вариант)\|обратная подстановка]], представленная в этой энциклопедии алгоритмов, одновременно является частью '''метода Гаусса для решения СЛАУ''', а именно - его '''обратным ходом''', чего нельзя сказать про представленную здесь прямую подстановку.

	Общая структура прямой подстановки с неособенной ~~левой~~ треугольной матрицей, тем не менее, практически полностью совпадает со структурой [[Обратная подстановка (вещественный вариант)\|обратной подстановки]]. Поэтому здесь мы рассмотрим случай, когда матрица <math>L</math>, как полученная из разложения типа Гаусса, имеет единичные диагональные элементы.		Общая структура прямой подстановки с неособенной нижней треугольной матрицей, тем не менее, практически полностью совпадает со структурой [[Обратная подстановка (вещественный вариант)\|обратной подстановки]]. Поэтому здесь мы рассмотрим случай, когда матрица <math>L</math>, как полученная из разложения типа Гаусса, имеет единичные диагональные элементы.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

	Исходные данные: ~~левая~~ треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).		Исходные данные: нижняя треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).

	Вычисляемые данные: вектор решения <math>y</math> (элементы <math>y_{i}</math>).		Вычисляемые данные: вектор решения <math>y</math> (элементы <math>y_{i}</math>).
Строка 112:		Строка 121:
	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

	'''Входные данные''': ~~левая~~ треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).		'''Входные данные''': нижняя треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).

	'''Объём входных данных''': <math>\frac{n (n + 1)}{2}</math> (в силу треугольности и единичности диагональных элементов достаточно хранить только поддиагональные элементы матрицы <math>L</math>).		'''Объём входных данных''': <math>\frac{n (n + 1)}{2}</math> (в силу треугольности и единичности диагональных элементов достаточно хранить только поддиагональные элементы матрицы <math>L</math>).

ASA в 13:56, 28 июля 2015

2015-07-28T13:56:10Z

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

ASA в 13:26, 23 июля 2015

2015-07-23T13:26:33Z

← Предыдущая версия		Версия от 13:26, 23 июля 2015
Строка 217:		Строка 217:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			== Литература ==

	[[En:Forward substitution]]		[[En:Forward substitution]]

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

ASA в 12:39, 23 июля 2015

2015-07-23T12:39:48Z

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

ASA в 12:06, 22 июля 2015

2015-07-22T12:06:15Z

← Предыдущая версия		Версия от 12:06, 22 июля 2015
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]], [[Участник:VadimVV\|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений\|раздел 2.2]]), [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.4]])

	== ~~Описание свойств~~ и ~~структуры~~ алгоритма ==		== Свойства и структура алгоритма ==

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
Строка 11:		Строка 11:
	Общая структура прямой подстановки с неособенной левой треугольной матрицей, тем не менее, практически полностью совпадает со структурой [[Обратная подстановка (вещественный вариант)\|обратной подстановки]]. Поэтому здесь мы рассмотрим случай, когда матрица <math>L</math>, как полученная из разложения типа Гаусса, имеет единичные диагональные элементы.		Общая структура прямой подстановки с неособенной левой треугольной матрицей, тем не менее, практически полностью совпадает со структурой [[Обратная подстановка (вещественный вариант)\|обратной подстановки]]. Поэтому здесь мы рассмотрим случай, когда матрица <math>L</math>, как полученная из разложения типа Гаусса, имеет единичные диагональные элементы.

	=== Математическое описание ===		=== Математическое описание алгоритма ===

	Исходные данные: левая треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).		Исходные данные: левая треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).
Строка 51:		Строка 51:
	в режиме накопления или без него.		в режиме накопления или без него.

	=== ~~Описание схемы~~ реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===

	Чтобы понять последовательность исполнения, перепишем формулы метода так:		Чтобы понять последовательность исполнения, перепишем формулы метода так:
Строка 100:		Строка 100:
	Описанный граф можно посмотреть на рисунке, выполненном для случая <math>n = 5</math>. Здесь вершины обозначены зелёным цветом. Подача входных данных из вектора <math>b</math>, идущая в вершины левого столбца, и матрицы <math>L</math>, идущая во все вершины, на рисунке не представлена.		Описанный граф можно посмотреть на рисунке, выполненном для случая <math>n = 5</math>. Здесь вершины обозначены зелёным цветом. Подача входных данных из вектора <math>b</math>, идущая в вершины левого столбца, и матрицы <math>L</math>, идущая во все вершины, на рисунке не представлена.

	=== ~~Описание ресурса~~ параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Для прямой подстановки порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:		Для прямой подстановки порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:
Строка 110:		Строка 110:
	При классификации по высоте ЯПФ, таким образом, метод прямой подстановки относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''линейной''.		При классификации по высоте ЯПФ, таким образом, метод прямой подстановки относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''линейной''.

	=== ~~Описание входных~~ и ~~выходных данных~~ ===		=== Входные и выходные данные алгоритма ===

	'''Входные данные''': левая треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).		'''Входные данные''': левая треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).
Строка 128:		Строка 128:
	При этом алгоритм прямой подстановки полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается, поскольку в корне меняет структуру алгоритма и делает параллельную сложность квадратической.		При этом алгоритм прямой подстановки полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается, поскольку в корне меняет структуру алгоритма и делает параллельную сложность квадратической.

	== Программная реализация ==		== Программная реализация алгоритма ==

	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===
Строка 145:		Строка 145:
	При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.		При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

	=== ~~Описание локальности~~ данных и вычислений ===		=== Локальность данных и вычислений ===
	==== ~~Описание локальности~~ реализации алгоритма ====		==== Локальность реализации алгоритма ====
	===== ~~Описание структуры~~ обращений в память и качественная оценка локальности =====		===== Структура обращений в память и качественная оценка локальности =====

	[[file:gauss forward 1.PNG\|thumb\|center\|700px\|Рисунок 12.1. Прямой ход метода Гаусса решения СЛАУ. Общий профиль обращений в память]]		[[file:gauss forward 1.PNG\|thumb\|center\|700px\|Рисунок 12.1. Прямой ход метода Гаусса решения СЛАУ. Общий профиль обращений в память]]
Строка 193:		Строка 193:
	[[file:gauss forward cvg.PNG\|thumb\|center\|700px\|Рисунок 12.6. Сравнение значений оценки cvg]]		[[file:gauss forward cvg.PNG\|thumb\|center\|700px\|Рисунок 12.6. Сравнение значений оценки cvg]]

	=== Возможные способы и особенности реализации ~~параллельного~~ алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	==== ~~Описание масштабируемости~~ алгоритма ====		==== Масштабируемость алгоритма ====
	==== ~~Описание масштабируемости~~ реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
	[[file:Масштабируемость параллельной реализации метода Гаусса Производительность.png\|thumb\|center\|700px\|Рисунок 1. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная производительность. ]]		[[file:Масштабируемость параллельной реализации метода Гаусса Производительность.png\|thumb\|center\|700px\|Рисунок 1. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная производительность. ]]
	[[file:Масштабируемость метод Гаусса.png\|thumb\|center\|700px\|Рисунок 2. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная эффективность. ]]		[[file:Масштабируемость метод Гаусса.png\|thumb\|center\|700px\|Рисунок 2. Масштабируемость параллельной реализации метода Гаусса (прямой ход) Максимальная эффективность. ]]
Строка 213:		Строка 213:

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

ASA: /* Описание масштабируемости реализации алгоритма */

2015-07-22T07:27:14Z

Описание масштабируемости реализации алгоритма

← Предыдущая версия		Версия от 07:27, 22 июля 2015
Строка 206:		Строка 206:
	* Максимальная эффективность 6.65%		* Максимальная эффективность 6.65%
	Оценка масштабируемости		Оценка масштабируемости
	* По числу процессов: -0.000101 – при увеличении числа процессов эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении ~~числа процессов~~. Учитывая разницу между максимальным и минимальным значением эффективности в 6,5% можно сделать вывод, что на рассмотренной области снижение эффективности, скорее всего, достаточно равномерное. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Могут присутствовать области возрастания эффективности, на всех рассмотренных размерах матрицы. Это может объясняться увеличением вычислительной сложности задачи, что при постоянных накладных расходах на организацию параллельного взаимодействия приводит к общему увеличению эффективности работы.		* По числу процессов: -0.000101 – при увеличении числа процессов эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении размера задачи. Учитывая разницу между максимальным и минимальным значением эффективности в 6,5% можно сделать вывод, что на рассмотренной области снижение эффективности, скорее всего, достаточно равномерное. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Могут присутствовать области возрастания эффективности, на всех рассмотренных размерах матрицы. Это может объясняться увеличением вычислительной сложности задачи, что при постоянных накладных расходах на организацию параллельного взаимодействия приводит к общему увеличению эффективности работы.
	* По размеру задачи:-0.00674– при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области. Это может свидетельствовать о том, что при увеличении размера задачи возрастают и накладные расходы на организацию параллельного взаимодействия. Так как интенсивность снижения эффективности по этому направлению выше, чем по направлению числа процессов, скорее всего падение интенсивности значительно при малом числе процессов более интенсивное, чем в присутствующих областях возрастания эффективности при большом числе процессов.		* По размеру задачи:-0.00674– при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области. Это может свидетельствовать о том, что при увеличении размера задачи возрастают и накладные расходы на организацию параллельного взаимодействия. Так как интенсивность снижения эффективности по этому направлению выше, чем по направлению числа процессов, скорее всего падение интенсивности значительно при малом числе процессов более интенсивное, чем в присутствующих областях возрастания эффективности при большом числе процессов.
	* По двум направлениям: -6.621e-05 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности очень мала. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 6,5 % говорит о том, что если на поверхности присутствуют области с очень интенсивным изменением эффективности, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.		* По двум направлениям: -6.621e-05 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, однако интенсивность уменьшения эффективности очень мала. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 6,5 % говорит о том, что если на поверхности присутствуют области с очень интенсивным изменением эффективности, но очень малые по площади. На остальной поверхности изменения эффективности незначительны и находятся на приблизительно одном и том же уровне.

ASA: /* Описание входных и выходных данных */

2015-07-10T13:32:55Z

Описание входных и выходных данных

← Предыдущая версия		Версия от 13:32, 10 июля 2015
Строка 114:		Строка 114:
	'''Входные данные''': левая треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).		'''Входные данные''': левая треугольная матрица <math>L</math> (элементы <math>l_{ij}</math>), вектор правой части <math>b</math> (элементы <math>b_{i}</math>).

	'''Объём входных данных''': :<math>\frac{n (n + 1)}{2}</math> (в силу треугольности и единичности диагональных элементов достаточно хранить только поддиагональные элементы матрицы <math>L</math>).		'''Объём входных данных''': <math>\frac{n (n + 1)}{2}</math> (в силу треугольности и единичности диагональных элементов достаточно хранить только поддиагональные элементы матрицы <math>L</math>).

	'''Выходные данные''': вектор решения <math>y</math> (элементы <math>y_{i}</math>).		'''Выходные данные''': вектор решения <math>y</math> (элементы <math>y_{i}</math>).

	'''Объём выходных данных''': :<math>n~.</math>		'''Объём выходных данных''': <math>n~.</math>

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

ASA: /* Информационный граф */

2015-07-10T13:31:06Z

Информационный граф

← Предыдущая версия		Версия от 13:31, 10 июля 2015
Строка 95:		Строка 95:

	Результат срабатывания операции является:		Результат срабатывания операции является:
	** при <math>j < i-1</math> - ''промежуточным данным'' алгоритма;		* при <math>j < i-1</math> - ''промежуточным данным'' алгоритма;
	** при <math>j = i-1</math> - выходным данным.		* при <math>j = i-1</math> - выходным данным.

	Описанный граф можно посмотреть на рисунке, выполненном для случая <math>n = 5</math>. Здесь вершины обозначены зелёным цветом. Подача входных данных из вектора <math>b</math>, идущая в вершины левого столбца, и матрицы <math>L</math>, идущая во все вершины, на рисунке не представлена.		Описанный граф можно посмотреть на рисунке, выполненном для случая <math>n = 5</math>. Здесь вершины обозначены зелёным цветом. Подача входных данных из вектора <math>b</math>, идущая в вершины левого столбца, и матрицы <math>L</math>, идущая во все вершины, на рисунке не представлена.