Fast solvers for tridiagonal Toeplitz linear systems
Tóm tắt
Let A be a tridiagonal Toeplitz matrix denoted by
$$A = {\text {Tritoep}} (\beta , \alpha , \gamma )$$
. The matrix A is said to be: strictly diagonally dominant if
$$|\alpha |>|\beta |+|\gamma |$$
, weakly diagonally dominant if
$$|\alpha |\ge |\beta |+|\gamma |$$
, subdiagonally dominant if
$$|\beta |\ge |\alpha |+|\gamma |$$
, and superdiagonally dominant if
$$|\gamma |\ge |\alpha |+|\beta |$$
. In this paper, we consider the solution of a tridiagonal Toeplitz system
$$A\mathbf {x}= \mathbf {b}$$
, where A is subdiagonally dominant, superdiagonally dominant, or weakly diagonally dominant, respectively. We first consider the case of A being subdiagonally dominant. We transform A into a block
$$2\times 2$$
matrix by an elementary transformation and then solve such a linear system using the block LU factorization. Compared with the LU factorization method with pivoting, our algorithm takes less flops, and needs less memory storage and data transmission. In particular, our algorithm outperforms the LU factorization method with pivoting in terms of computing efficiency. Then, we deal with superdiagonally dominant and weakly diagonally dominant cases, respectively. Numerical experiments are finally given to illustrate the effectiveness of our algorithms.
Tài liệu tham khảo
Bai Z-Z, Golub GH, Ng MK (2003) Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl. 24:603–626
Bunch JR, Marcia RF (2000) A pivoting strategy for symmetric tridiagonal matrices. J. Numer. Linear Algebra 12:911–922
Chan R, Jin X-J (2007) An Introduction to Iterative Toeplitz Solvers. SIAM, Philadelphia
Chan R, Ng MK (1996) Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38:427–482
Chen F, Jiang Y-L (2010) On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems. J. Comput. Appl. Math. 234:2432–2440
Du L, Sogabe T, Zhang S-L (2017) A fast algorithm for solving tridiagonal quasi-Toeplitz linear systems. Appl. Math. Lett. 75:74–81
Garey LE, Shaw RE (2001) A parallel method for linear equations with tridiagonal Toeplitz coefficient matrices. Comput. Math. Appl. 42:1–11
Golub G, Van Loan C (1996) Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore
Gu C-Q, Tian Z-L (2009) On the HSS iteration methods for positive definite Toeplitz linear systems. J. Comput. Appl. Math. 224:709–718
Kim HJ (1990) A parallel algorithm solving a tridiagonal Toeplitz linear system. Parallel Comput. 13:289–294
Liu Z-Y, Chen L, Zhang Y-L (2010) The reconstruction of an Hermitian Toeplitz matrices with prescribed eigenpairs. J. Syst. Sci. Complex. 23:961–970
Liu Z-Y, Zhang Y-L, Ferreira C, Ralha R (2010) On inverse eigenvalue problems for block Toeplitz matrices with Toeplitz blocks. Appl. Math. Comput. 216:1819–1830
Liu Z-Y, Qin X-R, Wu N-C, Zhang Y-L (2017) The shifted classical circulant and skew circulant splitting iterative methods for Toeplitz matrices. Canad. Math. Bull. 60:807–815
Liu Z-Y, Wu N-C, Qin X-R, Zhang Y-L (2018) Trigonometric transform splitting methods for real symmetric Toeplitz systems. Comput. Math. Appl. 75:2782–2794
Liu Z-Y, Chen S-H, Xu W-J, Zhang Y-L (2019) The eigen-structures of real (skew) circulant matrices with some applications. Comput. Appl. Math. 38:178. https://doi.org/10.1007/s40314-019-0971-9
McNally JM, Garey LE, Shaw RE (2000) A split-correct parallel algorithm for solving tridiagonal symmetric toeplitz systems. Int. J. Comput. Math. 75:303–313
Ng MK (2003) Circulant and skew-circulant splitting methods for Toeplitz systems. J. Comput. Appl. Math. 159:101–108
Noschese S, Pasquini L, Reichel L (2013) Tridiagonal Toeplitz matrices: properties and novel applications. Numer. Linear Algebra Appl. 20:302–326
Rojo O (1990) A new method for solving symmetric circulant tridiagonal systems of linear equations. J. Parllel Distr. Com. 20:61–67
Saad Y (2003) Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM, Philadelphia
Terekhov AV (2015) Parallel dichotomy algorithm for solving tridiagonal system of linear equations with multiple right-hand sides. J. Parllel Distr. Com. 87:102–108
Yan W-M, Chung K-L (1994) A fast algorithm for solving special tridiagonal systems. Computing 52:203–211