Convergence of the multigrid method for ill-conditioned block Toeplitz systems
We study the solutions of block Toeplitz systems A(mn)u = b by the multigrid method (MGM). Here the block Toeplitz matrices A(mn) are generated by a nonnegative function f(x; y) with zeros. Since the matrices A(mn) are ill-conditioned, the convergence factor of classical iterative methods will approach 1 as the size of the matrices becomes large. These classical methods, therefore, are not applicable for solving ill-conditioned systems. The MGM is then proposed in this paper. For a class of block Toeplitz matrices, we show that the convergence factor of the two-grid method (TGM) is uniformly bounded below 1 independent of mn and the full MGM has convergence factor depending only on the number of levels. The cost per iteration for the MGM is of O(mn log mn) operations. Numerical results are given to explain the convergence rate.
multigrid method block toeplitz matrix