×
Chaysri, Thaniporn; Hadjidimos, Apostolos; Noutsos, Dimitrios; Tachyridis, Grigorios

Band-times-circulant preconditioners for non-symmetric real Toeplitz systems with unknown generating function. (English) Zbl 1482.65041

East Asian J. Appl. Math. 12, No. 2, 285-322 (2022).
Summary: In this paper we study the preconditioning of \(n \times n\) non-symmetric, real Toeplitz systems, when the generating function of the coefficient matrix \(T_n\) is not known a priori, but we know that a generating function \(f\) exists related to the matrix sequence \(\{T_n\}\), \(T_n = T_n (f)\), with \(f\) smooth enough. The proposed preconditioner is derived as a combination of a band Toeplitz and a circulant matrix. We give details for the construction of the proposed preconditioner, by the entries of \(T_n\) and we study the cluster of the eigenvalues, as well as of the singular values, of the sequences of the coefficient matrices related to the preconditioned systems. Theoretical results prove the efficiency of the Preconditioned Generalized Minimal Residual method (PGMRES) and the Preconditioned Conjugate Gradient method of Normal Equations (PCGN). Such efficiency is also shown in demonstrating numerical examples, using the proposed preconditioning technique.

MSC:

65F08 Preconditioners for iterative methods
65F10 Iterative numerical methods for linear systems
15B05 Toeplitz, Cauchy, and related matrices
15A18 Eigenvalues, singular values, and eigenvectors

Keywords:

non-symmetric; Toeplitz; band-times-circulant; preconditioner

Software:

ILUT
Cite Review PDF
Full Text: DOI

References:

