Article
| Title: | An adaptive mesh refinement scheme for hierarchical hybrid grids (English) |
| Author: | Mann, Benjamin |
| Author: | Rüde, Ulrich |
| Language: | English |
| Journal: | Applications of Mathematics |
| ISSN: | 0862-7940 (print) |
| ISSN: | 1572-9109 (online) |
| Volume: | 70 |
| Issue: | 6 |
| Year: | 2025 |
| Pages: | 875-905 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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. (English) |
| Keyword: | adaptive mesh refinement |
| Keyword: | error estimation |
| Keyword: | finite elements |
| Keyword: | geometric multigrid |
| MSC: | 65N50 |
| MSC: | 65N55 |
| MSC: | 65Y05 |
| DOI: | 10.21136/AM.2025.0186-25 |
| . | |
| Date available: | 2025-12-20T06:23:14Z |
| Last updated: | 2025-12-22 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/153227 |
| . | |
| Reference: | [1] Ainsworth, M., Oden, J. T.: A posteriori error estimation in finite element analysis.Comput. Methods Appl. Mech. Eng. 142 (1997), 1-88. Zbl 0895.76040, MR 1442375, 10.1016/S0045-7825(96)01107-3 |
| Reference: | [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. Zbl 0838.65109, MR 1365264, 10.1002/(SICI)1099-1476(19960110)19:1<63::AID-MMA764>3.0.CO;2-S |
| Reference: | [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. Zbl 1419.65101, MR 3809435, 10.1016/j.camwa.2018.04.011 |
| Reference: | [4] Axelsson, O., Blaheta, R.: Two simple derivations of universal bounds for the CBS inequality constant.Appl. Math., Praha 49 (2004), 57-72. Zbl 1099.65103, MR 2032148, 10.1023/B:APOM.0000024520.06175.8b |
| Reference: | [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. Zbl 0396.65068, 10.1002/nme.1620121010 |
| Reference: | [6] Babuška, I., Rosenzweig, M. B.: A finite element scheme for domains with corners.Numer. Math. 20 (1972), 1-21. Zbl 0252.65084, MR 0323129, 10.1007/BF01436639 |
| Reference: | [7] Babuška, I., Strouboulis, T.: The Finite Element Methods and Its Reliability.Oxford University Press, Oxford (2001). Zbl 0995.65501, MR 1857191, 10.1093/oso/9780198502760.001.0001 |
| Reference: | [8] Bai, D., Brandt, A.: Local mesh refinement multilevel techniques.SIAM J. Sci. Stat. Comput. 8 (1987), 109-134. Zbl 0619.65091, MR 0879406, 10.1137/0908025 |
| Reference: | [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). Zbl 0990.65500, MR 1621384, 10.1137/1.9780898719635 |
| Reference: | [10] Bank, R. E., Weiser, A.: Some a posteriori error estimators for elliptic partial differential equations.Math. Comput. 44 (1985), 283-301. Zbl 0569.65079, MR 0777265, 10.2307/2007953 |
| Reference: | [11] Becker, R., Rannacher, R.: An optimal control approach to a posteriori error estimation in finite element methods.Acta Numerica 10 (2001), 1-102. Zbl 1105.65349, MR 2009692, 10.1017/S0962492901000010 |
| Reference: | [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. Zbl 1164.65517, MR 2065817, 10.1002/nla.382 |
| Reference: | [13] Bernert, K.: $\tau$-extrapolation -- Theoretical foundation, numerical experiment, and application to Navier-Stokes equations.SIAM J. Sci. Comput. 18 (1997), 460-478. Zbl 0952.35095, MR 1433789, 10.1137/S1064827594276266 |
| Reference: | [14] Bey, J.: Tetrahedral grid refinement.Computing 4 (1995), 355-378. Zbl 0839.65135, MR 1370107, 10.1007/BF02238487 |
| Reference: | [15] Blaheta, R.: Nested tetrahedral grids and strengthened C.B.S. inequality.Numer. Linear Algebra Appl. 10 (2003), 619-637. Zbl 1071.65164, MR 2030627, 10.1002/nla.340 |
| Reference: | [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. |
| Reference: | [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. Zbl 1563.65225, MR 4856616, 10.1137/24M1653756 |
| Reference: | [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. Zbl 0407.68037, MR 0474858, 10.1016/B978-0-12-587260-7.50015-7 |
| Reference: | [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. Zbl 1538.65583, MR 4372443, 10.1002/nla.2407 |
| Reference: | [20] Ciarlet, P. G.: The Finite Element Method for Elliptic Problems.Classics in Applied Mathematics. SIAM, Philadelphia (2002). Zbl 0999.65129, MR 1930132, 10.1137/1.9780898719208 |
| Reference: | [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. Zbl 1502.65198, MR 4480269, 10.1007/s11075-022-01281-3 |
| Reference: | [22] Egger, H., Rüde, U., Wohlmuth, B.: Energy-corrected finite element methods for corner singularities.SIAM J. Numer. Anal. 52 (2014), 171-193. Zbl 1293.65150, MR 3154149, 10.1137/120871377 |
| Reference: | [23] Elman, H. C.: Multigrid and Krylov subspace methods for the discrete Stokes equations.Int. J. Numer. Methods Fluids 22 (1996), 755-770. Zbl 0865.76078, 10.1002/(SICI)1097-0363(19960430)22:8<755::AID-FLD377>3.0.CO;2-1 |
| Reference: | [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. Zbl 1198.65213, MR 2672266, 10.1007/s00211-010-0292-9 |
| Reference: | [25] Fung, F., Stals, L., Deng, Q.: Fault-tolerant parallel multigrid method on unstructured adaptive mesh.SIAM J. Sci. Comput. 46 (2024), S145--S169. Zbl 07931243, MR 4813195, 10.1137/23M1582904 |
| Reference: | [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. MR 3580776, 10.1016/j.jocs.2016.06.006 |
| Reference: | [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. 10.1002/cpe.2968 |
| Reference: | [28] Gradl, T.: Data Structures and Algorithms for the Optimization of Hierarchical Hybrid Multigrid Methods: Ph.D. Thesis.Friedrich-Alexander-Universität, Erlangen (2015). |
| Reference: | [29] Grisvard, P.: Elliptic Problems in Nonsmooth Domains.Classics in Applied Mathematics 69. SIAM, Philadelphia (2011). Zbl 1231.35002, MR 3396210, 10.1137/1.9781611972030 |
| Reference: | [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). Zbl 0789.65048, MR 1227985, 10.1007/978-3-540-78862-1 |
| Reference: | [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. Zbl 1382.74004, 10.1007/978-3-319-40361-8_7 |
| Reference: | [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. 10.1080/17445760.2023.2266875 |
| Reference: | [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. Zbl 1492.65080, MR 4404469, 10.1137/20M1376005 |
| Reference: | [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. 10.1080/17445760.2018.1506453 |
| Reference: | [35] Kronbichler, M., Kormann, K.: A generic interface for parallel cell-based finite element operator application.Comput. Fluids 63 (2012), 135-147. Zbl 1365.76121, MR 2982707, 10.1016/j.compfluid.2012.04.012 |
| Reference: | [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. Zbl 1486.65225, MR 4284417, 10.1137/21M1397520 |
| Reference: | [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. Zbl 1490.65305, MR 4393121, 10.1007/s10915-022-01802-1 |
| Reference: | [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. 10.1016/j.jpdc.2025.105143 |
| Reference: | [39] Luce, R., Wohlmuth, B. I.: A local a posteriori error estimator based on equilibrated fluxes.SIAM J. Numer. Anal. 42 (2004), 1394-1414. Zbl 1078.65097, MR 2114283, 10.1137/S0036142903433790 |
| Reference: | [40] Mayr, M., Berger-Vergiat, L., Ohm, P., Tuminaro, R. S.: Noninvasive multigrid for semistructured grids.SIAM J. Sci. Comput. 44 (2022), A2734--A2764. Zbl 1507.65278, MR 4474385, 10.1137/20M1375413 |
| Reference: | [41] McCormick, S. F., Thomas, J.: The fast adaptive composite grid (FAC) method for elliptic equations.Math. Comput. 46 (1986), 439-456. Zbl 0594.65078, MR 0829618, 10.1090/S0025-5718-1986-0829618-X |
| Reference: | [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. Zbl 1059.65094, MR 2098852, 10.1016/j.jcp.2004.04.022 |
| Reference: | [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. MR 4573597, 10.1145/3580314 |
| Reference: | [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. Zbl 1506.76097, MR 4142137, 10.1016/j.cma.2020.113243 |
| Reference: | [45] Richter, T. M.: Goal-oriented error estimation for fluid-structure interaction problems.Comput. Methods Appl. Mech. Eng. 223-224 (2012), 28-42. Zbl 1253.74037, MR 2917479, 10.1016/j.cma.2012.02.014 |
| Reference: | [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. 10.1109/ICAPP.1995.472269 |
| Reference: | [47] Stals, L.: Parallel Multigrid On Unstructured Grids Using Adaptive Finite Element Methods: Ph.D. Thesis.Australian National University, Camberra (1995). 10.25911/5d6e4e221442f |
| Reference: | [48] Strang, G., Fix, G. J.: An Analysis of the Finite Element Methods.Wellesley-Cambridge Press, Wellesley (2008). Zbl 1171.65081, MR 2743037 |
| Reference: | [49] Trottenberg, U., Oosterlee, C. W., Schüller, A.: Multigrid.Academic Press, New York (2000). Zbl 0976.65106, MR 1807961 |
| Reference: | [50] Tufo, H. M., Fischer, P. F.: Fast parallel direct solvers for coarse grid problems.J. Parallel Distrib. Comput. 61 (2001), 151-177. Zbl 0972.68191, 10.1006/jpdc.2000.1676 |
| Reference: | [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. Zbl 1545.65148, MR 4784859, 10.1137/23M1578255 |
| Reference: | [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 |
| Reference: | [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. Zbl 0425.65054, MR 0502024, 10.1007/BF01411846 |
| Reference: | [54] al., W. Zhang et: AMReX: A framework for block-structured adaptive mesh refinement.J. Open Source Soft. 4 (2019), Article ID 1370. 10.21105/joss.01370 |
| Reference: | [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. Zbl 0602.73063, MR 0875306, 10.1002/nme.1620240206 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
