A meshless geometric multigrid method based on a node-coarsening algorithm for the linear finite element discretization. (English) Zbl 1524.65922
Summary: A meshless geometric multigrid (GMG) method based on a node-coarsening algorithm is proposed in the context of finite element method (FEM) with unstructured grids consisting of linear elements. Unlike the existing GMG methods, the present method does not require the generation of a sequence of coarse grids so that all the problems related to coarse-grid generation can be eliminated. Instead, only the sets of nodes in coarse levels are constructed for multigrid computation from the finest grid by using the node-coarsening algorithm that can be employed for any kind of a 2D/3D unstructured grid as well as a hybrid grid on the finest level. The implementation of the present coarsening algorithm is simple in the sense that the boundary information of the finest grid is not required. A searching algorithm to calculate the area/volume-shape function of the finite element method is also proposed to derive an operator for linear interpolation of multigrid computation. We have successfully validated the proposed method for various 2D/3D benchmark problems by showing that the elapsed time of the present GMG method is linearly proportional to the number of unknowns of a linear system of equations. We have also confirmed that the proposed method is nearly as efficient as the grid-based MG method based on a sequence of coarse grids in terms of CPU time. Lastly, we have successfully validated the meshless GMG method by solving an elliptic equation formulated by the finite volume method on a complicated 3D geometry filled with a hybrid unstructured mesh.
MSC:
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
| 65F10 | Iterative numerical methods for linear systems |
| 65N50 | Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs |
| 35J05 | Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation |
Keywords:
meshless geometric multigrid method; node-coarsening algorithm; linear interpolation; finite element method; unstructured gridReferences:
| [1] | Stüben, K., Algebraic multigrid (AMG): experiences and comparisons, Appl. Math. Comput., 13, 3-4, 419-451 (1983) · Zbl 0533.65064 |
| [2] | Brandt, A., Algebraic multigrid theory: the symmetric case, Appl. Math. Comput., 19, 1-4, 23-56 (1986) · Zbl 0616.65037 |
| [3] | Stüben, K., A Review of Algebraic Multigrid: Numerical Analysis: Historical Developments in the 20th Century, 331-359 (2001), Elsevier · Zbl 0985.65002 |
| [4] | Chang, Q.; Wong, Y. S.; Fu, H., On the algebraic multigrid method, J. Comput. Phys., 125, 2, 279-292 (1996) · Zbl 0857.65037 |
| [5] | Woodward, C. S., A Newton-Krylov-multigrid solver for variably saturated flow problems, WIT Transactions on Ecology and the Environment, 24 (1970) |
| [6] | Gaspar, F. J.; Gracia, J. L.; Lisbona, F. J.; Rodrigo, C., On geometric multigrid methods for triangular grids using three-coarsening strategy, Appl. Numer. Math., 59, 7, 1693-1708 (2009) · Zbl 1171.65448 |
| [7] | Jimack, P. K., Applications of multigrid techniques in cfd, Int. J. Numer. Methods Fluids, 1-12 (2007) |
| [8] | Wesseling, P.; Oosterlee, C. W., Geometric multigrid with applications to computational fluid dynamics, J. Comput. Appl. Math., 128, 1-2, 311-334 (2001) · Zbl 0989.76069 |
| [9] | Zubair, H. B.; MacLachlan, S. P.; Oosterlee, C. W., A geometric multigrid method based on L-shaped coarsening for PDEs on stretched grids, Numer. Linear Algebra Appl., 17, 6, 871-894 (2010) · Zbl 1240.65365 |
| [10] | Chan, T. F.; Xu, J.; Zikatanov, L., An agglomeration multigrid method for unstructured grids, Contemp. Math., 218, 67-81 (1998) · Zbl 0909.65102 |
| [11] | Park, S. H.; Kwon, J. H., Implementation of k-ω turbulence models in an implicit multigrid method, AIAA J., 42, 7, 1348-1357 (2004) |
| [12] | Watanabe, K.; Igarashi, H.; Honma, T., Comparison of geometric and algebraic multigrid methods in edge-based finite-element analysis, IEEE Trans. Magn., 41, 5, 1672-1675 (2005) |
| [13] | Langer, U.; Pusch, D., Comparison of Geometrical and Algebraic Multigrid Preconditioners for Data-Sparse Boundary Element Matrices, International Conference on Large-Scale Scientific Computing (2005), Springer: Springer Berlin, Heidelberg · Zbl 1073.65135 |
| [14] | Chen, H.; Xie, H.; Xu, F., A full multigrid method for eigenvalue problems, J. Comput. Phys., 322, 747-759 (2016) · Zbl 1352.65459 |
| [15] | Perez, E., Finite element and multigrid solution of the two dimensional Euler equations on a non structured mesh (1985), PhD Diss. INRIA |
| [16] | Wu, J.; Zheng, H., Uniform convergence of multigrid methods for adaptive meshes, Appl. Numer. Math., 113, 109-123 (2017) · Zbl 1355.65143 |
| [17] | Kettil, P.; Ekevid, T.; Wiberg, N. E., Towards fully mesh adaptive FE-simulations in 3D using multi-grid solver, Comput. Struct., 81, 735-746 (2003) |
| [18] | Bastian, P.; Wieners, C., Multigrid methods on adaptively refined grids, Comput. Sci. Eng., 8, 6, 44-54 (2006) |
| [19] | Brown, J. D.; Lowe, L. L., Multigrid elliptic equation solver with adaptive mesh refinement, J. Comput. Phys., 209, 2, 582-598 (2005) · Zbl 1073.65141 |
| [20] | Kočvara, M., An adaptive multigrid technique for three-dimensional elasticity, Int. J. Numer. Methods Eng., 36, 10, 1703-1716 (1993) · Zbl 0775.73267 |
| [21] | Ollivier-Gooch, C. F., Multigrid acceleration of an upwind Euler solver on unstructured meshes, AIAA J., 33, 10, 1822-1827 (1995) · Zbl 0856.76064 |
| [22] | Brune, P. R.; Knepley, M. G.; Scott, L. R., Unstructured geometric multigrid in two and three dimensions on complex and graded meshes, SIAM J. Sci. Comput., 35, 1, A173-A191 (2013) · Zbl 1264.65203 |
| [23] | Guillard, H., Node-nested multi-grid method with Delaunay coarsening (1993), PhD Diss. INRIA |
| [24] | Cavendish, J. C., Automatic triangulation of arbitrary planar domains for the finite element method, Int. J. Numer. Methods Eng., 8, 4, 679-696 (1974) · Zbl 0284.73045 |
| [25] | Wu, C. T.; Howard, C. E., Analysis and comparison of geometric and algebraic multigrid for convection-diffusion equations, SIAM J. Sci. Comput., 28, 6, 2208-2228 (2006) · Zbl 1133.65102 |
| [26] | Oliveira, F.; Pinto, M. A.V.; Marchi, C. H.; Araki, L. K., Optimized partial semicoarsening multigrid algorithm for heat diffusion problems and anisotropic grids, Appl. Math. Model., 36, 10, 4665-4676 (2012) · Zbl 1252.65143 |
| [27] | Dai, R.; Lin, P.; Zhang, J., An EXCMG accelerated multiscale multigrid computation for 3D Poisson equation, Comput. Math. Appl., 77, 8, 2051-2060 (2019) · Zbl 1442.65322 |
| [28] | Arrarás, A.; Gaspar, F. J.; Portero, L.; Rodrigo, C., Geometric multigrid methods for Darcy-Forchheimer flow in fractured porous media, Comput. Math. Appl., 78, 9, 3139-3151 (2019) · Zbl 1443.76209 |
| [29] | Shin, S.; Chergui, J.; Juric, D., A solver for massively parallel direct numerical simulation of three-dimensional multiphase flows, J. Mech. Sci. Technol., 31, 4, 1739-1751 (2017) |
| [30] | de la Riva, A. P.; Gaspar, F. J.; Rodrigo, C., On the robust solution of an isogeometric discretization of bilaplacian equation by using multigrid methods, Comput. Math. Appl., 386-394 (2019) · Zbl 1446.65193 |
| [31] | Katz, A.; Jameson, A., Multicloud: multigrid convergence with a meshless operator, J. Comput. Phys., 228, 14, 5237-5250 (2009) · Zbl 1280.76040 |
| [32] | Mavriplis, D. J.; Venkatakrishnan, V., Agglomeration multigrid for viscous turbulent flows, (25^th AIAA Fluid Dynamics Conf. (1994)) · Zbl 0846.76047 |
| [33] | Marmignon, C.; Cantaloube, B.; Le Pape, M. C.; Plata, M.; Couaillier, V.; Gazaix, M., Development of an agglomeration multigrid technique in the hybrid solver ELSA-H, (7^th Int. Conf. on Comput. Fluid Dynamics (ICCFD7) (2012)) |
| [34] | Lallemand, M. H.; Steve, H.; Dervieux, A., Unstructured multigridding by volume agglomeration: current status, Comput. Fluids, 21, 3, 397-433 (1992) · Zbl 0753.76136 |
| [35] | Lambropoulos, N. K.; Koubogiannis, D. G.; Giannakoglou, K. C., Acceleration of a Navier-Stokes equation solver for unstructured grids using agglomeration multigrid and parallel processing, Comput. Methods Appl. Mech. Eng., 193, 9-11, 781-803 (2004) · Zbl 1106.76405 |
| [36] | Bittencourt, M. L.; Douglas, C. C.; Feijóo, R. A., Nonnested multigrid methods for linear problems, Numer. Methods Partial Differ. Equ., 17, 4, 313-331 (2001) · Zbl 0987.65131 |
| [37] | Ha, S. T.; Choi, H. G., Performance comparison of interpolation operators of multi-grid method based on a distance weighted and area (volume) intersection approaches. Part II: finite element discretization, J. Mech. Sci. Technol., 33, 7, 3323-3331 (2019) |
| [38] | Chemin, A.; Elguedj, T.; Gravouil, A., Isogeometric local h-refinement strategy based on multigrids, Finite Elem. Anal. Des., 100, 77-90 (2015) |
| [39] | Briggs, W. L.; Henson, V. E.; McCormick, S. F., A Multigrid Tutorial (2000), SIAM · Zbl 0958.65128 |
| [40] | Feng, Y. T.; Perić, D.; Owen, D. R.J., A non-nested Galerkin multi-grid method for solving linear and nonlinear solid mechanics problems, Comput. Methods Appl. Mech. Eng., 144, 3-4, 307-325 (1997) · Zbl 0892.73076 |
| [41] | Löhner, R.; Morgan, K., An unstructured multigrid method for elliptic problems, Int. J. Numer. Methods Eng., 24, 1, 101-115 (1987) · Zbl 0624.65103 |
| [42] | Duy, N. M.; Tran, T. C., An integrated-RBF technique based on Galerkin formulation for elliptic differential equations, Eng. Anal. Bound. Elem., 33, 2, 191-199 (2009) · Zbl 1244.65177 |
| [43] | Shiralashetti, S. C.; Kantli, M. H.; Deshi, A. B., A new wavelet multigrid method for the numerical solution of elliptic type differential equations, Alex. Eng. J., 57, 1, 203-209 (2018) |
| [44] | Mohamed, S. A., Adaptive FAS-multigrid method for nonlinear elliptic equations on unstructured grids, Commun. Numer. Methods Eng., 24, 12, 1979-2002 (2008) · Zbl 1155.65106 |
| [45] | Pan, K.; He, D.; Hu, H.; Ren, Z., A new extrapolation cascadic multigrid method for three dimensional elliptic boundary value problems, J. Comput. Phys., 344, 499-515 (2017) · Zbl 1380.65407 |
| [46] | Park, I. K.; Lee, J. R.; Choi, Y. H.; Kang, D. H., A multi-scale and multi-physics approach to main steam line break accidents using coupled MASTER/CUPID/MARS code, Ann. Nucl. Energy, 135, Article 106972 pp. (2020) |
| [47] | Van Der Vorst, H. A., Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 13, 631-644 (1992) · Zbl 0761.65023 |
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.
