An overlapped two-way method for solving tridiagonal linear systems in a BSP computer (Q1763313)

Given a tridiagonal linear system \(Ax = d\), where \(A\) is a diagonally dominant matrix, this paper considers parallel methods for computing \(x\). The first method decomposes \(A\) as follows: \[ A = \left[ \begin{matrix} L_{11} & 0 \\ L_{21} & U_{22} \end{matrix} \right] \left[\begin{matrix} D_{11} & 0 \\ 0 & D_{22} \end{matrix}\right] \left[\begin{matrix} U_{11} & U_{12} \\ 0 & L_{22} \end{matrix}\right], \] where \(L_{11},L_{22}\) are lower bidiagonal and \(U_{11}, U_{22}\) are upper bidiagonal matrices of roughly the same size with ones on the diagonals; \(D_{11}\) and \(D_{22}\) are diagonal; \(L_{21}\) and \(U_{12}\) are zero besides a non-zero entry in the top-right/bottom-left position. While \(L_{11}D_{11}U_{11}\) is computed from top-to-bottom, the decomposition \(U_{22}D_{22}U_{22}\) is computed from bottom-to-top. This admits the efficient parallel computation of the complete decomposition as well as the subsequent solution of the bidiagonal systems on two processors. For more processors, the authors propose an overlapping partitition of the matrix, very much in the spirit of Schwarz iterations. It is suggested to use the first method to solve each block diagonal subsystem of the partition on two processors. Numerical experiments demonstrate that the actual execution times of the described algorithms match the predicted times rather well. No comparison with one of the other existing parallel methods for solving a tridiagonal system is made.