DCT- and DST-based splitting methods for Toeplitz systems

Abstract

New splitting iterative methods for Toeplitz systems are proposed by means of recently developed matrix splittings based on discrete sine and cosine transforms due to Kailath and Olshevsky [Displacement structure approach to discrete-trigonometric transform-based preconditioners of G. Strang type and of T. Chan type, SIAM J. Matrix Anal. Appl. 26 (2005), pp. 706–734]. Theoretical analysis shows that new splitting iterative methods converge to the unique solution of a symmetric Toeplitz linear system. Moreover, an upper bound of the contraction factor of our new splitting iterations is derived. Numerical examples are reported to illustrate the effectiveness of new splitting iterative methods.

Keywords:

• discrete trigonometric transforms
• Toeplitz matrix
• splitting
• iterative methods

2010 AMS Subject Classifications :

• 65F10
• 15B05

Acknowledgements

This research is supported by the NSFC (Nos. 60973015, 61170311), Sichuan Province Sci. and Tech. Research Project (Nos. 2009SPT-1, 2011JY0002, 12ZC1802).

Notes

The real part of the eigenvalues are positive.