Fast solvers for tridiagonal Toeplitz linear systems
- PDF / 323,866 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 226 Views
Fast solvers for tridiagonal Toeplitz linear systems Zhongyun Liu1 · Shan Li1 · Yi Yin2 · Yulin Zhang3 Received: 30 April 2020 / Revised: 28 September 2020 / Accepted: 24 October 2020 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2020
Abstract Let A be a tridiagonal Toeplitz matrix denoted by A = Tritoep(β, α, γ ). The matrix A is said to be: strictly diagonally dominant if |α| > |β| + |γ |, weakly diagonally dominant if |α| ≥ |β| + |γ |, subdiagonally dominant if |β| ≥ |α| + |γ |, and superdiagonally dominant if |γ | ≥ |α| + |β|. In this paper, we consider the solution of a tridiagonal Toeplitz system Ax = 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 × 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. Keywords Tridiagonal Toeplitz matrices · Diagonally dominant · Schur complement · Block LU factorization · Pivoting Mathematics Subject Classification 15A23 · 15B05 · 65F05 · 65F10
Communicated by Jinyun Yuan.
B
Yulin Zhang [email protected] Zhongyun Liu [email protected] Yi Yin [email protected]
1
School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha 410076, People’s Republic of China
2
Department of Basic Courses, Hunan College of Information, Changsha 410200, People’s Republic of China
3
Centro de Matemática Universidade do Minho, 4710-057 Braga, Portugal 0123456789().: V,-vol
123
315
Page 2 of 10
Z. Liu et al.
1 Introduction Consider the direct solution of the following nonsingular linear system: Ax = b, where A is an n × n tridiagonal Toeplitz matrix of the following form: ⎤ ⎡ α γ ⎥ ⎢β α γ ⎥ ⎢ ⎥ ⎢ .. .. .. ⎥ ⎢ . . . ⎥. A=⎢ ⎥ ⎢ .. .. .. ⎥ ⎢ . . . ⎥ ⎢ ⎣ β α γ⎦ β α
(1.1)
(1.2)
Toeplitz matrices are a class of special structured matrices, which arise from a variety of applications in mathematics, scientific computing, and engineering, for instance, image restoration storage problems in signal processing, algebraic differential equation, time series, and control theory. Exploiting their structure, some fast and/or accurate algorithms for Toeplitz systems and eigen-problems have been developed, see for instance (Chan and Jin 2007; Chan and Ng 1996; Golub and Van Loan 1996; Liu et al. 2010a, b) and references therein. There are two main types of methods for solving Toeplitz systems: direct methods and iterative methods. Iterative methods consist of classical splitting iteration met
Data Loading...
