Fast numerical algorithms for solving opposite-bordered tridiagonal Toeplitz linear systems and their applications

Abstract

This paper presents two fast numerical algorithms for solving opposite-bordered tridiagonal Toeplitz linear systems. Both algorithms are designed to solve a system of n equations in linear time. The first algorithm uses a block 2×2-LU factorization combined with a fast approach for solving upper quasi-triangular Toeplitz systems. The second algorithm applies a splitting technique to the opposite-bordered tridiagonal Toeplitz matrix, along with a fast algorithm for solving tridiagonal Toeplitz systems. The effectiveness of the proposed algorithms is demonstrated through numerical experiments.

Keywords

• Tridiagonal matrices
• Opposite-bordered tridiagonal Toeplitz matrices
• Systems of linear equations
• Linear solver
• Sherman–Morrison–Woodbury formula