Generalized Diagonal Pivoting Methods for Tridiagonal Systems without Interchanges
Jennifer B. Erway, Roummel F. Marcia, Joseph A. Tyson · 2010
It has been shown that a nonsingular symmetric tridiagonal linear system of the form Tx = b can be solved in a backward-stable manner using diagonal pivoting meth- ods, where the LBL T decomposition of T is computed, i.e., T = LBL T , where L is unit lower triangular and B is block diagonal with 1 1 and 2 2 blocks. In this paper, we generalize these methods for solving unsymmetric tridiagonal matrices. We present three algorithms that compute the LBM T factorization, where L and M are unit lower triangular and B is block diago- nal with 1 1 and 2 2 blocks. These algorithms are normwise backward stable and reduce to the LBL T factorization when applied to symmetric matrices. We demonstrate the robustness of the algorithms for the unsymmetric case using a wide range of well-conditioned and ill-conditioned linear systems. Numerical results suggest that these algorithms are comparable to Gaussian elimination with partial pivoting (GEPP). However, unlike GEPP, these algorithms do not require row interchanges, and thus, may be used in applications where row interchanges are not possible. In addition, substantial computational savings can be achieved by carefully managing the nonzero elements of the factors L, B, and M.