Preconditioned iterative methods for block Toeplitz systems
Ta-Kang Ku, C.‐C. Jay Kuo · 1991
An examination is made of the spectral clustering property of the preconditioned matrix R/sup -1/ T, with T generated by two-dimensional rational functions T (z/sub x/, z/sub y/) of order (p/sub x/, q/sub x/, p/sub y/, q/sub y/). A direct consequence of the analysis is that the computational complexity for solving an M N*M N rational block Toeplitz system by the preconditioned conjugate gradient (PCG) method is bounded above by O((M/sup 2/N+M N/sup 2/) log M N), which is much smaller than that required by direct methods, O(M/sup 3/ N/sup 2/). Furthermore, for solving well-conditioned M N*M N block Toeplitz systems, the PCG method requires only O(M N log M N) operations.>