An Aggregation-Based Two-Grid Method for Multilevel Block Toeplitz Linear Systems

This paper presents an aggregation-based two-grid method for solving a multilevel block Toeplitz system. Different from the existing multigrid methods for multilevel block Toeplitz systems, we aggregate a given multilevel block Toeplitz matrix to a new multilevel Toeplitz matrix in such a way that a very sparse coarse grid matrix is constructed in practice. Then, we give an asymptotically tight bound of the convergence rate and provide an algorithm for selecting the optimal prolongation vector and the relaxation factor for our method. Numerical experiments on artificial examples are provided for visualizing the correctness of our analysis, while experiments associated with practical examples show the efficiency of our method in terms of computing time.