A fast algorithm for solving tridiagonal quasi-Toeplitz linear systems

摘要

Abstract In this paper, we consider the solution of tridiagonal quasi-Toeplitz linear systems. By exploiting the special quasi-Toeplitz structure, we give a new decomposition form of the coefficient matrix. Based on this matrix decomposition form and combined with the Sherman–Morrison formula, we propose an efficient algorithm for solving the tridiagonal quasi-Toeplitz linear systems. Although our algorithm takes more floating-point operations (FLOPS) than the L U decomposition method, it needs less memory storage and data transmission and is about twice faster than the L U decomposition method. Numerical examples are given to illustrate the efficiency of our algorithm. ]]>