A nearly optimal multigrid method for general unstructured grids

详细信息    查看全文

• 作者：Lars Grasedyck ; Lu Wang ; Jinchao Xu
• 关键词：Clustering ; Multigrid ; Auxiliary space ; Finite elements
• 刊名：Numerische Mathematik
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：134
• 期：3
• 页码：637-666
• 全文大小：1,236 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Mathematics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  Numerical and Computational Methods
  Applied Mathematics and Computational Methods of Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：0945-3245
• 卷排序：134

文摘

In this paper, we develop a multigrid method on unstructured shape-regular grids. For a general shape-regular unstructured grid of \({\mathcal 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 \({\mathcal O}(N\log 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 - {\mathcal O}({1}/{\log N})\). Numerical experiments confirm the theoretical bounds and show that the total complexity is in \({\mathcal O}(N\log N)\).