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

В отличие от метода Стоуна, однако, первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем при рекурсивном сдваивании Стоуна.

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