×

On the HSS iteration methods for positive definite Toeplitz linear systems. (English) Zbl 1185.65055

J. Comput. Appl. Math. 224, No. 2, 709-718 (2009); erratum ibid. 235, No. 9, 3112-3114 (2011).
Summary: We study the HSS iteration method for large sparse non-Hermitian positive definite Toeplitz linear systems, which first appears in Bai, Golub and Ng’s paper published in 2003 [Z.-Z. Bai, G. H. Golub and M. K. Ng, SIAM J. Matrix Anal. Appl. 24, No. 3, 603–626 (2003; Zbl 1036.65032)], and HSS stands for the Hermitian and skew-Hermitian splitting of the coefficient matrix \(A\). In this note we use the HSS iteration method based on a special case of the HSS splitting, where the symmetric part \(H=\frac 1 2 (A+A^{\text T})\) is a centrosymmetric matrix and the skew-symmetric part \(S= \frac {1}{2}(A-A^{\text T})\) is a skew-centrosymmetric matrix for a given Toeplitz matrix. Hence, fast methods are available for computing the two half-steps involved in the HSS and IHSS iteration methods. Some numerical results illustrate their effectiveness.

MSC:

65F10 Iterative numerical methods for linear systems

Citations:

Zbl 1036.65032
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24, 603-626 (2003) · Zbl 1036.65032
[2] Bai, Z.-Z.; Golub, G. H.; Lu, L.-Z.; Yin, J.-F., Block triangular and skew-Hermitian splitting methods for positive definite linear systems, SIAM J. Sci. Comput., 26, 844-863 (2005) · Zbl 1079.65028
[3] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., On successive overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations, Numer. Linear Algebra Appl., 14, 319-335 (2007) · Zbl 1199.65097
[4] Chan, R.; Ng, M., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 427-482 (1996) · Zbl 0863.65013
[5] Chan, R.; Ng, M., Toeplitz Preconditioners for Hermite Toeplitz systems, Linear Algebra Appl., 190, 181-208 (1993) · Zbl 0783.65042
[6] Demmel, J. W., Applied Numerical Linear Algebra (1997), SIAM · Zbl 0879.65017
[7] Fassbender, H.; Ikramov, K. D., Computing matrix-vector products with centrosymmetric and centrohermitian matrices, Linear Algebra Appl., 364, 235-241 (2003) · Zbl 1016.65022
[8] Grenander, U.; Szegö, G., Toeplitz Forms and their Applications (1984), Chelsea Publishing: Chelsea Publishing New York · Zbl 0611.47018
[9] T.K. Ku, C.J. Kuo, Preconditioned iterative methods for solving Toeplitz-plus-Hankel systems, Tech. Rep, 181, USC, Signal and Image Processing Institute, June 1991; T.K. Ku, C.J. Kuo, Preconditioned iterative methods for solving Toeplitz-plus-Hankel systems, Tech. Rep, 181, USC, Signal and Image Processing Institute, June 1991 · Zbl 0782.65046
[10] Levinson, N., The wiener RMS (Root Mean Square) error criterion in filter design and prediction, J. Math. Phys., 25, 261-278 (1946)
[11] Liu, Z. Y., Some properties of centrosymmetric matrices, Appl. Math. Comput., 141, 2-3, 17-26 (2002)
[12] Melman, A., Symmetric centrosymmetric matrix-vector multiplication, Linear Algebra Appl., 320, 193-198 (2000) · Zbl 0971.65022
[13] Ng, Michael K., Circulant and skew-circulant splitting methods for Toeplitz systems, J. Comput. Appl. Math., 159, 101-108 (2003) · Zbl 1033.65014
[14] Toeplitz, O., Zur theorie der quadratischen und bilinearen Formen von unendlichvielen veränderlichen, I. Teil: Theorie der L-Formen, Math. Annal., 70, 351-376 (1911)
[15] Trench, W., An algorithm for the inversion of finite Toeplitz matrices, SIAM J. Appl. Math., 12, 515-522 (1964) · Zbl 0131.36002
[16] Tian, Zhaolu; Gu, Chuanqing, The iterative methods for centrosymmetric matrices, Appl. Math. Comput., 187, 902-911 (2007) · Zbl 1121.65035
[17] Yagle, A. E., New analogs of split algorithms for arbitrary Toeplitz-plus-Hankel matrices, IEEE Trans. Signal Process., 39, 2457-2463 (1991) · Zbl 0739.65026
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.