We introduce a new variational method for the numerical homogenization of divergence form elliptic, parabolic and hyperbolic equations with arbitrary rough (L∞) coefficients. Our method does not rely on concepts of ergodicity or scale-separation but on compactness properties of the solution space and a new variational approach to homogenization. The approximation space is generated by an interpolation basis (over scattered points forming a mesh of resolution H) minimizing the L2 norm of the source terms; its (pre-)computation involves minimizing 𝒪(H-d) quadratic (cell) problems on (super-)localized sub-domains of size 𝒪(H ln(1/H)). The resulting localized linear systems remain sparse and banded. The resulting interpolation basis functions are biharmonic for d ≤ 3, and polyharmonic for d ≥ 4, for the operator -div(a∇·) and can be seen as a generalization of polyharmonic splines to differential operators with arbitrary rough coefficients. The accuracy of the method (𝒪(H) in energy norm and independent from aspect ratios of the mesh formed by the scattered points) is established via the introduction of a new class of higher-order Poincaré inequalities. The method bypasses (pre-)computations on the full domain and naturally generalizes to time dependent problems, it also provides a natural solution to the inverse problem of recovering the solution of a divergence form elliptic equation from a finite number of point measurements.
@article{M2AN_2014__48_2_517_0,
author = {Owhadi, Houman and Zhang, Lei and Berlyand, Leonid},
title = {Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
volume = {48},
year = {2014},
pages = {517-552},
doi = {10.1051/m2an/2013118},
mrnumber = {3177856},
zbl = {1296.41007},
language = {en},
url = {http://dml.mathdoc.fr/item/M2AN_2014__48_2_517_0}
}
Owhadi, Houman; Zhang, Lei; Berlyand, Leonid. Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 48 (2014) pp. 517-552. doi : 10.1051/m2an/2013118. http://gdmltest.u-ga.fr/item/M2AN_2014__48_2_517_0/
[1] and , Finite element heterogeneous multiscale method for the wave equation. Multiscale Model. Simul. 9 (2011) 766-792. | MR 2818419 | Zbl 1298.65145
[2] and , Heterogeneous multiscale FEM for diffusion problems on rough surfaces. Multiscale Model. Simul. 3 (2004) 195-220. | MR 2123116 | Zbl 1160.65337
[3] and , A multiscale finite element method for numerical homogenization. Multiscale Model. Simul. 4 (2005) 790-812. | MR 2203941 | Zbl 1093.35007
[4] and . Subgrid upscaling and mixed multiscale finite elements. SIAM J. Numer. Anal. 44 (2006) 1150-1171. | MR 2231859 | Zbl 1120.65122
[5] , and , Improved accuracy for alternating-direction methods for parabolic equations based on regular and mixed finite elements. Math. Models Methods Appl. Sci. 17 (2007) 1279-1305. | MR 2342991 | Zbl 1146.65068
[6] and , Stochastic homogenization of Hamilton-Jacobi and degenerate Bellman equations in unbounded environments. J. Math. Pures Appl. 97 (2012) 460-504. | MR 2914944 | Zbl 1246.35029
[7] , Fonctions spline et noyaux reproduisants d'Aronszajn-Bergman. Rev. Française Informat. Recherche Opérationnelle 4 (1970) 31-43. | Numdam | MR 300061 | Zbl 0213.12502
[8] , and , Special finite element methods for a class of second order elliptic problems with rough coefficients. SIAM J. Numer. Anal. 31 (1994) 945-981. | MR 1286212 | Zbl 0807.65114
[9] and , Optimal local approximation spaces for generalized finite element methods with application to multiscale problems. Multiscale Model. Simul. 9 (2011) 373-406. | MR 2801210 | Zbl 1229.65195
[10] and , Generalized finite element methods: their performance and their relation to mixed methods. SIAM J. Numer. Anal. 20 (1983) 510-536. | MR 701094 | Zbl 0528.65046
[11] and , Can a finite element method perform arbitrarily badly? Math. Comput. 69 (2000) 443-462. | MR 1648351 | Zbl 0940.65086
[12] and , Corrector theory for MSFEM and HMM in random media. Multiscale Model. Simul. 9 (2011) 1549-1587. | MR 2861250 | Zbl 1244.65004
[13] and , Multiscale homogenization with bounded ratios and anomalous slow diffusion. Comm. Pure Appl. Math. 56 (2003) 80-113. | MR 1929443 | Zbl 1205.76223
[14] , and , Asymptotic analysis for periodic structure. North Holland, Amsterdam (1978). | MR 503330 | Zbl 0404.35001
[15] and , Flux norm approach to finite dimensional homogenization approximations with non-separated scales and high contrast. Arch. Rational Mech. Anal. 198 (2010) 677-721. | MR 2721592 | Zbl 1229.35009
[16] , and , Une variante de la théorie de l'homogénéisation stochastique des opérateurs elliptiques. C. R. Math. Acad. Sci. Paris 343 (2006) 717-724. | MR 2284699 | Zbl 1103.35014
[17] , and , Stochastic homogenization and random lattices. J. Math. Pures Appl. 88 (2007) 34-63. | MR 2334772 | Zbl 1129.60055
[18] and , Estimates in probability of the residual between the random and the homogenized solutions of one-dimensional second-order operator. Asymptot. Anal. 21 (1999) 303-315. | MR 1728027 | Zbl 0960.60057
[19] , , L.L. and X.-H. Wu, Challenges and technologies in reservoir modeling. Commun. Comput. Phys. (2009) 6 1-23. | MR 2537305
[20] , Error estimates for interpolation of rough and smooth functions using radial basis functions. Ph.D. thesis. University of Leicester (2004).
[21] and , A rate of convergence for monotone finite difference approximations to fully nonlinear, uniformly elliptic PDEs. Comm. Pure Appl. Math. 61 (2008) 1-17. | MR 2361302 | Zbl 1140.65075
[22] , and , A new multiscale finite element method for high-contrast elliptic interface problems. Math. Comput. 79 (2010) 1915-1955. | MR 2684351 | Zbl 1202.65154
[23] , and . Modeling across scales: Discrete geometric structures in homogenization and inverse homogenization. Reviews of Nonlinear Dynamics and Complexity. Special issue on Multiscale Analysis and Nonlinear Dynamics (2012). | MR 3221686
[24] , Interpolation des fonctions de deux variables suivant le principe de la flexion des plaques minces. Rev. Francaise Automat. Informat. Recherche Operationnelle Ser. RAIRO Anal. Numer. 10 (1976) 5-12. | Numdam | MR 470565
[25] , Splines minimizing rotation-invariant semi-norms in Sobolev spaces, in Constructive theory of functions of several variables, Proc. of Conf., Math. Res. Inst., Oberwolfach, 1976, in vol. 571. of Lect. Notes Math. Springer, Berlin (1977) 85-100. | MR 493110 | Zbl 0342.41012
[26] , Sur l'erreur d'interpolation des fonctions de plusieurs variables par les Dm-splines. RAIRO Anal. Numér. (1978) 12 325-334. | Numdam | MR 519016 | Zbl 0403.41003
[27] W. E and B. Engquist, The heterogeneous multiscale methods. Commun. Math. Sci. 1 (2003) 87-132. | MR 1979846 | Zbl 1093.35012
[28] , and , Multiscale finite element and domain decomposition methods for high-contrast problems using local spectral basis functions. J. Comput. Phys. 230 (2011) 937-955. | Zbl pre05867068
[29] , , and , Accurate multiscale finite element methods for two-phase flow simulations. J. Comput. Phys. 220 (2006) 155-174. | MR 2281625 | Zbl 1158.76349
[30] and , Multiscale finite element methods for porous media flows and their applications. Appl. Numer. Math. 57 (2007) 577-596. | MR 2322432 | Zbl 1112.76046
[31] and , Multiscale finite element methods, Theory and applications, in vol. 4, Surveys and Tutorials in the Applied Mathematical Sciences. Springer, New York (2009). | MR 2477579 | Zbl 1163.65080
[32] and , Convex Analysis and Variational Problems, vol. 28 of Classics in Appl. Math. Society for Industrial and Applied Mathematics (1987). | MR 1727362 | Zbl 0939.49002
[33] and , Asymptotic and numerical homogenization. Acta Numerica 17 (2008) 147-190. | MR 2436011 | Zbl 1179.65142
[34] , and , Multi-scale methods for wave propagation in heterogeneous media. Commun. Math. Sci. 9 (2011) 33-56. | MR 2836835 | Zbl 1281.65110
[35] , Multiple integrals in the calculus of variations and nonlinear elliptic systems, vol. 105. Ann. Math. Stud. Princeton University Press, Princeton, NJ (1983). | MR 717034 | Zbl 0516.49003
[36] and , Elliptic Partial Differential Equations of Second Order, 2nd edn. Springer-Verlag (1983). | MR 737190
[37] , Sulla convergenza di alcune successioni di integrali del tipo dell'aera. Rendi Conti di Mat. 8 (1975) 277-294. | MR 375037 | Zbl 0316.35036
[38] , Analytical framework for the numerical homogenization of elliptic monotone operators and quasiconvex energies. SIAM MMS 5 (2006) 996-1043. | MR 2272308 | Zbl 1119.74038
[39] , Reduction of the resonance error-Part 1: Approximation of homogenized coefficients. Math. Models Methods Appl. Sci. 21 (2011) 1601-1630. | MR 2826466 | Zbl 1233.35016
[40] and , An optimal error estimate in stochastic homogenization of discrete elliptic equations. Ann. Appl. Probab. 22 (2012) 1-28. | MR 2932541 | Zbl pre06026087
[41] , and , The al basis for the solution of elliptic problems in heterogeneous media. Multiscale Modeling and Simulation 10 (2012) 245-258. | MR 2902606 | Zbl 1250.65140
[42] and , The green function for uniformly elliptic equations. Manuscripta Math. 37 (1982) 303-342. | MR 657523 | Zbl 0485.35031
[43] and , Interpolation using surface splines. J. Aircr. 9 (1972) 189-191.
[44] , and , Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficients. Math. Comput. 68 (1999) 913-943. | MR 1642758 | Zbl 0922.65071
[45] and , A multiscale finite element method for elliptic problems in composite materials and porous media. J. Comput. Phys. 134 (1997) 169-189. | MR 1455261 | Zbl 0880.73065
[46] , and , Homogenization of Differential Operators and Integral Functionals. Springer-Verlag (1991). | MR 1329546 | Zbl 0801.35001
[47] , and , Stochastic homogenization of Hamilton-Jacobi-Bellman equations. Comm. Pure Appl. Math. 59 (2006) 1489-1521. | MR 2248897 | Zbl 1111.60055
[48] and , Polyharmonic splines on grids Z× aZn and their limits. Math. Comput. 74 (2005) 1831-1841. | MR 2164099 | Zbl 1075.41003
[49] , The averaging of random operators. Mat. Sb. (N.S.) 109 (1979) 188-202, 327. | MR 542557 | Zbl 0415.60059
[50] and , Correctors for the homogenization of Hamilton-Jacobi equations in the stationary ergodic setting. Comm. Pure Appl. Math. 56 (2003) 1501-1524. | MR 1988897 | Zbl 1050.35012
[51] and , Multivariate interpolation and conditionally positive definite functions. Approx. Theory Appl. 4 (1988) 77-89. | MR 986343 | Zbl 0703.41008
[52] and , Multivariate interpolation and conditionally positive definite functions. II. Math. Comput. 54 (1990) 211-230. | MR 993931 | Zbl 0859.41004
[53] and , Polyharmonic cardinal splines. J. Approx. Theory 60 (1990) 141-156. | MR 1033167 | Zbl 0702.41020
[54] and , Polyharmonic cardinal splines: a minimization property. J. Approx. Theory 63 (1990) 303-320. | MR 1081032 | Zbl 0719.41016
[55] and , Localization of elliptic multiscale problems. Technical report arXiv:1110.0692 (2012). | MR 3246801 | Zbl 1301.65123
[56] , Some methods for the reconstruction of functions of n variables defined on chaotic grids. Dokl. Akad. Nauk 326 (1992) 605-609. | MR 1198348 | Zbl 0802.41011
[57] , Spline interpolation of functions of several variables and bases in Sobolev spaces. Trudy Mat. Inst. Steklov. 198 (1992) 125-152. | MR 1289922 | Zbl 0834.41017
[58] , Interpolation of functions on chaotic grids. Dokl. Akad. Nauk 339 (1994) 594-597. | MR 1316519 | Zbl 0866.41004
[59] , Methods for the approximate recovery of functions defined on chaotic grids. Izv. Ross. Akad. Nauk Ser. Mat. 60 111-156, 1996. | MR 1427398 | Zbl 0883.41007
[60] , On a method for the interpolation of functions on chaotic grids. Mat. Zametki 62 (1997) 404-417. | MR 1620074 | Zbl 0920.41001
[61] , On n-widths for elliptic problems. J. Math. Anal. Appl. 247 (2000) 272-289. | MR 1766938 | Zbl 0963.35047
[62] , The theory of composites, vol. 6 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge (2002). | MR 1899805 | Zbl 0993.74002
[63] and , Numerical methods for multiscale elliptic problems. J. Comput. Phys. 214 (2006) 421-445. | MR 2208685 | Zbl 1092.65102
[64] , Theory of partial differential equations. MA6000A. Lect. Notes (2012). Available on http://people.bath.ac.uk/rm257/MA6000A/notes.pdf.
[65] and , H-convergence. Séminaire d'Analyse Fonctionnelle et Numérique de l'Université d'Alger (1978).
[66] , and , Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting. Math. Comput. 74 (2005) 743-763. | MR 2114646 | Zbl 1063.41013
[67] , A general convergence result for a functional related to the theory of homogenization. SIAM J. Math. Anal. 20 (1989) 608-623. | MR 990867 | Zbl 0688.35007
[68] , and , A framework for adaptive multiscale methods for elliptic problems. Multiscale Model. Simul. 7 (2008) 171-196. | MR 2399542 | Zbl 1160.65342
[69] and , Metric-based upscaling. Comm. Pure Appl. Math. 60 (2007) 675-723. | MR 2292954 | Zbl 1190.35070
[70] and . Localized bases for finite dimensional homogenization approximations with non-separated scales and high-contrast. SIAM Multiscale Model. Simul. 9 (2011) 1373-1398. arXiv:1011.0986. | MR 2861243 | Zbl 1244.65140
[71] , Anomalous slow diffusion from perpetual homogenization. Ann. Probab. 31 (2003) 1935-1969. | MR 2016606 | Zbl 1042.60049
[72] , Averaging versus chaos in turbulent transport? Comm. Math. Phys. 247 (2004) 553-599. | MR 2062644 | Zbl 1056.76038
[73] and , Boundary value problems with rapidly oscillating random coefficients, in Random fields, Vol. I, II (Esztergom (1979)), vol. 27. Colloq. Math. Soc. János Bolyai. North-Holland, Amsterdam (1981) 835-873. | MR 712714 | Zbl 0499.60059
[74] , N-Widths in Approximation Theory. Springer-Verlag (1985). | MR 774404 | Zbl 0551.41001
[75] , B-splines Polyarmoniques Cardinales: Interpolation, Quasi-interpolation, filtrage. Thèse d'État. Université de Toulouse (1990).
[76] , Elementary m-harmonic cardinal B-splines. Numer. Algorithms 2 (1992) 39-61. | MR 1149064 | Zbl 0851.41010
[77] , High level m-harmonic cardinal B-splines. Numer. Algorithms 2 (1992) 63-84. | MR 1149065 | Zbl 0897.41008
[78] , Detecting discontinuities in two-dimensional signals sampled on a grid. JNAIAM J. Numer. Anal. Ind. Appl. Math. 4 (2009) 203-215. | MR 2821355
[79] , Cardinal spline interpolation. Conference Board of the Mathematical Sciences Regional Conf. Ser. Appl. Math. No. 12. Society for Industrial and Applied Mathematics, Philadelphia, Pa., (1973). | MR 420078 | Zbl 0264.41003
[80] , Sulla convergenza di soluzioni di equazioni paraboliche ed ellittiche. Ann. Scuola Norm. Sup. Pisa 22 (1968) 571-597; errata, S. Spagnolo, Ann. Scuola Norm. Sup. Pisa 22 (1968) 673. | Numdam | MR 240443 | Zbl 0174.42101
[81] , Le problème de dirichlet pour les équations elliptiques du second ordre à coefficients discontinus. Ann. Inst. Fourier (Grenoble) 15 (1965) 189-258. | Numdam | MR 192177 | Zbl 0151.15401
[82] , Èquations elliptiques du second ordre à coefficients discontinus. Séminaire Jean Leray No. 3 (1963-1964). Numdam (1964). | Zbl 0151.15501
[83] . Transfer of approximation and numerical homogenization of hyperbolic boundary value problems with a continuum of scales. TR12-20 Rice Tech Report (2012).
[84] , and , The green function for elliptic systems in two dimensions. arXiv:1205.1089 (2012). | MR 3169756 | Zbl 1279.35021
[85] , Widths of embeddings in function spaces. J. Complexity 24 (2008) 545-570. | MR 2432104 | Zbl 1143.41301
[86] and , Computing absolute transmissibility in the presence of finescale heterogeneity. SPE Symposium on Reservoir Simulation 16011 (1987).
[87] , and , Analysis of upscaling absolute permeability. Discrete Contin. Dyn. Syst. Ser. B 2 (2002) 185-204. | MR 1898136 | Zbl 1162.65327
[88] , Averaging of symmetric diffusion in a random medium. Sibirsk. Mat. Zh. 27 (1986) 167-180. | MR 867870 | Zbl 0614.60051