BANDED TOEPLITZ PRECONDITIONERS FOR TOEPLITZMATRICES FROM SINC METHODS

Zhi-Ru Ren

1. LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
• Received:2011-06-24 Revised:2012-03-12 Online:2012-09-15 Published:2012-09-24
• Supported by:

This work is supported by State Key Laboratory of Scientific/Engineering Computing, Chinese Academy of Sciences. The author is very much grateful to the anonymousreferees for their constructive suggestions and helpful comments which have led to significant improvement of the original manuscript of this paper.

Zhi-Ru Ren. BANDED TOEPLITZ PRECONDITIONERS FOR TOEPLITZMATRICES FROM SINC METHODS[J]. Journal of Computational Mathematics, 2012, 30(5): 533-543.

We give general expressions, analyze algebraic properties and derive eigenvalue boundsfor a sequence of Toeplitz matrices associated with the sinc discretizations of various ordersof differential operators. We demonstrate that these Toeplitz matrices can be satisfactorilypreconditioned by certain banded Toeplitz matrices through showing that the spectra ofthe preconditioned matrices are uniformly bounded. In particular, we also derive eigenvaluebounds for the banded Toeplitz preconditioners. These results are elementary inconstructing high-quality structured preconditioners for the systems of linear equationsarising from the sinc discretizations of ordinary and partial differential equations, and areuseful in analyzing algebraic properties and deriving eigenvalue bounds for the correspondingpreconditioned matrices. Numerical examples are given to show effectiveness of thebanded Toeplitz preconditioners.

CLC Number:

 [1] Z.Z. Bai, R.H. Chan and Z.R. Ren, On sinc discretization and banded preconditioning for linearthird-order ordinary differential equations, Numer. Linear Algebra Appl., 18 (2011), 471-497.[2] Z.Z. Bai, Y.M. Huang and M.K. Ng, On preconditioned iterative methods for Burgers equations,SIAM J. Sci. Comput., 29 (2007), 415-439.[3] Z.Z. Bai, Y.M. Huang and M.K. Ng, On preconditioned iterative methods for certain timedependentpartial differential equations, SIAM J. Numer. Anal., 47 (2009), 1019-1037.[4] Z.Z. Bai and M.K. Ng, Preconditioners for nonsymmetric block Toeplitz-like-plus-diagonal linearsystems, Numer. Math., 96 (2003), 197-220.[5] F.D. Benedetto, Solution of Toeplitz normal equations by sine transform based preconditioning,Linear Algebra Appl., 285 (1998), 229-255.[6] R.H. Chan, Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions,IMA J. Numer. Anal., 11 (1991), 333-345.[7] R.H. Chan and M.K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38(1996), 427-482.[8] U. Grenander and G. Szegö, Toeplitz Forms and Their Applications, 2nd Ed., Chelsea PublishingCompany, New York, 1984.[9] X.Q. Jin, Developments and Applications of Block Toeplitz Iterative Solvers, Kluwer AcademicPublishers Group, Science Press, Beijing, 2002.[10] J. Lund and K. Bowers, Sinc Methods for Quadrature and Differential Equations, SIAM, Philadelphia,1992.[11] A.C. Morlet, Convergence of the sinc method for a fourth-order ordinary differential equationwith an application, SIAM J. Numer. Anal., 32 (1995), 1475-1503.[12] M.K. Ng, Fast iterative methods for symmetric sinc-Galerkin systems, IMA J. Numer. Anal., 19(1999), 357-373.[13] M.K. Ng and D. Potts, Fast iterative methods for sinc systems, SIAM J. Matrix Anal. Appl., 24(2002), 581-598.[14] F. Stenger, Numerical Methods Based on Sinc and Analytic Functions, Springer Ser. Comput.Math., Springer-Verlag, 1993.[15] J.H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, Oxford, 1965.
 [1] Fang Chen, Yaolin Jiang, Qingquan Liu. ON STRUCTURED VARIANTS OF MODIFIED HSS ITERATION METHODS FOR COMPLEX TOEPLITZ LINEAR SYSTEMS [J]. Journal of Computational Mathematics, 2013, 31(1): 57-67. [2] Jian-feng Cai,Michael K. Ng,Yi-min Wei. MODIFIED NEWTON'S ALGORITHM FOR COMPUTING THE GROUP INVERSESOF SINGULAR TOEPLITZ MATRICES [J]. Journal of Computational Mathematics, 2006, 24(5): 647-656. [3] Ji Hua XU, Jing Hui ZHAO. MOMENT GENERATING FUNCTIONS OF RANDOM VARIABLES AND ASYMPTOTIC BEHAVIOUR FOR GENERALIZED FELLER OPERATORS [J]. Journal of Computational Mathematics, 2000, 18(2): 173-182. [4] Kang Feng. THE CALCULUS OF GENERATING FUNCTIONS AND THE FORMAL ENERGY FORHAMILTONIAN ALGORITHMS [J]. Journal of Computational Mathematics, 1998, 16(6): 481-498. [5] Kang Feng. CONTACT ALGORITHMS FOR CONTACT DYNAMICAL SYSTEMS [J]. Journal of Computational Mathematics, 1998, 16(1): 1-014.
Viewed
Full text

Abstract