A nearly optimal multigrid method for general unstructured grids

Lars Grasedyck, Lu Wang, Jinchao Xu

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


In this paper, we develop a multigrid method on unstructured shape-regular grids. For a general shape-regular unstructured grid of O(N) elements, we present a construction of an auxiliary coarse grid hierarchy on which a geometric multigrid method can be applied together with a smoothing on the original grid by using the auxiliary space preconditioning technique. Such a construction is realized by a cluster tree which can be obtained in O(Nlog N) operations for a grid of N elements. This tree structure in turn is used for the definition of the grid hierarchy from coarse to fine. For the constructed grid hierarchy we prove that the convergence rate of the multigrid preconditioned CG for an elliptic PDE is 1 - O(1 / log N). Numerical experiments confirm the theoretical bounds and show that the total complexity is in O(Nlog N).
Original languageEnglish (US)
Pages (from-to)637-666
Number of pages30
JournalNumerische Mathematik
Issue number3
StatePublished - Nov 1 2016
Externally publishedYes

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'A nearly optimal multigrid method for general unstructured grids'. Together they form a unique fingerprint.

Cite this