Exponentially Convergent Multiscale Finite Element Method

Abstract

We provide a concise review of the exponentially convergent multiscale finite element method (ExpMsFEM) for efficient model reduction of PDEs in heterogeneous media without scale separation and in high-frequency wave propagation. The ExpMsFEM is built on the non-overlapped domain decomposition in the classical MsFEM while enriching the approximation space systematically to achieve a nearly exponential convergence rate regarding the number of basis functions. Unlike most generalizations of the MsFEM in the literature, the ExpMsFEM does not rely on any partition of unity functions. In general, it is necessary to use function representations dependent on the right-hand side to break the algebraic Kolmogorov n-width barrier to achieve exponential convergence. Indeed, there are online and offline parts in the function representation provided by the ExpMsFEM. The online part depends on the right-hand side locally and can be computed in parallel efficiently. The offline part contains basis functions that are used in the Galerkin method to assemble the stiffness matrix; they are all independent of the right-hand side, so the stiffness matrix can be used repeatedly in multi-query scenarios.

Keywords

Multiscale method / Exponential convergence / Helmholtz's equation / Domain decomposition / Nonlinear model reduction

References

[1.] Abdulle A, E WN, Engquist B, Vanden-Eijnden E. The heterogeneous multiscale method. Acta Numer., 2012, 21: 1-87

[2.] Babuška I, Lipton R. Optimal local approximation spaces for generalized finite element methods with application to multiscale problems. Multiscale Model. Simul., 2011, 9(1): 373-406

[3.] Babuška I, Lipton R, Sinz P, Stuebner M. Multiscale-spectral GFEM and optimal oversampling. Comput. Methods Appl. Mech. Eng., 2020, 364

[4.] Babuška I, Osborn JE. Can a finite element method perform arbitrarily badly?. Math. Comput., 2000, 69(230): 443-462

[5.] Babuška I, Osborn JE. Generalized finite element methods: their performance and their relation to mixed methods. SIAM J. Numer. Anal., 1983, 20(3): 510-536

[6.] Babuška I, Sauter S. Is the pollution effect of the FEM avoidable for the Helmholtz equation considering high wave numbers?. SIAM J. Numer. Anal., 1997, 34(6): 2392-2423

[7.] Brenner SC, Scott LR. . The Mathematical Theory of Finite Element Methods, 2008 Berlin Springer

[8.] Buhr A, Smetana K. Randomized local model order reduction. SIAM J. Sci. Comput., 2018, 40(4): A2120-A2151

[9.] Chen K, Li Q, Lu J, Wright SJ. Randomized sampling for basis function construction in generalized finite element methods. Multiscale Model. Simul., 2020, 18(2): 1153-1177

[10.] Chen Y, Hou TY. Multiscale elliptic PDE upscaling and function approximation via subsampled data. Multiscale Model. Simul., 2022, 20(1): 188-219

[11.] Chen Y, Hou TY, Wang Y. Exponential convergence for multiscale linear elliptic PDEs via adaptive edge basis functions. Multiscale Model. Simul., 2021, 19(2): 980-1010

[12.] Chen, Y., Hou, T.Y., Wang, Y.: Exponentially convergent multiscale methods for high frequency heterogeneous Helmholtz equations. arXiv:2105.04080 (2021)

[13.] Chung ET, Efendiev Y, Leung WT. Constraint energy minimizing generalized multiscale finite element method. Comput. Methods Appl. Mech. Eng., 2018, 339: 298-319

[14.] Efendiev YR, Hou TY, Wu X-H. Convergence of a nonconforming multiscale finite element method. SIAM J. Numer. Anal., 2000, 37(3): 888-910

[15.] Engquist B, Zhao H. Approximate separability of the Green’s function of the Helmholtz equation in the high frequency limit. Commun. Pure Appl. Math., 2018, 71(11): 2220-2274

[16.] Fu S, Chung E, Li G. Edge multiscale methods for elliptic problems with heterogeneous coefficients. J. Comput. Phys., 2019, 396: 228-242

[17.] Hauck S, Peterseim E. Super-localization of elliptic multiscale problems. Math. Comput., 2023, 92: 981-1003

[18.] Henning P, Peterseim D. Oversampling for the multiscale finite element method. Multiscale Model. Simul., 2013, 11(4): 1149-1175

[19.] Hetmaniuk U, Klawonn A. Error estimates for a two-dimensional special finite element method based on component mode synthesis. Electron. Trans. Numer. Anal., 2014, 41: 109-132

