Полный метод циклической редукции: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) м |
Frolov (обсуждение | вклад) м |
||
| Строка 18: | Строка 18: | ||
{{Шаблон:Трёхдиагональная СЛАУ}} | {{Шаблон:Трёхдиагональная СЛАУ}} | ||
| − | '''Циклическая редукция''', как и все варианты прогонки, заключается <ref>Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Глав-ная редакция физико-математической литературы, 1985г., 208 с.</ref><ref>Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref> в исключении из уравнений неизвестных, однако, в отличие от них, в ней исключение ведут одновременно по всей СЛАУ. В принципе, её можно считать вариантом [[Метод редукции|метода редукции]], выполняемого максимально возможное для данной СЛАУ число раз. | + | '''Циклическая редукция''', как и все варианты прогонки, заключается <ref name="IK3d">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Глав-ная редакция физико-математической литературы, 1985г., 208 с.</ref><ref>Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.</ref> в исключении из уравнений неизвестных, однако, в отличие от них, в ней исключение ведут одновременно по всей СЛАУ. В принципе, её можно считать вариантом [[Метод редукции|метода редукции]], выполняемого максимально возможное для данной СЛАУ число раз. |
[[file:CyclRed.png|thumb|right|600px|Рисунок 1. Граф алгоритма циклической редукции при n=15.]] | [[file:CyclRed.png|thumb|right|600px|Рисунок 1. Граф алгоритма циклической редукции при n=15.]] | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| + | |||
| + | Лучше всего схема циклической редукции<ref name="IK3d" /> разработана для случая <math>n = 2^{k}-1</math>. | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия 11:30, 21 апреля 2016
| Циклическая редукция для трёхдиагональной матрицы, точечный вариант | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(n)[/math] |
| Объём входных данных | [math]4n-2[/math] |
| Объём выходных данных | [math]n[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]O(log n)[/math] |
| Ширина ярусно-параллельной формы | [math]O(n)[/math] |
Основные авторы описания: А.В.Фролов.
Содержание
1 Свойства и структура алгоритма
1.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}, x = \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ \end{bmatrix}, b = \begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \\ \end{bmatrix} [/math]
Часто, однако, при изложении сути методов решения трёхдиагональных СЛАУ[3] элементы правой части и матрицы системы обозначают и нумеруют по-другому, например СЛАУ может иметь вид ([math]N=n-1[/math])
- [math] A = \begin{bmatrix} c_{0} & -b_{0} & 0 & \cdots & \cdots & 0 \\ -a_{1} & c_{1} & -b_{1} & \cdots & \cdots & 0 \\ 0 & -a_{2} & c_{2} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & -a_{N-1} & c_{N-1} & -b_{N-1} \\ 0 & \cdots & \cdots & 0 & -a_{N} & c_{N} \\ \end{bmatrix}\begin{bmatrix} y_{0} \\ y_{1} \\ \vdots \\ y_{N} \\ \end{bmatrix} = \begin{bmatrix} f_{0} \\ f_{1} \\ \vdots \\ f_{N} \\ \end{bmatrix} [/math]
или, если записывать отдельно по уравнениям, то
[math]c_{0} y_{0} - b_{0} y_{1} = f_{0}[/math],
[math]-a_{i} y_{i-1} + c_{i} y_{i} - b_{i} y_{i+1} = f_{i}, 1 \le i \le N-1[/math],
[math]-a_{N} y_{N-1} + c_{N} y_{N} = f_{N}[/math].
Циклическая редукция, как и все варианты прогонки, заключается [4][5] в исключении из уравнений неизвестных, однако, в отличие от них, в ней исключение ведут одновременно по всей СЛАУ. В принципе, её можно считать вариантом метода редукции, выполняемого максимально возможное для данной СЛАУ число раз.
1.2 Математическое описание алгоритма
Лучше всего схема циклической редукции[4] разработана для случая [math]n = 2^{k}-1[/math].
2 Литература
- ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
- ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
- ↑ Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.
- ↑ 4,0 4,1 Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Глав-ная редакция физико-математической литературы, 1985г., 208 с.
- ↑ Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.
