Методы решения СЛАУ с трёхдиагональными матрицами - История изменений

ASA в 10:01, 9 ноября 2017

2017-11-09T10:01:58Z

← Предыдущая версия		Версия от 10:01, 9 ноября 2017
Строка 69:		Строка 69:
	<references />		<references />

	[[Категория:~~Статьи в работе~~]]		[[Категория:Законченные статьи]]

	[[En:Methods for solving tridiagonal SLAEs]]		[[En:Methods for solving tridiagonal SLAEs]]

ASA в 07:38, 24 октября 2017

2017-10-24T07:38:07Z

← Предыдущая версия		Версия от 07:38, 24 октября 2017
Строка 70:		Строка 70:

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

			[[En:Methods for solving tridiagonal SLAEs]]

Frolov: /* Другие методы */

2017-04-26T11:14:42Z

Другие методы

← Предыдущая версия		Версия от 11:14, 26 апреля 2017
Строка 46:		Строка 46:
	=== Другие методы ===		=== Другие методы ===

	Эта часть методов не основана на LU-разложении исходной матрицы системы. Тем не менее, в каждом из методов есть такая (особенная для каждого метода) часть, которая зависит только от элементов матрицы систем. ~~Такую часть~~ при повторных решениях СЛАУ с той же матрицей можно ~~не повторять, что~~ делает повторные решения довольно экономичными.		Эта часть методов не основана на LU-разложении исходной матрицы системы. Тем не менее, в каждом из методов есть такая (особенная для каждого метода) часть, которая зависит только от элементов матрицы систем. Её при повторных решениях СЛАУ с той же матрицей можно использовать уже ранее вычисленную. Это делает повторные решения довольно экономичными.

	==== Методы с логарифмическим или полулогарифмическим временем решения ====		==== Методы с логарифмическим или полулогарифмическим временем решения ====

Frolov: /* Метод редукции */

2017-04-26T10:58:26Z

Метод редукции

← Предыдущая версия		Версия от 10:58, 26 апреля 2017
Строка 60:		Строка 60:
	===== Метод редукции =====		===== Метод редукции =====

	[[Метод редукции]] нециклического вида, несмотря на то, что известен давно<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref>, обычно рассматривается как "недоделка" циклической редукции, а не самостоятельный параллельный алгоритм, в частности, из-за избыточных вычислений.		[[Метод редукции]] нециклического вида, несмотря на то, что известен давно<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref>, обычно рассматривается как "недоделка" циклической редукции, а не самостоятельный параллельный алгоритм, в частности, из-за избыточных вычислений. Вместе с тем для большей сбалансированности и меньших простоев оборудования именно нециклическая редукция должна рассматриваться как предпочтительная<ref>А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.</ref>.

	===== Метод окаймления =====		===== Метод окаймления =====

Frolov: /* Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками */

2017-04-26T10:53:52Z

Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками

