A survey of preconditioners for ill-conditioned Toeplitz systems
Raymond H. Chan, Michael K. Ng, Andy M. Yip · Contemporary mathematics - American Mathematical Society · 2001
. In this paper, we survey some of latest developments in using preconditioned conjugate gradient methods for solving mildly ill-conditioned Toeplitz systems where the condition numbers of the systems grow like O(n ) for some ? 0. This corresponds to Toeplitz matrices generated by functions having zeros of order . Because of the ill-conditioning, the number of iterations required for convergence in the conjugate gradient method will grow like O(n =2 ). Different preconditioners proposed for these Toeplitz matrices are reviewed. The main result is that the total complexity of solving an ill-conditioned Toeplitz system is of O(n log n) operations. 1. Introduction An n-by-n matrix An is said to be Toeplitz if An = 2 6 6 6 6 6 6 4 a 0 a \\Gamma1 \\Delta \\Delta \\Delta a 2\\Gamman a 1\\Gamman a 1 a 0 a \\Gamma1 a 2\\Gamman . . . a 1 a 0 . . . . . . an\\Gamma2 . . . . . . a \\Gamma1 an\\Gamma1 an\\Gamma2 \\Delta \\Delta \\Delta a 1 a 0 3 7 7 7 7 7 7 5 ; (1.1) i.e., An is constant along its...