Hostname: page-component-8448b6f56d-qsmjn Total loading time: 0 Render date: 2024-04-23T15:20:36.778Z Has data issue: false hasContentIssue false
  • English
  • Français

Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization

Published online by Cambridge University Press:  11 March 2014

Houman Owhadi ,
Lei Zhang  and
Leonid Berlyand
Houman Owhadi
Affiliation:
Corresponding author. California Institute of Technology, Computing and Mathematical Sciences, MC 9-94, Pasadena, CA 91125, USA. owhadi@caltech.edu
Lei Zhang
Affiliation:
Shanghai Jiaotong University, Institute of Natural Sciences and Department of Mathematics, Key Laboratory of Scientific and Engineering Computing (Shanghai Jiao Tong University), Ministry of Education, 800 Dongchuan Road, Shanghai 200240, P.R. China; lzhang2012@sjtu.edu.cn
Leonid Berlyand
Affiliation:
Pennsylvania State University, Department of Mathematics, University Park, PA, 16802, USA; berlyand@math.psu.edu
Get access

Abstract

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.

Keywords

Homogenizationpolyharmonic splineslocalization
Type
Research Article
Information
ESAIM: Mathematical Modelling and Numerical Analysis , Volume 48 , Issue 2: Multiscale problems and techniques , March 2014 , pp. 517 - 552
Copyright
© EDP Sciences, SMAI, 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abdulle, A. and Grote, M.J., Finite element heterogeneous multiscale method for the wave equation. Multiscale Model. Simul. 9 (2011) 766–792. Google Scholar
Abdulle, A. and Schwab, Ch., Heterogeneous multiscale FEM for diffusion problems on rough surfaces. Multiscale Model. Simul. 3 (2004) 195–220. Google Scholar
Allaire, G. and Brizzi, R., A multiscale finite element method for numerical homogenization. Multiscale Model. Simul. 4 (2005) 790–812. Google Scholar
Arbogast, T. and Boyd, K.J.. Subgrid upscaling and mixed multiscale finite elements. SIAM J. Numer. Anal. 44 (2006) 1150–1171. Google Scholar
Arbogast, T., Huang, C.-S. and Yang, S.-M., 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. Google Scholar
Armstrong, S.N. and Souganidis, P.E., Stochastic homogenization of Hamilton-Jacobi and degenerate Bellman equations in unbounded environments. J. Math. Pures Appl. 97 (2012) 460–504. Google Scholar
Atteia, M., Fonctions spline et noyaux reproduisants d’Aronszajn-Bergman. Rev. Française Informat. Recherche Opérationnelle 4 (1970) 31–43. Google Scholar
Babuška, I., Caloz, G. and Osborn, J.E., Special finite element methods for a class of second order elliptic problems with rough coefficients. SIAM J. Numer. Anal. 31 (1994) 945–981. Google Scholar
Babuška, I. and Lipton, R., Optimal local approximation spaces for generalized finite element methods with application to multiscale problems. Multiscale Model. Simul. 9 (2011) 373–406. Google Scholar
Babuška, I. and Osborn, J.E., Generalized finite element methods: their performance and their relation to mixed methods. SIAM J. Numer. Anal. 20 (1983) 510–536. Google Scholar
Babuška, I. and Osborn, J.E., Can a finite element method perform arbitrarily badly? Math. Comput. 69 (2000) 443–462. Google Scholar
Bal, G. and Jing, W., Corrector theory for MSFEM and HMM in random media. Multiscale Model. Simul. 9 (2011) 1549–1587. Google Scholar
Ben Arous, G. and Owhadi, H., Multiscale homogenization with bounded ratios and anomalous slow diffusion. Comm. Pure Appl. Math. 56 (2003) 80–113. Google Scholar
A. Bensoussan, J.L. Lions and G. Papanicolaou, Asymptotic analysis for periodic structure. North Holland, Amsterdam (1978).
Berlyand, L. and Owhadi, H., Flux norm approach to finite dimensional homogenization approximations with non-separated scales and high contrast. Arch. Rational Mech. Anal. 198 (2010) 677–721. Google Scholar
Blanc, X., Le Bris, C. and Lions, P.-L., 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. Google Scholar
Blanc, X., Le Bris, C. and Lions, P.-L., Stochastic homogenization and random lattices. J. Math. Pures Appl. 88 (2007) 34–63. Google Scholar
Bourgeat, A. and Piatnitski, A., 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. Google Scholar
Branets, L.V., Ghai, S.S., L.L. and Wu, X.-H., Challenges and technologies in reservoir modeling. Commun. Comput. Phys. (2009) 6 1–23. Google Scholar
R.A. Brownlee, Error estimates for interpolation of rough and smooth functions using radial basis functions. Ph.D. thesis. University of Leicester (2004).
Caffarelli, L.A. and Souganidis, P.E., A rate of convergence for monotone finite difference approximations to fully nonlinear, uniformly elliptic PDEs. Comm. Pure Appl. Math. 61 (2008) 1–17. Google Scholar
Chu, C.-C., Graham, I.G. and Hou, T.Y., A new multiscale finite element method for high-contrast elliptic interface problems. Math. Comput. 79 (2010) 1915–1955. Google Scholar
M. Desbrun, R. Donaldson and H. Owhadi. 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).
Duchon, J., 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. Google Scholar
J. Duchon, 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.
Duchon, J., Sur l’erreur d’interpolation des fonctions de plusieurs variables par les D m-splines. RAIRO Anal. Numér. (1978) 12 325–334. Google Scholar
W. E and Engquist, B., The heterogeneous multiscale methods. Commun. Math. Sci. 1 (2003) 87–132. Google Scholar
Efendiev, Y., Galvis, J. and Wu, X., Multiscale finite element and domain decomposition methods for high-contrast problems using local spectral basis functions. J. Comput. Phys. 230 (2011) 937–955. Google Scholar
Efendiev, Y., Ginting, V., Hou, T. and Ewing, R., Accurate multiscale finite element methods for two-phase flow simulations. J. Comput. Phys. 220 (2006) 155–174. Google Scholar
Efendiev, Y. and Hou, T., Multiscale finite element methods for porous media flows and their applications. Appl. Numer. Math. 57 (2007) 577–596. Google Scholar
Y. Efendiev and T.Y. Hou, Multiscale finite element methods, Theory and applications, in vol. 4, Surveys and Tutorials in the Applied Mathematical Sciences. Springer, New York (2009).
I. Ekeland and R. Temam, Convex Analysis and Variational Problems, vol. 28 of Classics in Appl. Math. Society for Industrial and Applied Mathematics (1987).
Engquist, B. and Souganidis, P.E., Asymptotic and numerical homogenization. Acta Numerica 17 (2008) 147–190. Google Scholar
Engquist, B., Holst, H. and Runborg, O., Multi-scale methods for wave propagation in heterogeneous media. Commun. Math. Sci. 9 (2011) 33–56. Google Scholar
M. Giaquinta, Multiple integrals in the calculus of variations and nonlinear elliptic systems, vol. 105. Ann. Math. Stud. Princeton University Press, Princeton, NJ (1983).
D. Gilbarg and N.S. Trudinger, Elliptic Partial Differential Equations of Second Order, 2nd edn. Springer-Verlag (1983).
De Giorgi, E., Sulla convergenza di alcune successioni di integrali del tipo dell’aera. Rendi Conti di Mat. 8 (1975) 277–294. Google Scholar
Gloria, A., Analytical framework for the numerical homogenization of elliptic monotone operators and quasiconvex energies. SIAM MMS 5 (2006) 996–1043. Google Scholar
Gloria, A., Reduction of the resonance error-Part 1: Approximation of homogenized coefficients. Math. Models Methods Appl. Sci. 21 (2011) 1601–1630. Google Scholar
Gloria, A. and Otto, F., An optimal error estimate in stochastic homogenization of discrete elliptic equations. Ann. Appl. Probab. 22 (2012) 1–28. Google Scholar
Grasedyck, L., Greff, I. and Sauter, S., The al basis for the solution of elliptic problems in heterogeneous media. Multiscale Modeling and Simulation 10 (2012) 245–258. Google Scholar
Grüter, M. and Widman, K., The green function for uniformly elliptic equations. Manuscripta Math. 37 (1982) 303–342. Google Scholar
Harder, R.L. and Desmarais, R.N., Interpolation using surface splines. J. Aircr. 9 (1972) 189–191. Google Scholar
Hou, T.Y., Wu, X.-H. and Cai, Z., Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficients. Math. Comput. 68 (1999) 913–943. Google Scholar
Hou, T.Y. and Wu, X.H., A multiscale finite element method for elliptic problems in composite materials and porous media. J. Comput. Phys. 134 (1997) 169–189. Google Scholar
V.V. Jikov, S.M. Kozlov and O.A. Oleinik, Homogenization of Differential Operators and Integral Functionals. Springer-Verlag (1991).
Kosygina, E., Rezakhanlou, F. and Varadhan, S.R.S., Stochastic homogenization of Hamilton-Jacobi-Bellman equations. Comm. Pure Appl. Math. 59 (2006) 1489–1521. Google Scholar
Kounchev, O. and Render, H., Polyharmonic splines on grids Z× aZn and their limits. Math. Comput. 74 (2005) 1831–1841. Google Scholar
Kozlov, S.M., The averaging of random operators. Mat. Sb. (N.S.) 109 (1979) 188–202, 327. Google Scholar
Lions, P.-L. and Souganidis, P.E., Correctors for the homogenization of Hamilton-Jacobi equations in the stationary ergodic setting. Comm. Pure Appl. Math. 56 (2003) 1501–1524. Google Scholar
Madych, W.R. and Nelson, S.A., Multivariate interpolation and conditionally positive definite functions. Approx. Theory Appl. 4 (1988) 77–89. Google Scholar
Madych, W.R. and Nelson, S.A., Multivariate interpolation and conditionally positive definite functions. II. Math. Comput. 54 (1990) 211–230. Google Scholar
Madych, W.R. and Nelson, S.A., Polyharmonic cardinal splines. J. Approx. Theory 60 (1990) 141–156. Google Scholar
Madych, W.R. and Nelson, S.A., Polyharmonic cardinal splines: a minimization property. J. Approx. Theory 63 (1990) 303–320. Google Scholar
A. Malqvist and D. Peterseim, Localization of elliptic multiscale problems. Technical report arXiv:1110.0692 (2012).
Matveev, O.V., Some methods for the reconstruction of functions of n variables defined on chaotic grids. Dokl. Akad. Nauk 326 (1992) 605–609. Google Scholar
Matveev, O.V., Spline interpolation of functions of several variables and bases in Sobolev spaces. Trudy Mat. Inst. Steklov. 198 (1992) 125–152. Google Scholar
Matveev, O.V., Interpolation of functions on chaotic grids. Dokl. Akad. Nauk 339 (1994) 594–597. Google Scholar
Matveev, O.V., Methods for the approximate recovery of functions defined on chaotic grids. Izv. Ross. Akad. Nauk Ser. Mat. 60 111–156, 1996. Google Scholar
Matveev, O.V., On a method for the interpolation of functions on chaotic grids. Mat. Zametki 62 (1997) 404–417. Google Scholar
Melenk, J.M., On n-widths for elliptic problems. J. Math. Anal. Appl. 247 (2000) 272–289. Google Scholar
G.W. Milton, The theory of composites, vol. 6 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge (2002).
Ming, P. and Yue, X., Numerical methods for multiscale elliptic problems. J. Comput. Phys. 214 (2006) 421–445. Google Scholar
R. Moser, Theory of partial differential equations. MA6000A. Lect. Notes (2012). Available on http://people.bath.ac.uk/rm257/MA6000A/notes.pdf.
F. Murat and L. Tartar, H-convergence. Séminaire d’Analyse Fonctionnelle et Numérique de l’Université d’Alger (1978).
Narcowich, F.J., Ward, J.D. and Wendland, H., Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting. Math. Comput. 74 (2005) 743–763. Google Scholar
Nguetseng, G., A general convergence result for a functional related to the theory of homogenization. SIAM J. Math. Anal. 20 (1989) 608–623. Google Scholar
Nolen, J., Papanicolaou, G. and Pironneau, O., A framework for adaptive multiscale methods for elliptic problems. Multiscale Model. Simul. 7 (2008) 171–196. Google Scholar
Owhadi, H. and Zhang, L., Metric-based upscaling. Comm. Pure Appl. Math. 60 (2007) 675–723. Google Scholar
Owhadi, H. and Zhang, L.. 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. Google Scholar
Owhadi, H., Anomalous slow diffusion from perpetual homogenization. Ann. Probab. 31 (2003) 1935–1969. Google Scholar
Owhadi, H., Averaging versus chaos in turbulent transport? Comm. Math. Phys. 247 (2004) 553–599. Google Scholar
G.C. Papanicolaou and S.R.S. Varadhan, 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.
A. Pinkus, N-Widths in Approximation Theory. Springer-Verlag (1985).
C. Rabut, B-splines Polyarmoniques Cardinales: Interpolation, Quasi-interpolation, filtrage. Thèse d’État. Université de Toulouse (1990).
Rabut, Ch., Elementary m-harmonic cardinal B-splines. Numer. Algorithms 2 (1992) 39–61. Google Scholar
Rabut, Ch., High level m-harmonic cardinal B-splines. Numer. Algorithms 2 (1992) 63–84. Google Scholar
Rossini, M., Detecting discontinuities in two-dimensional signals sampled on a grid. JNAIAM J. Numer. Anal. Ind. Appl. Math. 4 (2009) 203–215. Google Scholar
I.J. Schoenberg, 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).
Spagnolo, S., 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. Google Scholar
Stampacchia, G., Le problème de dirichlet pour les équations elliptiques du second ordre à coefficients discontinus. Ann. Inst. Fourier (Grenoble) 15 (1965) 189–258. Google Scholar
G. Stampacchia, Èquations elliptiques du second ordre à coefficients discontinus. Séminaire Jean Leray No. 3 (1963–1964). Numdam (1964).
William Symes. Transfer of approximation and numerical homogenization of hyperbolic boundary value problems with a continuum of scales. TR12-20 Rice Tech Report (2012).
J.L. Taylor, S. Kim and R.M. Brown, The green function for elliptic systems in two dimensions. arXiv:1205.1089 (2012).
Vybiral, J., Widths of embeddings in function spaces. J. Complexity 24 (2008) 545–570. Google Scholar
C.D. White and R.N. Horne, Computing absolute transmissibility in the presence of finescale heterogeneity. SPE Symposium on Reservoir Simulation 16011 (1987).
Wu, X.H., Efendiev, Y. and Hou, T.Y., Analysis of upscaling absolute permeability. Discrete Contin. Dyn. Syst. Ser. B 2 (2002) 185–204. Google Scholar
Yurinskiĭ, V.V., Averaging of symmetric diffusion in a random medium. Sibirsk. Mat. Zh. 27 (1986) 167–180. Google Scholar