We study an element agglomeration coarsening strategy that requires data redistribution at coarse levels when the number of coarse elements becomes smaller than the number of MPI processes used on the finest level. The overall procedure generates coarse elements (general unstructured unions of fine grid elements) within the framework of element-based algebraic multigrid methods (or AMGe) studied previously. The AMGe-generated coarse spaces have the ability to exhibit approximation properties of the same order as the fine-level spaces since by construction they contain the piecewise polynomials of the same order as on the fine level. These approximation properties are key for the successful use of AMGe in multilevel solvers for nonlinear partial differential equations as well as for multilevel Monte Carlo (MLMC) simulations. The ability to coarsen without being constrained by the number of MPI processes, as described in the present paper, allows to improve the scalability of these solvers as well as the overall MLMC method. The paper illustrates this latter fact with detailed scalability study of MLMC simulations applied to model Darcy equations with a stochastic log-normal permeability field.
ÅströmJACarterAHetheringtonJ, et al. (2013) Preparing scientific application software for exascale computing. In: ManninenPÖsterP (eds) Appl. Parallel Sci. Comput., Lecture Notes in Computer Science. Springer, Vol. 7782, 27–42.
2.
BadiaSHamptonJPrincipeJ (2023) A massively parallel implementation of multilevel Monte Carlo for finite element models. Mathematics and Computers in Simulation213: 18–39.
3.
BakhishoffUKhaneghahEMAlievAR, et al. (2020) DTHMM ExaLB: discrete-time hidden Markov model for load balancing in distributed exascale computing environment. Cogent Engineering7(1): 1743404.
4.
BalaySAbhyankarSAdamsMF, et al. (2025) PETSc/TAO Users Manual. Argonne National Laboratory. Technical Report ANL-21/39 - Revision 3.23.
5.
BarkerAGeleverSLeeC, et al. (2021) Multilevel spectral coarsening for graph Laplacian problems with application to reservoir simulation. SIAM Journal on Scientific Computing43(4): A2737–A2765.
6.
BarthASchwabCZollingerN (2011) Multi-level Monte Carlo finite element method for elliptic pdes with stochastic coefficients. Numerische Mathematik119(1): 123–161.
7.
BienzAGroppWDOlsonLN (2020) Reducing communication in algebraic multigrid with multi-step node aware communication. The International Journal of High Performance Computing Applications34(5): 547–561.
8.
ChristouMChristoudiasTMorilloJ, et al. (2016) Earth system modelling on system-level heterogeneous architectures: EMAC (version 2.42) on the Dynamical Exascale Entry Platform (DEEP). Geoscientific Model Development9(9): 3483–3491.
9.
CliffeKAGilesMBScheichlR, et al. (2011) Multilevel Monte Carlo methods and applications to elliptic PDEs with random coefficients. Computing and Visualization in Science14(1): 3–15.
10.
DodwellTKetelsenCScheichlR, et al. (2015) A hierarchical multilevel Markov chain Monte Carlo algorithm with applications to uncertainty quantification in subsurface flow. SIAM/ASA Journal on Uncertainty Quantification3(1): 1075–1108.
11.
DonahueASCaldwellPM (2020) Performance and accuracy implications of parallel split physics-dynamics coupling in the energy exascale Earth system atmosphere model. Journal of Advances in Modeling Earth Systems12(7): e2020MS002080.
12.
DongarraJBeckmanPMooreT, et al. (2011) The international exascale Software project roadmap. The International Journal of High Performance Computing Applications25(1): 3–60.
13.
DrzisgaDGmeinerBRüdeU, et al. (2017) Scheduling massively parallel multigrid for multilevel monte Carlo methods. SIAM Journal on Scientific Computing39(5): S873–S897.
FairbanksHROsbornSVassilevskiPS (2021a) Estimating posterior quantity of interest expectations in a multilevel scalable framework. Numerical Linear Algebra with Applications28(3): e2352.
16.
FairbanksHRVillaUVassilevskiPS (2021b) Multilevel hierarchical decomposition of finite element White noise with application to multilevel Markov chain Monte Carlo. SIAM Journal on Scientific Computing43: S293–S316DOI.
17.
GilesM (2008) Multilevel Monte Carlo path simulation. Operations Research56(3): 607–617.
18.
GilesM (2013) Multilevel Monte Carlo methods. In: Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer, 83–103.
19.
HeinrichS (2001) Multilevel Monte Carlo methods. In: Large-Scale Scientific Computing. Springer, 58–67.
20.
HerouxMABartlettRAHowleVE, et al. (2005) An overview of the trilinos project. ACM Transactions on Mathematical Software31(3): 397–423.
HirschmannSLahnertMSchoberC, et al. (2019) Load-Balancing and spatial adaptivity for coarse-grained molecular dynamics applications. In: NagelWEKrönerDHReschMM (eds) High Perform Comput Sci Eng ’18. Springer, 409–423.
23.
HuXVassilevskiPS (2019) Modifying AMG coarse spaces with weak approximation property to exhibit approximation in energy norm. SIAM Journal on Matrix Analysis and Applications40(3): 1131–1152.
24.
KalchevDZVassilevskiPSVillaU (2021) On ParELAG’s Parallel Element-based Algebraic Multigrid and its MFEM Miniapps for H(curl) and H(div) Problems: A Report Including Lowest and next to the Lowest Order Numerical Results. Technical report. Lawrence Livermore National Laboratory. LLNL-TR-824455.
25.
KalchevDZVassilevskiPSVillaU (2023) Parallel element-based algebraic multigrid for H(curl) and H(div) problems using the ParELAG library. SIAM Journal on Scientific Computing45(3): S371–S400.
26.
KarypisGKumarV (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing20(1): 359–392.
27.
KůsPŠístekJ (2017) Coupling parallel adaptive mesh refinement with a nonoverlapping domain decomposition solver. Advances in Engineering Software110: 34–54.
28.
LashukIVassilevskiP (2014) The construction of coarse de Rham complexes with improved approximation properties. Computational Methods in Applied Mathematics14(2): 257–303.
29.
LeeCSVassilevskiPS (2017) Parallel solver for H(div) problems using hybridization and amg. In: Domain Decomposition Methods in Science and Engineering XXIII. Springer, 69–80.
30.
LeeCHamonFCastellettoN, et al. (2022) An aggregation-based nonlinear multigrid solver for two-phase flow and transport in porous media. Computers & Mathematics with Applications113: 282–299.
31.
LindgrenFRueHLindströmJ (2011) An explicit link between Gaussian fields and Gaussian Markov random fields: the stochastic partial differential equation approach. Journal of the Royal Statistical Society: Series B73(4): 423–498.
32.
MayDASananPRuppK, et al. (2016) Extreme-scale multigrid components within PETSc. In: Proceedings of the Platform for Advanced Scientific Computing Conference, PASC’16. Association for Computing Machinery.
33.
MFEM:modular finite element methods library. Available at: https://mfem.org.
OsbornSVassilevskiPVillaU (2017) A multilevel, hierarchical sampling technique for spatially correlated random fields. SIAM Journal on Scientific Computing39(5): S543–S562.
36.
OsbornSZulianPBensonT, et al. (2018) Scalable hierarchical PDE sampler for generating spatially correlated random fields using nonmatching meshes. Numerical Linear Algebra with Applications25(3): e2146.
37.
ÖzturanCDeCougnyHLShephardMS, et al. (1994) Parallel adaptive mesh refinement and redistribution on distributed memory computers. Computer Methods in Applied Mechanics and Engineering119(1): 123–137.
ReisnerAOlsonLNMoultonJD (2018) Scaling structured multigrid to 500K+ cores through coarse-grid redistribution. SIAM Journal on Scientific Computing40(4): C581–C604.
41.
ReiterSVogelAHeppnerI, et al. (2013) A massively parallel geometric multigrid solver on hierarchically distributed grids. Computing and Visualization in Science16(4): 151–164.
42.
RudiJMalossiACIIsaacT, et al. (2015) An extreme-scale implicit solver for complex PDEs: highly heterogeneous flow in Earth’s mantle. In: Proceedings International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’15. Association for Computing Machinery10.1145/2807591.2807675.
43.
ShegunovNIlievO (2020) On dynamic parallelization of multilevel monte carlo algorithm. Cybernetics and Information Technologies20(6): 116–125.
44.
StaffordEPérezBBosqueJL, et al. (2017) To distribute or not to distribute: the question of load balancing for performance or energy. In: RiveraFFPenaTFCabaleiroJC (eds) Euro-Par 2017: Parallel Processing, Lecture Notes in Computer Science. Springer, Vol. 10417, 710–722.
45.
VassilevskiPS (2002) Sparse matrix element topology with application to AMG(e) and preconditioning. Numerical Linear Algebra with Applications9(6-7): 429–444.
46.
VassilevskiPS (2008) Multilevel Block Factorization Preconditioners: Matrix-Based Analysis and Algorithms for Solving Finite Element Equations. Springer.
47.
WangKKulkarniALangM, et al. (2016) Exploring the design tradeoffs for extreme-scale high-performance computing System software. IEEE Transactions on Parallel and Distributed Systems27(4): 1070–1084.
