All Title Author
Keywords Abstract

Publish in OALib Journal
ISSN: 2333-9721
APC: Only $99

ViewsDownloads

Relative Articles

More...

Accelerated Circulant and Skew Circulant Splitting Methods for Hermitian Positive Definite Toeplitz Systems

DOI: 10.1155/2012/973407

Full-Text   Cite this paper   Add to My Lib

Abstract:

We study the CSCS method for large Hermitian positive definite Toeplitz linear systems, which first appears in Ng's paper published in (Ng, 2003), and CSCS stands for circulant and skew circulant splitting of the coefficient matrix . In this paper, we present a new iteration method for the numerical solution of Hermitian positive definite Toeplitz systems of linear equations. The method is a two-parameter generation of the CSCS method such that when the two parameters involved are equal, it coincides with the CSCS method. We discuss the convergence property and optimal parameters of this method. Finally, we extend our method to BTTB matrices. Numerical experiments are presented to show the effectiveness of our new method. 1. Introduction We consider iterative solution of the large system of linear equations where is Hermitian positive definite Toeplitz matrix and . An -by- matrix is said to be Toeplitz if ; that is, is constant along its diagonals. Toeplitz systems arise in a variety of applications, especially in signal processing and control theory. Many direct methods are proposed for solving Toeplitz linear systems. A straightforward application of Gaussian elimination will lead to an algorithm with complexity. There are a number of fast Toeplitz solvers that decrease the complexity to operations, see for instance [1–3]. Around 1980, superfast direct Toeplitz solvers of complexity , such as the one by Ammar and Gragg [4], were also developed. Recent research on using the preconditioned conjugate gradient method as an iterative method for solving Toeplitz systems has brought much attention. One of the main important results of this methodology is that the PCG method has a computational complexity proportional to for a large class of problem [5] and is therefore competitive with any direct method. In [6], an iterative method based on circulant and skew circulant splitting (CSCS) of the Toeplitz matrix was given. The authors have driven an upper bound of the contraction factor of the CSCS iteration which is dependent solely on the spectra of the circulant and the skew circulant matrices involved. In [7] the authors studied the HSS iteration method for large sparse non-Hermitian positive definite Toeplitz linear systems, which first appears in [8]. They used the HSS iteration method based on a special case of the HSS splitting, where the symmetric part is a centrosymmetric matrix and skew-symmetric part is a skew-centrosymmetric matrix for a given Toeplitz matrix and discussed the computational complexity of the HSS and IHSS methods. In this paper we

References

[1]  P. Delsarte and Y. V. Genin, “The split Levinson algorithm,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 34, no. 3, pp. 470–478, 1986.
[2]  N. Levinson, “The Wiener RMS (root mean square) error criterion in filter design and prediction,” Journal of Mathematics and Physics, vol. 25, pp. 261–278, 1947.
[3]  W. F. Trench, “An algorithm for the inversion of finite Toeplitz matrices,” vol. 12, pp. 515–522, 1964.
[4]  G. S. Ammar and W. B. Gragg, “Superfast solution of real positive definite Toeplitz systems,” SIAM Journal on Matrix Analysis and Applications, vol. 9, no. 1, pp. 61–76, 1988.
[5]  G. Strang, “Proposal for Toeplitz matrix calculations,” Studies in Applied Mathematics, vol. 74, no. 2, pp. 171–176, 1986.
[6]  M. K. Ng, “Circulant and skew circulant splitting methods for Toeplitz systems,” Journal of Computational and Applied Mathematics, vol. 159, no. 1, pp. 101–108, 2003.
[7]  C. Gu and Z. Tian, “On the HSS iteration methods for positive definite Toeplitz linear systems,” Journal of Computational and Applied Mathematics, vol. 224, no. 2, pp. 709–718, 2009.
[8]  Z. Z. Bai, G. H. Golub, and M. K. Ng, “Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems,” SIAM Journal on Matrix Analysis and Applications, vol. 24, no. 3, pp. 603–626, 2003.
[9]  T. K. Ku and C. C. J. Kuo, “Design and analysis of Toeplitz preconditioners,” IEEE Transactions on Signal Processing, vol. 40, no. 1, pp. 129–141, 1992.
[10]  M. K. Ng, Iterative Methods for Toeplitz Systems, Oxford University Press, New York, NY, USA, 2004.
[11]  R. H. Chan and M. K. Ng, “Conjugate gradient methods for Toeplitz systems,” SIAM Review, vol. 38, no. 3, pp. 427–482, 1996.
[12]  J. M. Ortega, Numerical Analysis. A Second Course, Academic Press, New York, NY, USA, 1972.
[13]  A. Frommer and D. B. Syzld, “Weighted max norms, splittings, and overlapping additive Schwarz iterations,” Numerische Mathematik, vol. 5, p. 4862, 1997.
[14]  R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, NY, USA, 1985.
[15]  R. H. Chan, “Circulant preconditioners for Hermitian Toeplitz systems,” SIAM Journal on Matrix Analysis and Applications, vol. 10, no. 4, pp. 542–550, 1989.

Full-Text

Contact Us

[email protected]

QQ:3279437679

WhatsApp +8615387084133