A nearly optimal multigrid method for general unstructured grids (Q728458)

This paper is concerned with a multigrid method on unstructured shape-regular grids. By using the auxiliary space preconditioning technique the authors construct an auxiliary coarse grid hierarchy on which a geometric multigrid method can be applied together with a smoothing on the original grid. For a grid consisting of \(N\) elements, it is shown that such a construction is realized by a cluster tree which can be obtained in \(O(N \log N)\) operations. The tree structure is further used for the definition of the grid hierarchy from coarse to fine. For the constructed grid hierarchy it is obtained that the convergence rate of the multigrid preconditioned conjugate gradient method for an elliptic partial differential equation is \(1-O(1/log N)\). Numerical experiments are also included to support the theoretical findings.