Уровень задачи

Методы решения СЛАУ с трёхдиагональными матрицами: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[выверенная версия][выверенная версия]
 
(не показано 11 промежуточных версий 2 участников)
Строка 1: Строка 1:
−
== Методы решения СЛАУ с трёхдиагональными матрицами ==
+
{{level-p}}
−
Во многих математических моделях удаётся свести задачу к СЛАУ<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}
Строка 12: Строка 14:
 
</math>
 
</math>
  
−
На этой странице представлены разные методы решения такой СЛАУ.  
+
== Методы решения СЛАУ с трёхдиагональными матрицами ==
 +
 
 +
Здесь представлены разные методы решения СЛАУ с трёхдиагональными матрицами.  
  
 
=== Методы, основанные на стандартном ''LU''-разложении трёхдиагональной матрицы ''A'' на две двухдиагональные ===
 
=== Методы, основанные на стандартном ''LU''-разложении трёхдиагональной матрицы ''A'' на две двухдиагональные ===
Строка 18: Строка 22:
 
Часть методов основана на ''LU''-разложении исходной матрицы системы и последующем решении образовавшихся двухдиагональных СЛАУ. Подобный подход позволяет при повторном решении новой СЛАУ с разложенной матрицей не повторять разложение, а выполнять только решения двухдиагональных СЛАУ.
 
Часть методов основана на ''LU''-разложении исходной матрицы системы и последующем решении образовавшихся двухдиагональных СЛАУ. Подобный подход позволяет при повторном решении новой СЛАУ с разложенной матрицей не повторять разложение, а выполнять только решения двухдиагональных СЛАУ.
  
−
==== Метод с линейным временем вычислений ====  
+
==== Методы с линейным временем вычислений ====  
 +
 
 +
===== Методы прогонки =====
 +
 
 +
====== Монотонная прогонка ======
 +
 
 +
[[Прогонка, точечный вариант|Монотонная прогонка]]<ref name="setki">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref> – последовательный алгоритм решения трёхдиагональной СЛАУ – является частным случаем общего метода исключения неизвестных, однако получила специальное название из-за распространённости задач такого типа в прикладных исследованиях. В математической литературе<ref name="setki" /> указано, что применение метода прогонки эквивалентно последовательному решению двух задач: <math>LU</math>-разложению трёхдиагональной матрицы <math>A</math> на две двухдиагональные с помощью [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактной схемы метода Гаусса]] и затем решению двух СЛАУ с двухдиагональными матрицами с помощью обычной [[Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей|подстановки]]. Метод почти последователен (исключением является то, что решение первой из двухдиагональных СЛАУ можно выполнять почти параллельно с разложением трёхдиагональной матрицы). При повторении прогонки для новой СЛАУ с той же матрицей алгоритм [[Повторная прогонка, точечный вариант|повторной прогонки]] полностью последователен.
  
−
===== Метод прогонки =====
+
====== Встречная прогонка ======
  
−
[[Прогонка, точечный вариант|Прогонка]]<ref name="setki">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref> – последовательный алгоритм решения трёхдиагональной СЛАУ – является частным случаем общего метода исключения неизвестных, однако получила специальное название из-за распространённости задач такого типа в прикладных исследованиях. В математической литературе<ref name="setki" /> указано, что применение метода прогонки эквивалентно последовательному решению двух задач: <math>LU</math>-разложению трёхдиагональной матрицы <math>A</math> на две двухдиагональные с помощью [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактной схемы метода Гаусса]] и затем решению двух СЛАУ с двухдиагональными матрицами с помощью обычной [[Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей|подстановки]]. Метод почти последователен (исключением является то, что решение первой из двухдиагональных СЛАУ можно выполнять почти параллельно с разложением трёхдиагональной матрицы). При повторении прогонки для новой СЛАУ с той же матрицей алгоритм [[Повторная прогонка, точечный вариант|повторной прогонки]] полностью последователен.
+
[[Встречная прогонка, точечный вариант|Встречная прогонка]]<ref name="setki" /> - тоже является частным случаем общего метода исключения неизвестных. Получена из алгоритмов монотонной прогонки за счёт идеи встречного (откуда и её название) исключения неизвестных в уравнениях "с начала" и "с конца" СЛАУ.  
  
 
==== Метод с логарифмическим временем вычислений ====
 
==== Метод с логарифмическим временем вычислений ====
Строка 28: Строка 38:
 
===== Метод сдваивания Стоуна =====
 
===== Метод сдваивания Стоуна =====
  
−
[[Метод сдваивания Стоуна]]<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-разложения трёхдиагональной матрицы]] и  [[Метод сдваивания Стоуна для решения двудиагональных СЛАУ|метода сдваивания Стоуна для решения двудиагональных СЛАУ]]. По ряду причин, изложенных на соответствующих страницах, первый из них не применяется на практике, а второй - малораспространён.
  
 
==== Метод с временем вычислений меньше линейного ====
 
