The Shifted Classical Circulant and Skew Circulant Splitting Iterative Methods for Toeplitz Matrices

Liu, Zhongyun ; Qin, Xiaorong ; Wu, Nianci ; Zhang, Yulin

Canadian mathematical bulletin, Tome 60 (2017) no. 4, pp. 807-815

Résumé

It is known that every Toeplitz matrix $T$ enjoys a circulant and skew circulant splitting (denoted $\text{CSCS}$ ) i.e., $T=C-S$ a circulant matrix and $S$ a skew circulant matrix. Based on the variant of such a splitting (also referred to as $\text{CSCS}$ ), we first develop classical $\text{CSCS}$ iterative methods and then introduce shifted $\text{CSCS}$ iterative methods for solving hermitian positive definite Toeplitz systems in this paper. The convergence of each method is analyzed. Numerical experiments show that the classical $\text{CSCS}$ iterative methods work slightly better than the Gauss–Seidel $(\text{GS})$ iterative methods if the $\text{CSCS}$ is convergent, and that there is always a constant $\alpha $ such that the shifted $\text{CSCS}$ iteration converges much faster than the Gauss–Seidel iteration, no matter whether the $\text{CSCS}$ itself is convergent or not.

Détail

DOI : 10.4153/CMB-2016-077-5

Mots-clés : 15A23, 65F10, 65F15, Hermitian positive definite, CSCS splitting, Gauss-Seidel splitting, iterative method, Toeplitz matrix

Bibliographie

[1] [1] Ammar, G. and W. Gragg, Superfast solution of real positive definite Toeplitz systems. SIAM J. Matrix Anal. Appl. 9(1988), 61–76. Google Scholar | DOI

[2] [2] Bai, Z.-Z., Golub, G. H., and Ng, M. K., Hermitian and skew-hermitian splitting methods for non-hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl. 24(2003), no. 3, 603–626. Google Scholar | DOI

[3] [3] Bai, Z.-Z., Golub, G. H., L.-Z. Lu, and J.-R Yin, Block triangular and skew-hermitian splitting methods for nonhermitian positive definite systems. SIAM J. Sci. Comput. 26(2005), no.3, 844–863. Google Scholar | DOI

[4] [4] Bai, Z.-Z., Golub, G. H., and J.-Y. Pan, Preconditioned hermitian and skew-hermitian splitting methods for non-hermitian positive semidefinite linear systems. Numer. Math. 98(2004), 1–32. Google Scholar | DOI

[5] [5] Benzi, M., A generalization of the hermitian and skew-hermitian splitting iteration. SIAM J. Matrix Anal. Appl. 31(2009), no. 2, 360–374. Google Scholar | DOI

[6] [6] Benzi, M. and D. Bertaccini, Block preconditioning of real-valued iterative algorithms for complex linear systems. IMA J. Numer. Anal. 28(2008), 598–618. Google Scholar | DOI

[7] [7] Chan, R. H. and Ng, M. K., Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(1996), 427–482. Google Scholar | DOI

[8] [8] Chan, R. H. and X.-Q. Jin, Circulant and skew-circulant preconditioned for skew-hermitian type Toeplitz systems. BIT 31(1991), 632–646. Google Scholar | DOI

[9] [9] Commges, D. and M. Monsion, Fast inversion of triangular Toeplitz matrices. IEEE Trans. Automat. Control 29(1984), 250–251. Google Scholar | DOI

[10] [10] Frommer, A. and D.B. Szyld, H-splitting and two-stage iterative methods. Numer. Math. 63(1992), 345–356. Google Scholar | DOI

[11] [11] Golub, G. and C. Van Loan, Matrix computations. Third ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. Google Scholar

[12] [12] Horn, R. A. and Johnson, C. R., Matrix analysis. Cambridge University Press, Cambridge, 1985. Google Scholar | DOI

[13] [13] Lanzkron, P. J., Rose, D. J., and Syzld, D. B., Convergence of nested classical iterative methods for linear systems. Numer. Math. 58(1991), 685–702. Google Scholar | DOI

[14] [14] Lin, R-R., W.-K. Ching, and Ng, M. K., Fast inversion of triangular Toeplitz matrices. Theoret. Comput. Sci. 315(2004), 511–523. Google Scholar | DOI

[15] [15] Liu, Z. Y., Wu, H. B., and L. Lin, The two-stage iterative methods for symmetric positive definite matrices. Appl. Math. Comput. 114(2000), 1–12. Google Scholar | DOI

[16] [16] Nabben, R., A note on comparison theorems for splittings and multisplittings of hermitian positive definite matrices. Linear Algebra Appl. 233(1996), 67–80. Google Scholar | DOI

[17] [17] Ng, M. K., Circulant and skew-circulant splitting methods for Toeplitz systems. J. Comput. Appl. Math. 159(2003), 101–108. Google Scholar | DOI

[18] [18] Ortega, J. M., Numerical analysis: A second course. Academic Press, New York, 1972. Google Scholar

[19] [19] Saad, Y., Iterative methods for sparse Linear systems. Secon ed., SIAM, Philadelphia, PA, 2000. Google Scholar