×

A hybrid geometric + algebraic multigrid method with semi-iterative smoothers. (English) Zbl 1340.65301

The main theme of this paper is the development of a “hybrid” multigrid approach, applicable to discretized partial differential equations where uniform refinement is applied to some unstructured, “base” mesh of moderate size. The proposal is to use algebraic multigrid to coarsen the base mesh and maintain efficient treatment of the unstructured aspects of the problem, but to use classical geometric multigrid components for levels of the multigrid hierarchy that come from uniform refinement. To motivate their algorithmic choices, the author devote some attention to the choice of consistent interpolation and restriction operators, with respect to finite-element, finite-difference, or finite-volume discretizations, accurately summarizing the well-known choices made in these cases. A multistep Jacobi-like relaxation scheme is proposed, with weights chosen using Chebyshev polynomials. The presented numerical results are generally acceptable, although the authors fail to present a numerical example where their strategy outperforms standard geometric multigrid.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65F08 Preconditioners for iterative methods
65N06 Finite difference methods for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N08 Finite volume methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
35J25 Boundary value problems for second-order elliptic equations

Software:

PETSc; TetGen; Triangle; Matlab; ML
Full Text: DOI

References:

[1] BriggsWL, HensonVE, McCormickSF. A Multigrid Tutorial, 2nd edn. SIAM: Philadelphia, PA, 2000. · Zbl 0958.65128
[2] TrottenbergU, OosterleeCW, SchullerA. Multigrid. Academic Press: San Diego, CA, 2000.
[3] BrannickJ, BrezinaM, FalgoutR, ManteuffelT, McCormickS, RugeJ, SheehanB, XuJ, ZikatanovL. Extending the applicability of multigrid methods. Journal of Physics: Conference Series2006; 46: 443-452.
[4] JiaoX, WangD. Reconstructing high‐order surfaces for meshing. Engineering with Computers2012; 28: 361-373.
[5] BrambleJ, PasciakJ. The analysis of smoothers for multigrid algorithms. Mathematics of Computation1992; 58: 467-488. · Zbl 0771.65082
[6] HackbuschW. Multi‐grid Methods and Applications. Springer‐Verlag: Berlin, Germany, 1985. · Zbl 0595.65106
[7] SampathRS, BirosG. A parallel geometric multigrid method for finite elements on octree meshes. SIAM Journal on Scientific Computing2010; 32: 1361-1392. · Zbl 1213.65144
[8] AdamsMF, DemmelJ. Parallel multigrid solver algorithms and implementations for 3D unstructured finite element problem. In ACM/IEEE Proceedings of sc99: High Performance Networking and Computing: Portland, Oregon, 1999.
[9] MavriplisDJ. Multigrid Techniques for Unstructured Meshes. VKI Lecture Series VKI‐LS 1995‐02, Von Karman Institute for Fluid Dynamics: Rhode‐Saint‐Genese, Belgium, 1995.
[10] MavriplisDJ. An assessment of linear versus nonlinear multigrid methods for unstructured mesh solvers. Journal of Computational Physics2002; 175(1):302-325. DOI: 10.1006/jcph.2001.6948. · Zbl 0995.65099
[11] XuJ. The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids. Computing1996; 56(3):215-235. DOI: 10.1007/BF02238513. · Zbl 0857.65129
[12] MavriplisD, JamesonA. Multigrid solution of the Euler equations on unstructured and adaptive meshes. 3rd Copper Mountain Conference on Multigrid Methods, Copper Mountain, CO, 1987. Paper 23.
[13] HulsemannF, KowarschikM, MohrM, RudeU. Parallel geometric multigrid. In Numerical Solution of Partial Differential Equations on Parallel Computers, volume 51 of LNCSE, chapter 5, 2005; 165-208. · Zbl 1097.65123
[14] BrandtA, McCormickS, RugeJ. Algebraic multigrid (AMG) for sparse matrix equations. In Sparsity and Its Applications. Cambridge University Press, Cambridge, UK, 1984; 257-284. · Zbl 0548.65014
[15] VanekP. Acceleration of convergence of a two‐level algorithm by smoothing transfer operators. Applications of Mathematics1992; 37(4):265-274. · Zbl 0773.65021
[16] BrezinaM, ClearyAJ, FalgoutRD, HensonVE, JonesJE, ManteuffelTA, McCormickSF, RugeJW. Algebraic multigrid based on element interpolation (AMGE). SIAM Journal on Scientific Computing2000; 22(5):1570-1592. DOI: 10.1137/S1064827598344303. · Zbl 0991.65133
[17] AdamsM. Prometheus—scalable unstructured finite element solver.
[18] FalgoutR, ClearyA, JonesJ, ChowE, HensonV, BaldwinC, BrownP, VassilevskiP, YangUM. Hypre home page, 2001.
[19] GeeM, SiefertC, HuJ, TuminaroR, SalaM. Ml 5.0 smoothed aggregation user’s guide. Technical Report SAND2006‐2649, Sandia National Laboratories, Albuquerque, NM, 2006.
[20] SundarH, StadlerG, GhattasO, BirosG. Parallel geometric-algebraic multigrid on unstructured forests of octrees, Proceedings of IEEE/ACM SC12, 2012.
[21] SaadY. Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM: Philadelphia, PA, 2003. · Zbl 1031.65046
[22] SaadY. Numerical Methods for Large Eigenvalue Problems. SIAM: Philadelphia, PA, 2011. · Zbl 1242.65068
[23] BalayS, BuschelmanK, EijkhoutV, GroppWD, KaushikD, KnepleyMG, McInnesLC, SmithBF, ZhangH. PETSc users manual. Technical Report ANL‐95/11 ‐ Revision 3.0.0, Argonne, IL, 2008.
[24] BenitoJJ, UreñaF, GaveteL. Leading‐edge Applied Mathematical Modeling Research. Nova Science Publishers, Inc.: New York, 2008. · Zbl 1141.76003
[25] ShaidurovVV. Multigrid Methods for Finite Elements. Springer: Houten, Netherlands, 1995.
[26] JiaoX, WangD, ZhaH. Simple and effective variational optimization of surface and volume triangulations. Engineering with Computers2011; 27: 81-94.
[27] JiaoX, WangD. Reconstructing high‐order surfaces for meshing. In Proceedings of the 19th International Meshing Roundtable, ShontzS (ed.) (ed.). Springer: Berlin Heidelberg, 2010; 143-160.
[28] GolubGH, VargaRS. Chebyshev semi‐iterative methods, successive overrelaxation iterative methods, and second‐order Richardson iterative methods. Numerische Mathematik. Parts I and II1961; 3: 147-168. · Zbl 0099.10903
[29] VargaR. Matrix Iterative Analysis. Prentice‐Hall: Englewood Cliffs, NJ, 1962. · Zbl 0133.08602
[30] AdamsM, BrezinaM, HuJ, TuminaroR. Parallel multigrid smoothing: polynomial versus Gauss-Seidel. Journal of Computational Physics2003; 188(2):593-610. DOI: 10.1016/S0021‐9991(03)00194‐3. · Zbl 1022.65030
[31] HagemanLA, YoungDM. Applied Iterative Methods. Dover Books on Mathematics, Dover Publications: Mineola, NY, 2004. · Zbl 1059.65028
[32] ClaytonAJ. Further results on polynomials having least maximum modulus over an ellipse in the complex plane. Technical Report AEEW‐M348, United Kingdom Atomic Energy Authority, Winfrith, Dorchester, 1963.
[33] ShewchukJR. Triangle: Engineering a 2d quality mesh generator and Delaunay triangulator. Lecture Notes in Computer Science, Vol. 1148, 1996; 203-222.
[34] SiH. TetGen, a quality tetrahedral mesh generator and three‐dimensional Delaunay triangulator v1.4, 2006.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.