[20.] Hetmaniuk U, Lehoucq R. A special finite element method based on component mode synthesis. ESAIM: Math. Model. Numer. Anal., 2010, 44(3): 401-420

[21.] Hou TY, Liu P. Optimal local multi-scale basis functions for linear elliptic equations with rough coefficient. Discret. Contin. Dyn. Syst., 2016, 36(8): 4451-4476

[22.] Hou TY, Wu X-H. A multiscale finite element method for elliptic problems in composite materials and porous media. J. Comput. Phys., 1997, 134(1): 169-189

[23.] Hou TY, Wu X-H, Cai Z. Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficients. Math. Comput., 1999, 68(227): 913-943

[24.] Hou TY, Zhang X-H. Sparse operator compression of higher-order elliptic operators with rough coefficients. Res. Math. Sci., 2017, 4(1): 1-49

[25.] Hughes TJR, Feijóo GR, Mazzei L, Quincy J-B. The variational multiscale method—a paradigm for computational mechanics. Comput. Methods Appl. Mech. Eng., 1998, 166(1): 3-24

[26.] Kornhuber R, Peterseim D, Yserentant H. An analysis of a class of variational multiscale methods based on subspace decomposition. Math. Comput., 2018, 87(314): 2765-2774

[27.] Lafontaine D, Spence EA, Wunsch J. For most frequencies, strong trapping has a weak effect in frequency-domain scattering. Math. Comput., 2021, 74(10): 2025-2063

[28.] Li G. On the convergence rates of GMsFEMs for heterogeneous elliptic problems without oversampling techniques. Multiscale Model. Simul., 2019, 17(2): 593-619

[29.] Ma, C., Alber, C., Scheichl, R.: Wavenumber explicit convergence of a multiscale GFEM for heterogeneous Helmholtz problems. arXiv:2112.10544 (2021)

[30.] Ma C, Scheichl R. Error estimates for fully discrete generalized FEMs with locally optimal spectral approximations. Math. Comput., 2022, 91: 2539-2569

[31.] Ma, C., Scheichl, R., Dodwell, T.: Novel design and analysis of generalized FE methods based on locally optimal spectral approximations. arXiv:2103.09545 (2021)

[32.] Maier R. A high-order approach to elliptic multiscale problems with general unstructured coefficients. SIAM J. Numer. Anal., 2021, 59(2): 1067-1089

[33.] Målqvist A, Peterseim D. Localization of elliptic multiscale problems. Math. Comput., 2014, 83(290): 2583-2603

[34.] Melenk JM. On n-widths for elliptic problems. J. Math. Anal. Appl., 2000, 247(1): 272-289

[35.] Melenk JM, Sauter S. Convergence analysis for finite element discretizations of the Helmholtz equation with Dirichlet-to-Neumann boundary conditions. Math. Comput., 2010, 79(272): 1871-1914

[36.] Owhadi H. Bayesian numerical homogenization. Multiscale Model. Simul., 2015, 13(3): 812-828

[37.] Owhadi H. Multigrid with rough coefficients and multiresolution operator decomposition from hierarchical information games. SIAM Rev., 2017, 59(1): 99-149

[38.] Owhadi H, Scovel C. . Operator-Adapted Wavelets, Fast Solvers, and Numerical Homogenization: From a Game Theoretic Approach to Numerical Approximation and Algorithm Design, 2019 Cambridge Cambridge University Press

[39.] Owhadi H, Zhang L. Metric-based upscaling. Commun. Pure Appl. Math., 2007, 60(5): 675-723

[40.] Owhadi H, Zhang L. Localized bases for finite-dimensional homogenization approximations with nonseparated scales and high contrast. Multiscale Model. Simul., 2011, 9(4): 1373-1398

[41.] Owhadi H, Zhang L, Berlyand L. Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization. ESAIM: Math. Model. Numer. Anal., 2014, 48(2): 517-552

[42.] Peherstorfer B. Breaking the Kolmogorov barrier with nonlinear model reduction. Not. Am. Math. Soc., 2022, 69(5): 725-733

[43.] Pinkus A. . N-Widths in Approximation Theory, 2012 Berlin Springer Science & Business Media

[44.] Schleuß J, Smetana K. Optimal local approximation spaces for parabolic problems. Multiscale Model. Simul., 2022, 20(1): 551-582

[45.] Smetana K, Patera AT. Optimal local approximation spaces for component-based static condensation procedures. SIAM J. Sci. Comput., 2016, 38(5): A3318-A3356

Funding

National Science Foundation(DMS 2205590)