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

Последовательно-параллельный вариант решения с LU-разложением и обратными подстановками - один из вариантов замены прогонки в приложении к решению трёхдиагональной СЛАУ вида [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]

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

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

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