Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
adaptive mesh refinement; error estimation; finite elements; geometric multigrid
adaptive mesh refinement; error estimation; finite elements; geometric multigrid
Summary:
This work introduces an adaptive mesh refinement technique for hierarchical hybrid grids with the goal to reach scalability and maintain excellent performance on massively parallel computer systems. On the block-structured hierarchical hybrid grids, this is accomplished by using classical, unstructured refinement only on the coarsest level of the hierarchy, while keeping the number of structured refinement levels constant over the whole domain. This leads to a compromise, where the excellent performance characteristics of hierarchical hybrid grids can be maintained at the price that the flexibility of generating locally refined meshes is constrained. Furthermore, the mesh adaptivity often relies on a posteriori error estimators or error indicators, which tend to become computationally expensive. Again, with the goal of preserving scalability and performance, a method is proposed that leverages the grid hierarchy and the full multigrid scheme. Utilizing the sequence of approximations on the nested hierarchy of grids permits the computation of a cheap error estimator that is well-suited for large-scale parallel computing. We present the theoretical foundations for both global and local error estimates, and present a rigorous analysis of their effectivity. The proposed method, including the error estimator and the adaptive coarse grid refinement, is implemented in the finite element framework HyTeG. Extensive numerical experiments are conducted to validate the effectiveness, as well as performance and scalability.
References:
[1] Ainsworth, M., Oden, J. T.: A posteriori error estimation in finite element analysis. Comput. Methods Appl. Mech. Eng. 142 (1997), 1-88. DOI 10.1016/S0045-7825(96)01107-3 | MR 1442375 | Zbl 0895.76040
[2] Apel, T., Sändig, A.-M., Whiteman, J. R.: Graded mesh refinement and error estimates for finite element solutions of elliptic boundary value problems in non-smooth domains. Math. Methods Appl. Sci. 19 (1996), 63-85. DOI 10.1002/(SICI)1099-1476(19960110)19:1<63::AID-MMA764>3.0.CO;2-S | MR 1365264 | Zbl 0838.65109
[3] Aulisa, E., Ke, G., Lee, S.-Y.: An adaptive mesh refinement strategy for finite element solution of the elliptic problem. Comput. Math. Appl. 76 (2018), 224-244. DOI 10.1016/j.camwa.2018.04.011 | MR 3809435 | Zbl 1419.65101
[4] Axelsson, O., Blaheta, R.: Two simple derivations of universal bounds for the CBS inequality constant. Appl. Math., Praha 49 (2004), 57-72. DOI 10.1023/B:APOM.0000024520.06175.8b | MR 2032148 | Zbl 1099.65103
[5] Babuška, I., Rheinboldt, W. C.: A-posteriori error estimates for the finite element method. Int. J. Numer. Methods Eng. 12 (1978), 1597-1615. DOI 10.1002/nme.1620121010 | Zbl 0396.65068
[6] Babuška, I., Rosenzweig, M. B.: A finite element scheme for domains with corners. Numer. Math. 20 (1972), 1-21. DOI 10.1007/BF01436639 | MR 0323129 | Zbl 0252.65084
[7] Babuška, I., Strouboulis, T.: The Finite Element Methods and Its Reliability. Oxford University Press, Oxford (2001). DOI 10.1093/oso/9780198502760.001.0001 | MR 1857191 | Zbl 0995.65501
[8] Bai, D., Brandt, A.: Local mesh refinement multilevel techniques. SIAM J. Sci. Stat. Comput. 8 (1987), 109-134. DOI 10.1137/0908025 | MR 0879406 | Zbl 0619.65091
[9] Bank, R. E.: PLTMG: A Software Package for Solving Elliptic Partial Differential Equations User's Guide 8.0. Software-Environments-Tools 5. SIAM, Philadelphia (1998). DOI 10.1137/1.9780898719635 | MR 1621384 | Zbl 0990.65500
[10] Bank, R. E., Weiser, A.: Some a posteriori error estimators for elliptic partial differential equations. Math. Comput. 44 (1985), 283-301. DOI 10.2307/2007953 | MR 0777265 | Zbl 0569.65079
[11] Becker, R., Rannacher, R.: An optimal control approach to a posteriori error estimation in finite element methods. Acta Numerica 10 (2001), 1-102. DOI 10.1017/S0962492901000010 | MR 2009692 | Zbl 1105.65349
[12] Bergen, B. K., Hülsemann, F.: Hierarchical hybrid grids: Data structures and core algorithms for multigrid. Numer. Linear Algebra Appl. 11 (2004), 279-291. DOI 10.1002/nla.382 | MR 2065817 | Zbl 1164.65517
[13] Bernert, K.: $\tau$-extrapolation -- Theoretical foundation, numerical experiment, and application to Navier-Stokes equations. SIAM J. Sci. Comput. 18 (1997), 460-478. DOI 10.1137/S1064827594276266 | MR 1433789 | Zbl 0952.35095
[14] Bey, J.: Tetrahedral grid refinement. Computing 4 (1995), 355-378. DOI 10.1007/BF02238487 | MR 1370107 | Zbl 0839.65135
[15] Blaheta, R.: Nested tetrahedral grids and strengthened C.B.S. inequality. Numer. Linear Algebra Appl. 10 (2003), 619-637. DOI 10.1002/nla.340 | MR 2030627 | Zbl 1071.65164
[16] Blaheta, R.: Hierarchical FEM: Strengthened CBS inequalities, error estimates and iterative solvers. Programs and Algorithms of Numerical Mathematics Institute of Mathematics AS CR, Prague (2006), 24-29.
[17] Böhm, F., Bauer, D., Kohl, N., Alappat, C. L., Thönnes, D., Mohr, M., Köstler, H., Rüde, U.: Code generation and performance engineering for matrix-free finite element methods on hybrid tetrahedral grids. SIAM J. Sci. Comput. 47 (2025), B131--B159. DOI 10.1137/24M1653756 | MR 4856616 | Zbl 1563.65225
[18] Brandt, A.: Multi-level adaptive techniques (MLAT) for partial differential equations: Ideas and software. Mathematical Software III Academic Press, New York (1977), 277-318. DOI 10.1016/B978-0-12-587260-7.50015-7 | MR 0474858 | Zbl 0407.68037
[19] Buttari, A., Huber, M., Leleux, P., Mary, T., Rüde, U., Wohlmuth, B.: Block low-rank single precision coarse grid solvers for extreme scale multigrid methods. Numer. Linear Algebra Appl. 29 (2022), Article ID e2407, 15 pages. DOI 10.1002/nla.2407 | MR 4372443 | Zbl 1538.65583
[20] Ciarlet, P. G.: The Finite Element Method for Elliptic Problems. Classics in Applied Mathematics. SIAM, Philadelphia (2002). DOI 10.1137/1.9780898719208 | MR 1930132 | Zbl 0999.65129
[21] Dostál, Z., Horák, D., Kružík, J., Brzobohatý, T., Vlach, O.: Highly scalable hybrid domain decomposition method for the solution of huge scalar variational inequalities. Numer. Algorithms 91 (2022), 773-801. DOI 10.1007/s11075-022-01281-3 | MR 4480269 | Zbl 1502.65198
[22] Egger, H., Rüde, U., Wohlmuth, B.: Energy-corrected finite element methods for corner singularities. SIAM J. Numer. Anal. 52 (2014), 171-193. DOI 10.1137/120871377 | MR 3154149 | Zbl 1293.65150
[23] Elman, H. C.: Multigrid and Krylov subspace methods for the discrete Stokes equations. Int. J. Numer. Methods Fluids 22 (1996), 755-770. DOI 10.1002/(SICI)1097-0363(19960430)22:8<755::AID-FLD377>3.0.CO;2-1 | Zbl 0865.76078
[24] Ferraz-Leite, S., Ortner, C., Praetorius, D.: Convergence of simple adaptive Galerkin schemes based on $h-h/2$ error estimators. Numer. Math. 116 (2010), 291-316. DOI 10.1007/s00211-010-0292-9 | MR 2672266 | Zbl 1198.65213
[25] Fung, F., Stals, L., Deng, Q.: Fault-tolerant parallel multigrid method on unstructured adaptive mesh. SIAM J. Sci. Comput. 46 (2024), S145--S169. DOI 10.1137/23M1582904 | MR 4813195 | Zbl 07931243
[26] Gmeiner, B., Huber, M., John, L., Rüde, U., Wohlmuth, B.: A quantitative performance study for Stokes solvers at the extreme scale. J. Comput. Sci. 17 (2016), 509-521. DOI 10.1016/j.jocs.2016.06.006 | MR 3580776
[27] Gmeiner, B., Köstler, H., Stürmer, M., Rüde, U.: Parallel multigrid on hierarchical hybrid grids: A performance study on current high performance computing clusters. Concurrency Comput. Pract. Exp. 26 (2014), 217-240. DOI 10.1002/cpe.2968
[28] Gradl, T.: Data Structures and Algorithms for the Optimization of Hierarchical Hybrid Multigrid Methods: Ph.D. Thesis. Friedrich-Alexander-Universität, Erlangen (2015).
[29] Grisvard, P.: Elliptic Problems in Nonsmooth Domains. Classics in Applied Mathematics 69. SIAM, Philadelphia (2011). DOI 10.1137/1.9781611972030 | MR 3396210 | Zbl 1231.35002
[30] Hairer, E., Nørsett, S. P., Wanner, G.: Solving Ordinary Differential Equations. I. Nonstiff Problems. Springer Series in Computational Mathematics 8. Springer, Berlin (1993). DOI 10.1007/978-3-540-78862-1 | MR 1227985 | Zbl 0789.65048
[31] Hapla, V., Horak, D., Pospisil, L., Cermak, M., Vasatova, A., Sojka, R.: Solving contact mechanics problems with PERMON. High Performance Computing in Science and Engineering Lecture Notes in Computer Science 9611. Springer, Cham (2015), 101-115. DOI 10.1007/978-3-319-40361-8_7 | Zbl 1382.74004
[32] Kohl, N., Bauer, D., Böhm, F., Rüde, U.: Fundamental data structures for matrix-free finite elements on hybrid tetrahedral grids. Int. J. Parallel Emergent Distrib. Syst. 39 (2024), 51-74. DOI 10.1080/17445760.2023.2266875
[33] Kohl, N., Rüde, U.: Textbook efficiency: Massively parallel matrix-free multigrid for the Stokes system. SIAM J. Sci. Comput. 44 (2022), C124--C155. DOI 10.1137/20M1376005 | MR 4404469 | Zbl 1492.65080
[34] Kohl, N., Thönnes, D., Drzisga, D., Bartuschat, D., Rüde, U.: The $HyTeG$ finite-element software framework for scalable multigrid solvers. Int. J. Parallel Emergent Distrib. Syst. 34 (2019), 477-496. DOI 10.1080/17445760.2018.1506453
[35] Kronbichler, M., Kormann, K.: A generic interface for parallel cell-based finite element operator application. Comput. Fluids 63 (2012), 135-147. DOI 10.1016/j.compfluid.2012.04.012 | MR 2982707 | Zbl 1365.76121
[36] Kühn, M. J., Kruse, C., Rüde, U.: Energy-minimizing, symmetric discretizations for anisotropic meshes and energy functional extrapolation. SIAM J. Sci. Comput. 43 (2021), A2448--A2473. DOI 10.1137/21M1397520 | MR 4284417 | Zbl 1486.65225
[37] Kühn, M. J., Kruse, C., Rüde, U.: Implicitly extrapolated geometric multigrid on disk-like domains for the gyrokinetic Poisson equation from fusion plasma applications. J. Sci. Comput. 91 (2022), Article ID 28, 27 pages. DOI 10.1007/s10915-022-01802-1 | MR 4393121 | Zbl 1490.65305
[38] Leleux, P., Schwarz, C., Kühn, M. J., Kruse, C., Rüde, U.: Complexity analysis and scalability of a matrix-free extrapolated geometric multigrid solver for curvilinear coordinates representations from fusion plasma applications. J. Parallel Distrib. Comput. 205 (2025), Article ID 105143, 31 pages. DOI 10.1016/j.jpdc.2025.105143
[39] Luce, R., Wohlmuth, B. I.: A local a posteriori error estimator based on equilibrated fluxes. SIAM J. Numer. Anal. 42 (2004), 1394-1414. DOI 10.1137/S0036142903433790 | MR 2114283 | Zbl 1078.65097
[40] Mayr, M., Berger-Vergiat, L., Ohm, P., Tuminaro, R. S.: Noninvasive multigrid for semistructured grids. SIAM J. Sci. Comput. 44 (2022), A2734--A2764. DOI 10.1137/20M1375413 | MR 4474385 | Zbl 1507.65278
[41] McCormick, S. F., Thomas, J.: The fast adaptive composite grid (FAC) method for elliptic equations. Math. Comput. 46 (1986), 439-456. DOI 10.1090/S0025-5718-1986-0829618-X | MR 0829618 | Zbl 0594.65078
[42] McCorquodale, P., Colella, P., Grote, D. P., Vay, J.-L.: A node-centered local refinement algorithm for Poisson's equation in complex geometries. J. Comput. Phys. 201 (2004), 34-60. DOI 10.1016/j.jcp.2004.04.022 | MR 2098852 | Zbl 1059.65094
[43] Munch, P., Heister, T., Saavedra, L. Prieto, Kronbichler, M.: Efficient distributed matrix-free multigrid methods on locally refined meshes for FEM computations. ACM Trans. Parallel Comput. 10 (2023), Article ID 3, 38 pages. DOI 10.1145/3580314 | MR 4573597
[44] Papež, J., Rüde, U., Vohralík, M., Wohlmuth, B.: Sharp algebraic and total a posteriori error bounds for $h$ and $p$ finite elements via a multilevel approach: Recovering mass balance in any situation. Comput. Methods Appl. Mech. Eng. 371 (2020), Article ID 113243, 39 pages. DOI 10.1016/j.cma.2020.113243 | MR 4142137 | Zbl 1506.76097
[45] Richter, T. M.: Goal-oriented error estimation for fluid-structure interaction problems. Comput. Methods Appl. Mech. Eng. 223-224 (2012), 28-42. DOI 10.1016/j.cma.2012.02.014 | MR 2917479 | Zbl 1253.74037
[46] Stals, L.: Adaptive multigrid in parallel. Proceedings 1st International Conference on Algorithms and Architectures for Parallel Processing. Volume 2 IEEE, Piscataway (1995), 792-795. DOI 10.1109/ICAPP.1995.472269
[47] Stals, L.: Parallel Multigrid On Unstructured Grids Using Adaptive Finite Element Methods: Ph.D. Thesis. Australian National University, Camberra (1995). DOI 10.25911/5d6e4e221442f
[48] Strang, G., Fix, G. J.: An Analysis of the Finite Element Methods. Wellesley-Cambridge Press, Wellesley (2008). MR 2743037 | Zbl 1171.65081
[49] Trottenberg, U., Oosterlee, C. W., Schüller, A.: Multigrid. Academic Press, New York (2000). MR 1807961 | Zbl 0976.65106
[50] Tufo, H. M., Fischer, P. F.: Fast parallel direct solvers for coarse grid problems. J. Parallel Distrib. Comput. 61 (2001), 151-177. DOI 10.1006/jpdc.2000.1676 | Zbl 0972.68191
[51] Vacek, P., Carson, E., Soodhalter, K. M.: The effect of approximate coarsest-level solves on the convergence of multigrid V-cycle methods. SIAM J. Sci. Comput. 46 (2024), A2634--A2659. DOI 10.1137/23M1578255 | MR 4784859 | Zbl 1545.65148
[52] Verfürth, R.: A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques. Wiley-Teubner Series Advances in Numerical Mathematics. John Wiley & Sons, Chichester (1996). Zbl 0853.65108
[53] Zenger, C., Gietl, H.: Improved difference schemes for the Dirichlet problem of Poisson's equation in the neighbourhood of corners. Numer. Math. 30 (1978), 315-332. DOI 10.1007/BF01411846 | MR 0502024 | Zbl 0425.65054
[54] al., W. Zhang et: AMReX: A framework for block-structured adaptive mesh refinement. J. Open Source Soft. 4 (2019), Article ID 1370. DOI 10.21105/joss.01370
[55] Zienkiewicz, O. C., Zhu, J. Z.: A simple error estimator and adaptive procedure for practical engineering analysis. Int. J. Numer. Methods Eng. 24 (1987), 337-357. DOI 10.1002/nme.1620240206 | MR 0875306 | Zbl 0602.73063
Search
Partner of
