Уровень метода

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

Материал из Алговики
Перейти к: навигация, поиск


Основные авторы описания: А.В.Фролов

Метод сдваивания Стоуна (иначе схема Стона [1]) - один из вариантов замены прогонки в приложении к решению СЛАУ[2][3] вида [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]

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

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

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

Литература

  1. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31
  2. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  3. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  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. Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.