Метод сдваивания Стоуна - История изменений

ASA в 12:29, 14 марта 2018

2018-03-14T12:29:57Z

← Предыдущая версия		Версия от 12:29, 14 марта 2018
Строка 21:		Строка 21:
	[[Категория:Неустойчивые параллельные методы]]		[[Категория:Неустойчивые параллельные методы]]
	[[Категория:Алгоритмы с избыточными вычислениями]]		[[Категория:Алгоритмы с избыточными вычислениями]]

			[[en:Stone doubling algorithm]]

ASA в 12:28, 14 марта 2018

2018-03-14T12:28:26Z

← Предыдущая версия		Версия от 12:28, 14 марта 2018
Строка 1:		Строка 1:
	{{level-a}}		{{level-m}}

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

Frolov в 10:15, 12 октября 2017

2017-10-12T10:15:35Z

← Предыдущая версия		Версия от 10:15, 12 октября 2017
Строка 1:		Строка 1:
	{{level-m}}		{{level-a}}

	Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]]		Основные авторы описания: [[Участник:Frolov\|А.В.Фролов]]
Строка 9:		Строка 9:
	Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Полный метод циклической редукции\|методу циклической редукции]]. В отличие от своих непосредственных предшественников с логарифмическим критическим путём графа алгоритма, метод Стоуна, как и классическая монотонная прогонка, основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двудиагональных СЛАУ\|метода сдваивания Стоуна для решения двудиагональных СЛАУ]].		Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Полный метод циклической редукции\|методу циклической редукции]]. В отличие от своих непосредственных предшественников с логарифмическим критическим путём графа алгоритма, метод Стоуна, как и классическая монотонная прогонка, основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двудиагональных СЛАУ\|метода сдваивания Стоуна для решения двудиагональных СЛАУ]].

	Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости, расходясь уже на сколько-нибудь реальных размерах матриц. Поэтому на практике метод Стоуна ~~давно~~ не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.		Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости, расходясь уже на сколько-нибудь реальных размерах матриц. Поэтому на практике метод Стоуна не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.

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

Frolov в 14:28, 13 декабря 2016

2016-12-13T14:28:22Z

← Предыдущая версия		Версия от 14:28, 13 декабря 2016
Строка 1:		Строка 1:
	{{level-m}}		{{level-m}}

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

	'''Метод сдваивания Стоуна''' (иначе '''схема Стона''' <ref name="F">Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31</ref>) - один из вариантов замены [[Прогонка, точечный вариант\|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где		'''Метод сдваивания Стоуна''' (иначе '''схема Стона''' <ref name="F">Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31</ref>) - один из вариантов замены [[Прогонка, точечный вариант\|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где

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

2016-12-12T12:13:04Z

← Предыдущая версия		Версия от 12:13, 12 декабря 2016
Строка 5:		Строка 5:
	{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}		{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}

	Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Полный метод циклической редукции\|методу циклической редукции]]. В отличие от своих непосредственных предшественников с логарифмическим критическим путём графа алгоритма, метод Стоуна, как и классическая монотонная прогонка, основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения ~~двухдиагональных~~ СЛАУ\|метода сдваивания Стоуна для решения ~~двухдиагональных~~ СЛАУ]].		Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Полный метод циклической редукции\|методу циклической редукции]]. В отличие от своих непосредственных предшественников с логарифмическим критическим путём графа алгоритма, метод Стоуна, как и классическая монотонная прогонка, основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двудиагональных СЛАУ\|метода сдваивания Стоуна для решения двудиагональных СЛАУ]].

	Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости, расходясь уже на сколько-нибудь реальных размерах матриц. Поэтому на практике метод Стоуна давно не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.		Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости, расходясь уже на сколько-нибудь реальных размерах матриц. Поэтому на практике метод Стоуна давно не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.

Frolov в 14:32, 10 декабря 2016

2016-12-10T14:32:08Z

← Предыдущая версия		Версия от 14:32, 10 декабря 2016
Строка 5:		Строка 5:
	{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}		{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}

	Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Полный метод циклической редукции\|методу циклической редукции]]. В отличие от своих предшественников, метод Стоуна основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ\|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]].		Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Полный метод циклической редукции\|методу циклической редукции]]. В отличие от своих непосредственных предшественников с логарифмическим критическим путём графа алгоритма, метод Стоуна, как и классическая монотонная прогонка, основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ\|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]].

	Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости. Поэтому на практике метод Стоуна давно не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.		Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости, расходясь уже на сколько-нибудь реальных размерах матриц. Поэтому на практике метод Стоуна давно не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.

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

Frolov в 10:43, 26 мая 2016

2016-05-26T10:43:19Z

← Предыдущая версия		Версия от 10:43, 26 мая 2016
Строка 5:		Строка 5:
	{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}		{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}

	Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[~~Метод~~ циклической редукции\|методу циклической редукции]]. В отличие от своих предшественников, метод Стоуна основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ\|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]].		Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Полный метод циклической редукции\|методу циклической редукции]]. В отличие от своих предшественников, метод Стоуна основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ\|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]].

	Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости. Поэтому на практике метод Стоуна давно не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.		Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы\|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости. Поэтому на практике метод Стоуна давно не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.

Frolov в 13:09, 18 декабря 2015

2015-12-18T13:09:18Z

@@ Строка 2: / Строка 2: @@
 '''Метод сдваивания Стоуна''' (иначе '''схема Стона''' <ref name="F">Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31</ref>) - один из вариантов замены [[Прогонка, точечный вариант|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где
-:<math>
-A = \begin{bmatrix}
+{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}
 Впервые предложен в начале 70-х гг. 20го века<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> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Метод циклической редукции|методу циклической редукции]]. В отличие от своих предшественников, метод Стоуна основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]].

Nebaruzdin: Добавление уровня классификации.

2015-12-03T14:31:09Z

Добавление уровня классификации.

← Предыдущая версия		Версия от 14:31, 3 декабря 2015
Строка 1:		Строка 1:
			{{level-m}}

	'''Метод сдваивания Стоуна''' (иначе '''схема Стона''' <ref name="F">Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31</ref>) - один из вариантов замены [[Прогонка, точечный вариант\|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где		'''Метод сдваивания Стоуна''' (иначе '''схема Стона''' <ref name="F">Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31</ref>) - один из вариантов замены [[Прогонка, точечный вариант\|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где
	:<math>		:<math>

Frolov в 14:02, 28 августа 2015

2015-08-28T14:02:30Z

← Предыдущая версия		Версия от 14:02, 28 августа 2015
Строка 1:		Строка 1:
	'''Метод сдваивания Стоуна''' - один из вариантов замены [[Прогонка, точечный вариант\|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где		'''Метод сдваивания Стоуна''' (иначе '''схема Стона''' <ref name="F">Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31</ref>) - один из вариантов замены [[Прогонка, точечный вариант\|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где
	:<math>		:<math>
	A = \begin{bmatrix}		A = \begin{bmatrix}