← Предыдущая версия		Версия от 10:53, 26 апреля 2017
Строка 42:		Строка 42:
	==== Метод с временем вычислений меньше линейного ====		==== Метод с временем вычислений меньше линейного ====
	===== Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с ''LU''-разложением и обратными подстановками =====		===== Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с ''LU''-разложением и обратными подстановками =====
	[[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]] предложен [http://russianscdays.org/node/28 в 2015 г.]<ref name="FAV">~~Фролов~~ А.В. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // ~~Принята в качестве доклада на первую объединенную международную конференцию "~~Суперкомпьютерные дни в России~~", Москва,~~ 28-29 сентября 2015 г.</ref> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ. Как и метод Стоуна, основан на <math>LU</math>-разложении матрицы исходной СЛАУ с использованием ассоциативности операции матричного умножения и состоит из двух существенно различных по свойствам частей: [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы\|последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы]] и [[Последовательно-параллельный вариант обратной подстановки\|последовательно-параллельного варианта обратной подстановки]]. Первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем у рекурсивного сдваивания Стоуна. В то же время строгое исследование области устойчивости пока не проведено. Как и алгоритм Стоуна, имеет ограниченную применимость для блочно-трёхдиагональной реализации.		[[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]] предложен [http://russianscdays.org/node/28 в 2015 г.]<ref name="FAV">А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162</ref> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ. Как и метод Стоуна, основан на <math>LU</math>-разложении матрицы исходной СЛАУ с использованием ассоциативности операции матричного умножения и состоит из двух существенно различных по свойствам частей: [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы\|последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы]] и [[Последовательно-параллельный вариант обратной подстановки\|последовательно-параллельного варианта обратной подстановки]]. Первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем у рекурсивного сдваивания Стоуна. В то же время строгое исследование области устойчивости пока не проведено. Как и алгоритм Стоуна, имеет ограниченную применимость для блочно-трёхдиагональной реализации.

	=== Другие методы ===		=== Другие методы ===

Frolov: /* СЛАУ с трёхдиагональными матрицами */

2017-04-26T10:51:16Z

СЛАУ с трёхдиагональными матрицами

← Предыдущая версия		Версия от 10:51, 26 апреля 2017
Строка 2:		Строка 2:
	== СЛАУ с трёхдиагональными матрицами ==		== СЛАУ с трёхдиагональными матрицами ==

	Во многих математических моделях удаётся свести задачу к СЛАУ<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <math>Ax = b</math> с трёхдиагональной матрицей		Во многих математических моделях одномерных явлений удаётся свести задачу к СЛАУ<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <math>Ax = b</math> с трёхдиагональной матрицей
	:<math>		:<math>
	A = \begin{bmatrix}		A = \begin{bmatrix}

Frolov в 10:49, 26 апреля 2017

2017-04-26T10:49:42Z

← Предыдущая версия		Версия от 10:49, 26 апреля 2017
Строка 1:		Строка 1:
	{{level-p}}		{{level-p}}
	== ~~Методы решения~~ СЛАУ с трёхдиагональными матрицами ==		== СЛАУ с трёхдиагональными матрицами ==

	Во многих математических моделях удаётся свести задачу к СЛАУ<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <math>Ax = b</math> с трёхдиагональной матрицей		Во многих математических моделях удаётся свести задачу к СЛАУ<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <math>Ax = b</math> с трёхдиагональной матрицей
	:<math>		:<math>
Строка 13:		Строка 14:
	</math>		</math>

	~~На этой странице~~ представлены разные методы решения ~~такой~~ СЛАУ.		== Методы решения СЛАУ с трёхдиагональными матрицами ==

			Здесь представлены разные методы решения СЛАУ с трёхдиагональными матрицами.

	=== Методы, основанные на стандартном ''LU''-разложении трёхдиагональной матрицы ''A'' на две двухдиагональные ===		=== Методы, основанные на стандартном ''LU''-разложении трёхдиагональной матрицы ''A'' на две двухдиагональные ===

Frolov в 10:46, 26 апреля 2017

2017-04-26T10:46:55Z

← Предыдущая версия		Версия от 10:46, 26 апреля 2017
Строка 1:		Строка 1:
	{{level-m}}		{{level-p}}
	== Методы решения СЛАУ с трёхдиагональными матрицами ==		== Методы решения СЛАУ с трёхдиагональными матрицами ==
	Во многих математических моделях удаётся свести задачу к СЛАУ<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <math>Ax = b</math> с трёхдиагональной матрицей		Во многих математических моделях удаётся свести задачу к СЛАУ<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <math>Ax = b</math> с трёхдиагональной матрицей

Frolov в 12:15, 12 декабря 2016

2016-12-12T12:15:09Z

← Предыдущая версия		Версия от 12:15, 12 декабря 2016
Строка 35:		Строка 35:
	===== Метод сдваивания Стоуна =====		===== Метод сдваивания Стоуна =====

	[[Метод сдваивания Стоуна]]<ref>Stone H.S. An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations // J. ACM, Vol. 20, No. 1 (Jan. 1973), P. 27-38.</ref><ref name="Stone 2">Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref> разработан в начале 70-х гг. 20го века. Как и [[Прогонка\|прогонка]], которую он должен был заменить, [[Метод сдваивания Стоуна\|метод сдваивания Стоуна для решения СЛАУ с трёхдиагональными матрицами]] состоит из двух отдельно разработанных частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения ~~двухдиагональных~~ СЛАУ\|метода сдваивания Стоуна для решения ~~двухдиагональных~~ СЛАУ]]. По ряду причин, изложенных на соответствующих страницах, первый из них не применяется на практике, а второй - малораспространён.		[[Метод сдваивания Стоуна]]<ref>Stone H.S. An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations // J. ACM, Vol. 20, No. 1 (Jan. 1973), P. 27-38.</ref><ref name="Stone 2">Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref> разработан в начале 70-х гг. 20го века. Как и [[Прогонка\|прогонка]], которую он должен был заменить, [[Метод сдваивания Стоуна\|метод сдваивания Стоуна для решения СЛАУ с трёхдиагональными матрицами]] состоит из двух отдельно разработанных частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двудиагональных СЛАУ\|метода сдваивания Стоуна для решения двудиагональных СЛАУ]]. По ряду причин, изложенных на соответствующих страницах, первый из них не применяется на практике, а второй - малораспространён.

	==== Метод с временем вычислений меньше линейного ====		==== Метод с временем вычислений меньше линейного ====

ASA в 11:53, 10 февраля 2016

2016-02-10T11:53:58Z

← Предыдущая версия		Версия от 11:53, 10 февраля 2016
Строка 1:		Строка 1:
			{{level-m}}
	== Методы решения СЛАУ с трёхдиагональными матрицами ==		== Методы решения СЛАУ с трёхдиагональными матрицами ==
	Во многих математических моделях удаётся свести задачу к СЛАУ<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <math>Ax = b</math> с трёхдиагональной матрицей		Во многих математических моделях удаётся свести задачу к СЛАУ<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <math>Ax = b</math> с трёхдиагональной матрицей