Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions


Authors: Man-Chung Yeung and Raymond H. Chan
Journal: Math. Comp. 61 (1993), 701-718
MSC: Primary 65F35
DOI: https://doi.org/10.1090/S0025-5718-1993-1195423-4
MathSciNet review: 1195423
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the solution of n-by-n Toeplitz systems $ {T_n}x = b$ by preconditioned conjugate gradient methods. The preconditioner $ {C_n}$ is the T. Chan circulant preconditioner, which is defined to be the circulant matrix that minimizes $ {\left\Vert {{B_n} - {T_n}} \right\Vert _F}$ over all circulant matrices $ {B_n}$. For Toeplitz matrices generated by positive $ 2\pi $-periodic continuous functions, we have shown earlier that the spectrum of the preconditioned system $ C_n^{ - 1}{T_n}$ is clustered around 1 and hence the convergence rate of the preconditioned system is superlinear. However, in this paper, we show that if instead the generating function is only piecewise continuous, then for all $ \varepsilon $ sufficiently small, there are $ O(\log n)$ eigenvalues of $ C_n^{ - 1}{T_n}$ that lie outside the interval $ (1 - \varepsilon,1 + \varepsilon)$. In particular, the spectrum of $ C_n^{ - 1}{T_n}$ cannot be clustered around 1. Numerical examples are given to verify that the convergence rate of the method is no longer superlinear in general.


References [Enhancements On Off] (What's this?)

  • [1] G. Ammar and W. Gragg, Superfast solution of real positive definite Toeplitz systems, SIAM J. Matrix Anal. Appl. 9 (1988), 61-76. MR 938136 (89b:65065)
  • [2] R. Chan, The spectrum of a family of circulant preconditioned Toeplitz systems, SIAM J. Numer. Anal. 26 (1989), 503-506. MR 987404 (90f:65048)
  • [3] -, Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal. 11 (1991), 333-345. MR 1118960 (92f:65041)
  • [4] R. Chan and K. Ng, Fast iterative solvers for Toeplitz-plus-band systems, SIAM J. Sci. Statist. Comput. (to appear).
  • [5] R. Chan and G. Strang, Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput. 10 (1989), 104-119. MR 976165 (90d:65069)
  • [6] R. Chan and M. Yeung, Circulant preconditioners for Toeplitz matrices with positive continuous generating functions, Math. Comp. 58 (1992), 233-240. MR 1106960 (92e:65040)
  • [7] -, Jackson's Theorem and circulant preconditioned Toeplitz systems, J. Approx. Theory 70 (1992), 191-205. MR 1172018 (93c:65046)
  • [8] -, Circulant preconditioners constructed from kernels, SIAM J. Numer. Anal. 29 (1992), 1093-1103. MR 1173187 (93f:65029)
  • [9] T. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. 9 (1988), 766-771. MR 945937 (89e:65046)
  • [10] T. Huckle, Circulant and skew-circulant matrices for solving Toeplitz matrix problems, SIAM J. Matrix Anal. Appl. (to appear). MR 1168078 (93e:65073)
  • [11] T. Ku and C. Kuo, Design and analysis of Toeplitz preconditioners, IEEE Trans. Signal Process. 40 (1991), 129-141.
  • [12] Z. Nehari, On bounded bilinear forms, Ann. of Math. (2) 65 (1957), 153-162. MR 0082945 (18:633f)
  • [13] G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math. 74 (1986), 171-176.
  • [14] M. Tismenetsky, A decomposition of Toeplitz matrices and optimal circulant preconditioning, Linear Algebra Appl. 154 (1991), 105-121. MR 1113141 (92c:65056)
  • [15] L. Trefethen, Approximation theory and numerical linear algebra, Algorithms for Approximation II (M. Cox and J. Mason, eds.), Chapman and Hall, London, 1990. MR 1071991 (91j:65063)
  • [16] E. Tyrtyshnikov, Optimal and super-optimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992), 459-473. MR 1152763 (92k:65062)
  • [17] -, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl. (to appear). MR 1366576 (96m:15018)
  • [18] J. Walker, Fourier analysis, Oxford Univ. Press, New York, 1988. MR 957507 (90b:42001)
  • [19] H. Widom, Hankel matrices, Trans. Amer. Math. Soc. 121 (1966), 1-35. MR 0187099 (32:4553)
  • [20] J. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422 (32:1894)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F35

Retrieve articles in all journals with MSC: 65F35


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1195423-4
Keywords: Toeplitz matrix, circulant matrix, generating function, preconditioned conjugate gradient method, superlinear convergence rate
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society