An Algebraic Multigrid Preconditioner Based on Aggregation from Top to Bottom

In aggregation based algebraic multigrids, the current schemes are to construct the grid hierarchy from bottom to top, where several nodes on the finer level are clustered into a node on the coarser level step by step. Therefore this kind of scheme is mainly based on local information. In this paper, we present a new aggregation scheme, where the grid hierarchy is formed from top to bottom in a natural way. The adjacent graph of the original coefficient matrix is partitioned first, and then each part is recursively partitioned until some limitations are met for a certain level. Then the grid hierarchy is formed based on the global information, which is completely different from the classical ones. When partitioning graphs, any kind of method can be used, including those based on coordinate information and those based on the element of the matrix only, such as the methods provided in the software package METIS. Finally, the new scheme is validated from the solution of some discrete two-dimensional systems with preconditioned conjugate gradient iterations.