Convergence of the multigrid method for ill-conditioned block Toeplitz systems (Q5937106)

The authors study the solutions of systems of equations with the so called block-Toeplitz-Toeplitz-block coefficient matrices (each block of the \(m \times m\) block-Toeplitz matrix is \(n \times n\) Toeplitz matrix). They are supposed to be generated by a nonnegative function with zeros. For a class of such matrices (the generating function is real-valued even) is shown that: (i) the convergence factor of the two-grid method is uniformly bounded below one independent of \(mn\) and (ii) the full multigrid method has convergence factor depending only on the number of the levels. In the case \(m=2^k-1\), \(n=2^l-1\) it is proved that the cost per iteration is \(O(mn \log mn)\). Results from numerical experiments with four different generating functions are presented and discussed.