==== Метод с временем вычислений меньше линейного ====
 
===== Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с ''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-разложения трёхдиагональной матрицы]] и [[Последовательно-параллельный вариант обратной подстановки|последовательно-параллельного варианта обратной подстановки]]. Первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем у рекурсивного сдваивания Стоуна. В то же время строгое исследование области устойчивости пока не проведено. Как и алгоритм Стоуна, имеет ограниченную применимость для блочно-трёхдиагональной реализации.
  
 
=== Другие методы ===
 
=== Другие методы ===
  
−
Эта часть методов не основана на LU-разложении исходной матрицы системы. Тем не менее, в каждом из методов есть такая (особенная для каждого метода) часть, которая зависит только от элементов матрицы систем. Такую часть при повторных решениях СЛАУ с той же матрицей можно не повторять, что делает повторные решения довольно экономичными.   
+
Эта часть методов не основана на LU-разложении исходной матрицы системы. Тем не менее, в каждом из методов есть такая (особенная для каждого метода) часть, которая зависит только от элементов матрицы систем. Её при повторных решениях СЛАУ с той же матрицей можно использовать уже ранее вычисленную. Это делает повторные решения довольно экономичными.   
  
 
==== Методы с логарифмическим или полулогарифмическим временем решения ====
 
==== Методы с логарифмическим или полулогарифмическим временем решения ====
Строка 50: Строка 60:
 
===== Метод редукции =====
 
===== Метод редукции =====
  
−
[[Метод редукции]] нециклического вида, несмотря на то, что известен давно<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref>, обычно рассматривается как "недоделка" циклической редукции, а не самостоятельный параллельный алгоритм, в частности, из-за избыточных вычислений.  
+
[[Метод редукции]] нециклического вида, несмотря на то, что известен давно<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref>, обычно рассматривается как "недоделка" циклической редукции, а не самостоятельный параллельный алгоритм, в частности, из-за избыточных вычислений. Вместе с тем для большей сбалансированности и меньших простоев оборудования именно нециклическая редукция должна рассматриваться как предпочтительная<ref>А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.</ref>.
  
 
===== Метод окаймления =====
 
===== Метод окаймления =====
−
[[Метод окаймления]] по своей идее восходит к применению принципа "разделяй и властвуй", аналоги для ленточных матриц появились ещё в 2006г.<ref>А.В.Попов. Решение задач линейной алгебры с разреженными симметричными матрицами на MIMD-компьютере. Искусственный интеллект (Донецк). — 2006, №4, с. 670-679</ref>, а, возможно, и ранее. Позже, при выходе публикации про [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]] в ответ на замечание рецензента о схожести его схемы с методом окаймления автором было вставлено замечание о разных структурах образующихся разложений<ref name="FAV" />.  
+
[[Метод окаймления]] по своей идее восходит к применению принципа "разделяй и властвуй", аналоги для ленточных матриц появились ещё в 2006г.<ref>А.В.Попов. Решение задач линейной алгебры с разреженными симметричными матрицами на MIMD-компьютере // Искусственный интеллект (Донецк). — 2006, №4, с. 670-679</ref>, а, возможно, и ранее. Позже, при выходе публикации про [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]] в ответ на замечание рецензента о схожести его схемы с методом окаймления автором было вставлено замечание о разных структурах образующихся разложений<ref name="FAV" />.
  
 
== Литература ==
 
== Литература ==
Строка 59: Строка 69:
 
<references />
 
<references />
  
−
[[Категория:Статьи в работе]]
+
[[Категория:Законченные статьи]]
 +
 
 +
[[En:Methods for solving tridiagonal SLAEs]]

Текущая версия на 13:01, 9 ноября 2017


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

Во многих математических моделях одномерных явлений удаётся свести задачу к СЛАУ[1][2] [math]Ax = b[/math] с трёхдиагональной матрицей

[math] A = \begin{bmatrix} a_{11} & a_{12} & 0 & \cdots & \cdots & 0 \\ a_{21} & a_{22} & a_{23}& \cdots & \cdots & 0 \\ 0 & a_{32} & a_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & a_{n-1 n-2} & a_{n-1 n-1} & a_{n-1 n} \\ 0 & \cdots & \cdots & 0 & a_{n n-1} & a_{n n} \\ \end{bmatrix} [/math]

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

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

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

Часть методов основана на LU-разложении исходной матрицы системы и последующем решении образовавшихся двухдиагональных СЛАУ. Подобный подход позволяет при повторном решении новой СЛАУ с разложенной матрицей не повторять разложение, а выполнять только решения двухдиагональных СЛАУ.

2.1.1 Методы с линейным временем вычислений

2.1.1.1 Методы прогонки
2.1.1.1.1 Монотонная прогонка