[1] O. Axelsson, Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations, Linear Algebra Appl. 29, 1-16 (1980). · Zbl 0439.65020
[2] Z.-Z. Bai, Sharp error bounds of some Krylov subspace methods for non-Hermitian linear systems, Appl. Math. Comput. 109(2-3), 273-285 (2000). · Zbl 1026.65028
[3] Z.-Z. Bai, Several splittings for non-Hermitian linear systems, Sci. China Math. 51(8), 1339-1348 (2008). · Zbl 1168.65014
[4] Z.-Z. Bai, Motivations and realizations of Krylov subspace methods for large sparse linear systems, J. Comput. Appl. Math. 283, 71-78 (2015). · Zbl 1311.65032
[5] Z.-Z. Bai, Quasi-HSS iteration methods for non-Hermitian positive definite linear systems of strong skew-Hermitian parts, Numer. Linear Algebra Appl. 25(4), e2116 (2018). · Zbl 1513.65063
[6] Z.-Z. Bai, R.H. Chan and Z.-R. Ren, On sinc discretization and banded preconditioning for lin-ear third-order ordinary differential equations, Numer. Linear Algebra Appl. 18(3), 471-497 (2011). · Zbl 1245.65095
[7] Z.-Z. Bai, R.H. Chan and Z.-R. Ren, On order-reducible sinc discretizations and block-diagonal preconditioning methods for linear third-order ordinary differential equations, Numer. Linear Algebra Appl. 21(1), 108-135, (2014). · Zbl 1324.65105
[8] Z.-Z. Bai, Y.-M. Huang and M.K. Ng, On preconditioned iterative methods for Burgers equations, SIAM J. Sci. Comput. 29(1), 415-439 (2007). · Zbl 1144.65034
[9] Z.-Z. Bai, Y.-M. Huang and M.K. Ng, On preconditioned iterative methods for certain time-dependent partial differential equations, SIAM J. Numer. Anal. 47(2), 1019-1037 (2009). · Zbl 1195.65032
[10] Z.-Z. Bai and K.-Y. Lu, Fast matrix splitting preconditioners for higher dimensional spatial frac-tional diffusion equations, J. Comput. Phys. 404, 109117, (2020). · Zbl 1453.65062
[11] Z.-Z. Bai, K.-Y. Lu and J.-Y. Pan, Diagonal and Toeplitz splitting iteration methods for diagonal-plus-Toeplitz linear systems from spatial fractional diffusion equations, Numer. Linear Algebra Appl. 24(4), e2093 (2017). · Zbl 1463.65040
[12] Z.-Z. Bai and M.K. Ng, Preconditioners for nonsymmetric block Toeplitz-like-plus-diagonal linear systems, Numer. Math. 96(2), 197-220, (2003). · Zbl 1080.65021
[13] Z.-Z. Bai and J.-Y. Pan, Matrix Analysis and Computations, SIAM (2021). · Zbl 07417710
[14] Z.-Z. Bai and Z.-R. Ren, Block-triangular preconditioning methods for linear third-order ordinary differential equations based on reduced-order sinc discretizations, Japan J. Industr. Appl. Math. 30(3), 511-527 (2013). · Zbl 1291.65226
[15] I. Bendixson, Sur les racines d’une équation fondamentale, Acta Math. 25, 359-365 (1902). · JFM 33.0106.01
[16] M. Benzi, Preconditioning techniques for large linear systems: a survey, J. Comput. Phys. 182 (2), 418-477 (2002). · Zbl 1015.65018
[17] M. Bôcher, Introduction to the Theory of Fourier’s Series, Ann. Math. 7(3), Second series, 81-152 (1906). · JFM 37.0285.01
[18] J.M. Bogoya, A. Böttcher, S.M. Grudsky and E.A. Maximenko, Eigenvalues of Hermitian Toeplitz matrices with smooth simple-loop symbols, J. Math. Anal. Appl. 422(2), 1308-1334 (2015). · Zbl 1302.65086
[19] A. Böttcher and B. Silbermann, Introduction to Large Truncated Toeplitz Matrices, Springer Science & Business Media (1999). · Zbl 0916.15012
[20] R.H. Chan, Circulant preconditioners for Hermitian Toeplitz systems, SIAM J. Matrix Anal. Appl. 10(4), 542-550 (1989). · Zbl 0684.65035
[21] R.H. Chan, Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal. 11, 333-345, (1991). · Zbl 0737.65022
[22] R.H. Chan, W.-K. Ching, Toeplitz-circulant preconditioners for Toeplitz systems and their applica-tions to queueing networks with batch arrivals, SIAM J. Sci. Comput., 17(3), 762-772 (1996). · Zbl 0859.65030
[23] R.H. Chan and M.K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev. 38(3), 427-482 (1996). · Zbl 0863.65013
[24] R.H. Chan, D. Potts and G. Steidl, Preconditioners for nondefinite Hermitian Toeplitz systems, SIAM J. Matrix Anal. Appl. 22(3), 647-665 (2000). · Zbl 0983.65043
[25] R.H. Chan and M.C. Yeung, Circulant preconditioners for complex Toeplitz matrices, SIAM J. Numer. Anal. 30(4), 1193-1207 (1993). · Zbl 0787.65017
[26] T.F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9(4), 766-771 (1988). · Zbl 0646.65042
[27] T. Chaysri, A. Hadjidimos, D. Noutsos and G. Tachyridis, Band preconditioners for non-sym-metric real Toeplitz systems with unknown generating function, in: Proceedings of the 25th In-ternational Conference on Circuits, Systems, Communications and Computers, IEEE. (To appear)
[28] J.W. Demmel, Applied Numerical Linear Algebra, SIAM (1997). · Zbl 0879.65017
[29] F. Di Benedetto, G. Fiorentino and S. Serra, CG preconditioning for Toeplitz matrices, Computers Math. Applic. 25(6), 35-45 (1993). · Zbl 0782.65063
[30] S-E. Ekström and C. Garoni, A matrix-less and parallel interpolation-extrapolation algorithm for computing the eigenvalues of preconditioned banded symmetric Toeplitz matrices, Numer. Algor. 80(3), 819-848 (2019). · Zbl 1455.65051
[31] S-E. Ekström, C. Garoni and S. Serra-Capizzano, Are the eigenvalues of banded symmetric Toe-plitz matrices known in almost closed form?, Exp. Math. 27(4), 478-487 (2018). · Zbl 1405.15037
[32] S-E. Ekström and S. Serra-Capizzano, Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols, Numer. Linear Algebra Appl. 25(5), e2137 (2018). · Zbl 1513.65095
[33] P. Ferrari, I. Furci, S. Hon, M.A. Mursaleen and S. Serra-Capizzano, The eigenvalue distribution of special 2-by-2 block matrix-sequences with applications to the case of symmetrized Toeplitz structures, SIAM J. Matrix Anal. Appl. 40(3), 1066-1086 (2019). · Zbl 1426.15041
[34] E. Hewitt, R.E. Hewitt, The Gibbs-Wilbraham phenomenon: An episode in Fourier analysis, Arch. Hist. Exact Sci. 21, 129-160 (1979). · Zbl 0424.42002
[35] M.A. Hirsch, Sur les racines d’une équation fondamentale, Acta Math. 25, 367-370, (1902). · JFM 33.0106.02
[36] S. Hon and A.J. Wathen, Circulant preconditioners for analytic functions of Toeplitz matrices, Numer. Algor. 79(4), 1211-1230 (2018). · Zbl 1404.65015
[37] N.M. Nachtigal, S.C. Reddy and L.N. Trefethen, How fast are nonsymmetric matrix iterations?, SIAM J. Matrix Anal. Appl. 13(3), 778-795 (1992). · Zbl 0754.65036
[38] M.K. Ng, Iterative Methods for Toeplitz Systems, Oxford University Press (2004). · Zbl 1059.65031
[39] M.K. Ng and R.H. Chan, Scientific applications of iterative Toeplitz solvers, Calcolo, 33(3-4), 249-267 (1996). · Zbl 0904.65038
[40] S. Noschese, L. Pasquini and L. Reichel, Tridiagonal Toeplitz matrices: properties and novel applications, Numer. Linear Algebra Appl. 20(2), 302-326 (2013). · Zbl 1289.65082
[41] D. Noutsos, S. Serra-Capizzano and P. Vassalos, A preconditioning proposal for ill-conditioned Hermitian two-level Toeplitz systems, Numer. Linear Algebra Appl. 12(2-3), 231-239 (2005). · Zbl 1164.65401
[42] D. Noutsos, S. Serra-Capizzano and P. Vassalos, Asymptotic behavior of the condition number of two-level Toeplitz matrix sequences, Linear Algebra Appl. 395, 121-140 (2005). · Zbl 1066.15002
[43] D. Noutsos and G. Tachyridis, Band Toeplitz preconditioners for non-symmetric real Toeplitz systems by preconditioned GMRES method, J. Comput. Appl. Math. 373, 112250, (2020). · Zbl 1473.65029
[44] D. Noutsos and G. Tachyridis, Band-times-circulant preconditioners for non-symmetric Toeplitz systems, BIT Numer. Math. (2021). doi: https://doi.org/10.1007/s10543-021-00883-y (To appear) · Zbl 1473.65029 · doi:10.1007/s10543-021-00883-y
[45] D. Noutsos and P. Vassalos, New band Toeplitz preconditioners for ill-conditioned symmetric positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl. 23, 728-743 (2002). · Zbl 1011.65014
[46] D. Noutsos and P. Vassalos, Superlinear convergence for PCG using band plus algebra precondi-tioners for Toeplitz systems, Comput. Math. Appl. 56, 1255-1270 (2008). · Zbl 1155.65322
[47] J. Pestana, A.J. Wathen, A preconditioned minres method for nonsymmetric Toeplitz matrices, SIAM J. Matrix Anal. Appl. 36(1), 273-288 (2015). · Zbl 1315.65034
[48] H. Rutishauser, “On Test Matrices.” Programmation en Mathematiques Numeriques, Editions Centre Nat Recherche Sci, Paris, 165, 349-365 (1966). · Zbl 0209.17502
[49] Y. Saad, ILUT: A dual threshold incomplete LU factorization, Numer. Linear Algebra Appl. 1(4), 387-402, (1994). · Zbl 0838.65026
[50] Y. Saad and M.H. Schultz, GMRES: A generalized minimal residual algorithm for solving non-symmetric linear systems, SIAM J. Sci. and Stat. Comput. 7(3), 856-869, (1986). · Zbl 0599.65018
[51] E.W. Sachs and A.K. Strauss, Efficient solution of a partial integro-differential equation in fi-nance, Appl. Numer. Math. 58(11), 1687-1703 (2008). · Zbl 1155.65109
[52] S. Serra, Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptoti-cally ill-conditioned positive definite Toeplitz systems, Math. Comp. 66, 651-665 (1997). · Zbl 0864.65019
[53] S. Serra, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl. 270(1-3), 109-129 (1998). · Zbl 0892.15014
[54] S. Serra, How to choose the best iterative strategy for symmetric Toeplitz systems, SIAM J. Numer. Anal. 36(4), 1078-1103 (1999). · Zbl 0938.65065
[55] S. Serra-Capizzano, An ergodic theorem for classes of preconditioned matrices, Linear Algebra Appl. 282(1-3), 161-183 (1998). · Zbl 0935.65026
[56] S. Serra-Capizzano, Superlinear PCG methods for symmetric Toeplitz systems, Math. Comput. 68(226), 793-803 (1999). · Zbl 1043.65066
[57] S. Serra-Capizzano, Spectral behavior of matrix sequences and discretized boundary value prob-lems, Linear Algebra Appl. 337(1-3), 37-78 (2001). · Zbl 1004.15012
[58] G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74, 171-176 (1986). · Zbl 0621.65025
[59] L.N. Trefethen and D. Bau III, Numerical Linear Algebra, SIAM (1997). · Zbl 0874.65013
[60] E.E. Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clus-tering, Linear Algebra Appl. 232, 1-43 (1996). · Zbl 0841.15006
[61] E.E. Tyrtyshnikov and N.L. Zamarashkin, Thin structure of eigenvalue clusters for non-Hermitian Toeplitz matrices, Linear Algebra Appl. 292(1-3), 297-310 (1999). · Zbl 0942.47016
[62] M.C. Yeung and R.H. Chan, Circulant preconditioners for Toeplitz matrices with piecewise con-tinuous generating functions, Math. Comput. 61(204), 701-718 (1993). · Zbl 0788.65039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.