Preconditioned iterative methods for block Toeplitz systems

An examination is made of the spectral clustering property of the preconditioned matrix R^-1 T, with T generated by two-dimensional rational functions T ( z_x, z_y) of order (p_x, q_x, p_y, q_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²N+M N²) log M N), which is much smaller than that required by direct methods, O(M³ N²). Furthermore, for solving well-conditioned M N×M N block Toeplitz systems, the PCG method requires only O (M N log M N) operations