Монотонная прогонка[3] – последовательный алгоритм решения трёхдиагональной СЛАУ – является частным случаем общего метода исключения неизвестных, однако получила специальное название из-за распространённости задач такого типа в прикладных исследованиях. В математической литературе[3] указано, что применение метода прогонки эквивалентно последовательному решению двух задач: [math]LU[/math]-разложению трёхдиагональной матрицы [math]A[/math] на две двухдиагональные с помощью компактной схемы метода Гаусса и затем решению двух СЛАУ с двухдиагональными матрицами с помощью обычной подстановки. Метод почти последователен (исключением является то, что решение первой из двухдиагональных СЛАУ можно выполнять почти параллельно с разложением трёхдиагональной матрицы). При повторении прогонки для новой СЛАУ с той же матрицей алгоритм повторной прогонки полностью последователен.

2.1.1.1.2 Встречная прогонка

Встречная прогонка[3] - тоже является частным случаем общего метода исключения неизвестных. Получена из алгоритмов монотонной прогонки за счёт идеи встречного (откуда и её название) исключения неизвестных в уравнениях "с начала" и "с конца" СЛАУ.

2.1.2 Метод с логарифмическим временем вычислений

2.1.2.1 Метод сдваивания Стоуна

Метод сдваивания Стоуна[4][5] разработан в начале 70-х гг. 20го века. Как и прогонка, которую он должен был заменить, метод сдваивания Стоуна для решения СЛАУ с трёхдиагональными матрицами состоит из двух отдельно разработанных частей: алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы и метода сдваивания Стоуна для решения двудиагональных СЛАУ. По ряду причин, изложенных на соответствующих страницах, первый из них не применяется на практике, а второй - малораспространён.

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

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

Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками предложен в 2015 г.[6] в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ. Как и метод Стоуна, основан на [math]LU[/math]-разложении матрицы исходной СЛАУ с использованием ассоциативности операции матричного умножения и состоит из двух существенно различных по свойствам частей: последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы и последовательно-параллельного варианта обратной подстановки. Первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем у рекурсивного сдваивания Стоуна. В то же время строгое исследование области устойчивости пока не проведено. Как и алгоритм Стоуна, имеет ограниченную применимость для блочно-трёхдиагональной реализации.

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

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

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

2.2.1.1 Метод циклической редукции

Метод циклической редукции впервые появился в разных вариациях на рубеже 60-70-х гг. XX века[7][8][5] и до настоящего времени является, пожалуй, самым популярным из параллельных замен метода прогонки. Несмотря на то, что для распараллеливания в нём использованы избыточные по сравнению с прогонкой вычисления, пригоден как для решения одиночных СЛАУ, так и для многих СЛАУ с одной и той же матрицей. Диапазон устойчивости находится в тех же границах, что и у классической прогонки; существует и блочный аналог метода.

2.2.1.2 Метод дихотомии

Метод дихотомии предложен в 2010 г.[9] и предназначен в основном для решения большого количества СЛАУ с одной и той же трёхдиагональной матрицей. Для решения одиночных трёхдиагональных СЛАУ слишком тяжеловесен, в силу того, что количество операций O(n) выполняется при подготовительной работе на каждом из процессоров.

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

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

Метод редукции нециклического вида, несмотря на то, что известен давно[10], обычно рассматривается как "недоделка" циклической редукции, а не самостоятельный параллельный алгоритм, в частности, из-за избыточных вычислений. Вместе с тем для большей сбалансированности и меньших простоев оборудования именно нециклическая редукция должна рассматриваться как предпочтительная[11].

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

Метод окаймления по своей идее восходит к применению принципа "разделяй и властвуй", аналоги для ленточных матриц появились ещё в 2006г.[12], а, возможно, и ранее. Позже, при выходе публикации про Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками в ответ на замечание рецензента о схожести его схемы с методом окаймления автором было вставлено замечание о разных структурах образующихся разложений[6].

3 Литература

  1. ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. ↑ 3,0 3,1 3,2 Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.
  4. ↑ 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.
  5. ↑ 5,0 5,1 Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.
  6. ↑ 6,0 6,1 А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162
  7. ↑ Buneman O. A Compact Non-iterative Poisson Solver // Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.
  8. ↑ Buzbee B.L., Golub G.H., Nielson C.W. On Direct Methods for Solving Poisson's Equations // SIAM J. Numer. Anal., Vol. 7, No. 4 (Dec. 1970), P. 627-656.
  9. ↑ Terekhov Andrew. Parallel dichotomy algorithm for solving tridiagonal system of linear equations with multiple right-hand sides. // Parallel Comput. 2010. Vol. 36. N. 8. pp. 423–438
  10. ↑ Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.
  11. ↑ А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.
  12. ↑ А.В.Попов. Решение задач линейной алгебры с разреженными симметричными матрицами на MIMD-компьютере // Искусственный интеллект (Донецк). — 2006, №4, с. 670-679
Источник — https://algowiki-project.org/w/ru/index.php?title=Методы_решения_СЛАУ_с_трёхдиагональными_матрицами&oldid=23836