Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization

Houman Owhadi; Lei Zhang; Leonid Berlyand

ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique (2014)

  • Volume: 48, Issue: 2, page 517-552
  • ISSN: 0764-583X

Abstract

top
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.

How to cite

top

Owhadi, Houman, Zhang, Lei, and 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 48.2 (2014): 517-552. <http://eudml.org/doc/273273>.

@article{Owhadi2014,
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 &#x1d4aa;(H−d) quadratic (cell) problems on (super-)localized sub-domains of size &#x1d4aa;(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 (&#x1d4aa;(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.},
author = {Owhadi, Houman, Zhang, Lei, Berlyand, Leonid},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique},
keywords = {homogenization; polyharmonic splines; localization},
language = {eng},
number = {2},
pages = {517-552},
publisher = {EDP-Sciences},
title = {Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization},
url = {http://eudml.org/doc/273273},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Owhadi, Houman
AU - Zhang, Lei
AU - Berlyand, Leonid
TI - Polyharmonic homogenization, rough polyharmonic splines and sparse super-localization
JO - ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 2
SP - 517
EP - 552
AB - 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 &#x1d4aa;(H−d) quadratic (cell) problems on (super-)localized sub-domains of size &#x1d4aa;(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 (&#x1d4aa;(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.
LA - eng
KW - homogenization; polyharmonic splines; localization
UR - http://eudml.org/doc/273273
ER -

References

top
  1. [1] A. Abdulle and M.J. Grote, Finite element heterogeneous multiscale method for the wave equation. Multiscale Model. Simul.9 (2011) 766–792. Zbl1298.65145MR2818419
  2. [2] A. Abdulle and Ch. Schwab, Heterogeneous multiscale FEM for diffusion problems on rough surfaces. Multiscale Model. Simul.3 (2004) 195–220. Zbl1160.65337MR2123116
  3. [3] G. Allaire and R. Brizzi, A multiscale finite element method for numerical homogenization. Multiscale Model. Simul.4 (2005) 790–812. Zbl1093.35007MR2203941
  4. [4] T. Arbogast and K.J. Boyd. Subgrid upscaling and mixed multiscale finite elements. SIAM J. Numer. Anal.44 (2006) 1150–1171. Zbl1120.65122MR2231859
  5. [5] T. Arbogast, C.-S. Huang and S.-M. Yang, 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. Zbl1146.65068MR2342991
  6. [6] S.N. Armstrong and P.E. Souganidis, Stochastic homogenization of Hamilton-Jacobi and degenerate Bellman equations in unbounded environments. J. Math. Pures Appl.97 (2012) 460–504. Zbl1246.35029MR2914944
  7. [7] M. Atteia, Fonctions spline et noyaux reproduisants d’Aronszajn-Bergman. Rev. Française Informat. Recherche Opérationnelle4 (1970) 31–43. Zbl0213.12502MR300061
  8. [8] I. Babuška, G. Caloz and J.E. Osborn, Special finite element methods for a class of second order elliptic problems with rough coefficients. SIAM J. Numer. Anal.31 (1994) 945–981. Zbl0807.65114MR1286212
  9. [9] I. Babuška and R. Lipton, Optimal local approximation spaces for generalized finite element methods with application to multiscale problems. Multiscale Model. Simul.9 (2011) 373–406. Zbl1229.65195MR2801210
  10. [10] I. Babuška and J.E. Osborn, Generalized finite element methods: their performance and their relation to mixed methods. SIAM J. Numer. Anal.20 (1983) 510–536. Zbl0528.65046MR701094
  11. [11] I. Babuška and J.E. Osborn, Can a finite element method perform arbitrarily badly? Math. Comput.69 (2000) 443–462. Zbl0940.65086MR1648351
  12. [12] G. Bal and W. Jing, Corrector theory for MSFEM and HMM in random media. Multiscale Model. Simul.9 (2011) 1549–1587. Zbl1244.65004MR2861250
  13. [13] G. Ben Arous and H. Owhadi, Multiscale homogenization with bounded ratios and anomalous slow diffusion. Comm. Pure Appl. Math.56 (2003) 80–113. Zbl1205.76223MR1929443
  14. [14] A. Bensoussan, J.L. Lions and G. Papanicolaou, Asymptotic analysis for periodic structure. North Holland, Amsterdam (1978). Zbl0404.35001MR503330
  15. [15] L. Berlyand and H. Owhadi, Flux norm approach to finite dimensional homogenization approximations with non-separated scales and high contrast. Arch. Rational Mech. Anal.198 (2010) 677–721. Zbl1229.35009MR2721592
  16. [16] X. Blanc, C. Le Bris and P.-L. Lions, Une variante de la théorie de l’homogénéisation stochastique des opérateurs elliptiques. C. R. Math. Acad. Sci. Paris343 (2006) 717–724. Zbl1103.35014MR2284699
  17. [17] X. Blanc, C. Le Bris and P.-L. Lions, Stochastic homogenization and random lattices. J. Math. Pures Appl.88 (2007) 34–63. Zbl1129.60055MR2334772
  18. [18] A. Bourgeat and A. Piatnitski, 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. Zbl0960.60057MR1728027
  19. [19] L.V. Branets, S.S. Ghai, L.L. and X.-H. Wu, Challenges and technologies in reservoir modeling. Commun. Comput. Phys. (2009) 6 1–23. MR2537305
  20. [20] R.A. Brownlee, Error estimates for interpolation of rough and smooth functions using radial basis functions. Ph.D. thesis. University of Leicester (2004). 
  21. [21] L.A. Caffarelli and P.E. Souganidis, A rate of convergence for monotone finite difference approximations to fully nonlinear, uniformly elliptic PDEs. Comm. Pure Appl. Math.61 (2008) 1–17. Zbl1140.65075MR2361302
  22. [22] C.-C. Chu, I.G. Graham and T.Y. Hou, A new multiscale finite element method for high-contrast elliptic interface problems. Math. Comput.79 (2010) 1915–1955. Zbl1202.65154MR2684351
  23. [23] 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). MR3221686
  24. [24] J. Duchon, 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. MR470565
  25. [25] 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. Zbl0342.41012MR493110
  26. [26] J. Duchon, Sur l’erreur d’interpolation des fonctions de plusieurs variables par les Dm-splines. RAIRO Anal. Numér. (1978) 12 325–334. Zbl0403.41003MR519016
  27. [27] W. E and B. Engquist, The heterogeneous multiscale methods. Commun. Math. Sci. 1 (2003) 87–132. Zbl1093.35012MR1979846
  28. [28] Y. Efendiev, J. Galvis and X. Wu, Multiscale finite element and domain decomposition methods for high-contrast problems using local spectral basis functions. J. Comput. Phys.230 (2011) 937–955. Zbl05867068
  29. [29] Y. Efendiev, V. Ginting, T. Hou and R. Ewing, Accurate multiscale finite element methods for two-phase flow simulations. J. Comput. Phys.220 (2006) 155–174. Zbl1158.76349MR2281625
  30. [30] Y. Efendiev and T. Hou, Multiscale finite element methods for porous media flows and their applications. Appl. Numer. Math.57 (2007) 577–596. Zbl1112.76046MR2322432
  31. [31] 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). Zbl1163.65080MR2477579
  32. [32] I. Ekeland and R. Temam, Convex Analysis and Variational Problems, vol. 28 of Classics in Appl. Math. Society for Industrial and Applied Mathematics (1987). Zbl0939.49002MR1727362
  33. [33] B. Engquist and P.E. Souganidis, Asymptotic and numerical homogenization. Acta Numerica17 (2008) 147–190. Zbl1179.65142MR2436011
  34. [34] B. Engquist, H. Holst and O. Runborg, Multi-scale methods for wave propagation in heterogeneous media. Commun. Math. Sci.9 (2011) 33–56. Zbl1281.65110MR2836835
  35. [35] M. Giaquinta, Multiple integrals in the calculus of variations and nonlinear elliptic systems, vol. 105. Ann. Math. Stud. Princeton University Press, Princeton, NJ (1983). Zbl0516.49003MR717034
  36. [36] D. Gilbarg and N.S. Trudinger, Elliptic Partial Differential Equations of Second Order, 2nd edn. Springer-Verlag (1983). Zbl0361.35003MR737190
  37. [37] E. De Giorgi, Sulla convergenza di alcune successioni di integrali del tipo dell’aera. Rendi Conti di Mat.8 (1975) 277–294. Zbl0316.35036MR375037
  38. [38] A. Gloria, Analytical framework for the numerical homogenization of elliptic monotone operators and quasiconvex energies. SIAM MMS5 (2006) 996–1043. Zbl1119.74038MR2272308
  39. [39] A. Gloria, Reduction of the resonance error-Part 1: Approximation of homogenized coefficients. Math. Models Methods Appl. Sci.21 (2011) 1601–1630. Zbl1233.35016MR2826466
  40. [40] A. Gloria and F. Otto, An optimal error estimate in stochastic homogenization of discrete elliptic equations. Ann. Appl. Probab.22 (2012) 1–28. Zbl06026087MR2932541
  41. [41] L. Grasedyck, I. Greff and S. Sauter, The al basis for the solution of elliptic problems in heterogeneous media. Multiscale Modeling and Simulation10 (2012) 245–258. Zbl1250.65140MR2902606
  42. [42] M. Grüter and K. Widman, The green function for uniformly elliptic equations. Manuscripta Math.37 (1982) 303–342. Zbl0485.35031MR657523
  43. [43] R.L. Harder and R.N. Desmarais, Interpolation using surface splines. J. Aircr.9 (1972) 189–191. 
  44. [44] T.Y. Hou, X.-H. Wu and Z. Cai, Convergence of a multiscale finite element method for elliptic problems with rapidly oscillating coefficients. Math. Comput.68 (1999) 913–943. Zbl0922.65071MR1642758
  45. [45] T.Y. Hou and X.H. Wu, A multiscale finite element method for elliptic problems in composite materials and porous media. J. Comput. Phys.134 (1997) 169–189. Zbl0880.73065MR1455261
  46. [46] V.V. Jikov, S.M. Kozlov and O.A. Oleinik, Homogenization of Differential Operators and Integral Functionals. Springer-Verlag (1991). Zbl0801.35001MR1329546
  47. [47] E. Kosygina, F. Rezakhanlou and S.R.S. Varadhan, Stochastic homogenization of Hamilton-Jacobi-Bellman equations. Comm. Pure Appl. Math.59 (2006) 1489–1521. Zbl1111.60055MR2248897
  48. [48] O. Kounchev and H. Render, Polyharmonic splines on grids Z× aZn and their limits. Math. Comput.74 (2005) 1831–1841. Zbl1075.41003MR2164099
  49. [49] S.M. Kozlov, The averaging of random operators. Mat. Sb. (N.S.) 109 (1979) 188–202, 327. Zbl0415.60059MR542557
  50. [50] P.-L. Lions and P.E. Souganidis, Correctors for the homogenization of Hamilton-Jacobi equations in the stationary ergodic setting. Comm. Pure Appl. Math.56 (2003) 1501–1524. Zbl1050.35012MR1988897
  51. [51] W.R. Madych and S.A. Nelson, Multivariate interpolation and conditionally positive definite functions. Approx. Theory Appl.4 (1988) 77–89. Zbl0703.41008MR986343
  52. [52] W.R. Madych and S.A. Nelson, Multivariate interpolation and conditionally positive definite functions. II. Math. Comput.54 (1990) 211–230. Zbl0859.41004MR993931
  53. [53] W.R. Madych and S.A. Nelson, Polyharmonic cardinal splines. J. Approx. Theory60 (1990) 141–156. Zbl0702.41020MR1033167
  54. [54] W.R. Madych and S.A. Nelson, Polyharmonic cardinal splines: a minimization property. J. Approx. Theory63 (1990) 303–320. Zbl0719.41016MR1081032
  55. [55] A. Malqvist and D. Peterseim, Localization of elliptic multiscale problems. Technical report arXiv:1110.0692 (2012). Zbl1301.65123MR3246801
  56. [56] O.V. Matveev, Some methods for the reconstruction of functions of n variables defined on chaotic grids. Dokl. Akad. Nauk326 (1992) 605–609. Zbl0802.41011MR1198348
  57. [57] O.V. Matveev, Spline interpolation of functions of several variables and bases in Sobolev spaces. Trudy Mat. Inst. Steklov.198 (1992) 125–152. Zbl0834.41017MR1289922
  58. [58] O.V. Matveev, Interpolation of functions on chaotic grids. Dokl. Akad. Nauk339 (1994) 594–597. Zbl0866.41004MR1316519
  59. [59] O.V. Matveev, Methods for the approximate recovery of functions defined on chaotic grids. Izv. Ross. Akad. Nauk Ser. Mat. 60 111–156, 1996. Zbl0883.41007MR1427398
  60. [60] O.V. Matveev, On a method for the interpolation of functions on chaotic grids. Mat. Zametki62 (1997) 404–417. Zbl0920.41001MR1620074
  61. [61] J.M. Melenk, On n-widths for elliptic problems. J. Math. Anal. Appl.247 (2000) 272–289. Zbl0963.35047MR1766938
  62. [62] G.W. Milton, The theory of composites, vol. 6 of Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge (2002). Zbl0993.74002MR1899805
  63. [63] P. Ming and X. Yue, Numerical methods for multiscale elliptic problems. J. Comput. Phys.214 (2006) 421–445. Zbl1092.65102MR2208685
  64. [64] R. Moser, Theory of partial differential equations. MA6000A. Lect. Notes (2012). Available on http://people.bath.ac.uk/rm257/MA6000A/notes.pdf. 
  65. [65] F. Murat and L. Tartar, H-convergence. Séminaire d’Analyse Fonctionnelle et Numérique de l’Université d’Alger (1978). 
  66. [66] F.J. Narcowich, J.D. Ward and H. Wendland, Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting. Math. Comput.74 (2005) 743–763. Zbl1063.41013MR2114646
  67. [67] G. Nguetseng, A general convergence result for a functional related to the theory of homogenization. SIAM J. Math. Anal.20 (1989) 608–623. Zbl0688.35007MR990867
  68. [68] J. Nolen, G. Papanicolaou and O. Pironneau, A framework for adaptive multiscale methods for elliptic problems. Multiscale Model. Simul.7 (2008) 171–196. Zbl1160.65342MR2399542
  69. [69] H. Owhadi and L. Zhang, Metric-based upscaling. Comm. Pure Appl. Math.60 (2007) 675–723. Zbl1190.35070MR2292954
  70. [70] H. Owhadi and L. Zhang. 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. Zbl1244.65140MR2861243
  71. [71] H. Owhadi, Anomalous slow diffusion from perpetual homogenization. Ann. Probab.31 (2003) 1935–1969. Zbl1042.60049MR2016606
  72. [72] H. Owhadi, Averaging versus chaos in turbulent transport? Comm. Math. Phys.247 (2004) 553–599. Zbl1056.76038MR2062644
  73. [73] 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. Zbl0499.60059MR712714
  74. [74] A. Pinkus, N-Widths in Approximation Theory. Springer-Verlag (1985). Zbl0551.41001MR774404
  75. [75] C. Rabut, B-splines Polyarmoniques Cardinales: Interpolation, Quasi-interpolation, filtrage. Thèse d’État. Université de Toulouse (1990). 
  76. [76] Ch. Rabut, Elementary m-harmonic cardinal B-splines. Numer. Algorithms2 (1992) 39–61. Zbl0851.41010MR1149064
  77. [77] Ch. Rabut, High level m-harmonic cardinal B-splines. Numer. Algorithms2 (1992) 63–84. Zbl0897.41008MR1149065
  78. [78] M. Rossini, Detecting discontinuities in two-dimensional signals sampled on a grid. JNAIAM J. Numer. Anal. Ind. Appl. Math.4 (2009) 203–215. MR2821355
  79. [79] 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). Zbl0264.41003MR420078
  80. [80] S. Spagnolo, 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. Zbl0174.42101MR240443
  81. [81] G. Stampacchia, Le problème de dirichlet pour les équations elliptiques du second ordre à coefficients discontinus. Ann. Inst. Fourier (Grenoble) 15 (1965) 189–258. Zbl0151.15401MR192177
  82. [82] G. Stampacchia, Èquations elliptiques du second ordre à coefficients discontinus. Séminaire Jean Leray No. 3 (1963–1964). Numdam (1964). Zbl0151.15501
  83. [83] William Symes. Transfer of approximation and numerical homogenization of hyperbolic boundary value problems with a continuum of scales. TR12-20 Rice Tech Report (2012). 
  84. [84] J.L. Taylor, S. Kim and R.M. Brown, The green function for elliptic systems in two dimensions. arXiv:1205.1089 (2012). Zbl1279.35021MR3169756
  85. [85] J. Vybiral, Widths of embeddings in function spaces. J. Complexity24 (2008) 545–570. Zbl1143.41301MR2432104
  86. [86] C.D. White and R.N. Horne, Computing absolute transmissibility in the presence of finescale heterogeneity. SPE Symposium on Reservoir Simulation 16011 (1987). 
  87. [87] X.H. Wu, Y. Efendiev and T.Y. Hou, Analysis of upscaling absolute permeability. Discrete Contin. Dyn. Syst. Ser. B2 (2002) 185–204. Zbl1162.65327MR1898136
  88. [88] V.V. Yurinskiĭ, Averaging of symmetric diffusion in a random medium. Sibirsk. Mat. Zh.27 (1986) 167–180. Zbl0614.60051MR867870

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.