Machine Computation Using the Exponentially Convergent Multiscale Spectral Generalized Finite Element Method
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 2, p. 493-515

A multiscale spectral generalized finite element method (MS-GFEM) is presented for the solution of large two and three dimensional stress analysis problems inside heterogeneous media. It can be employed to solve problems too large to be solved directly with FE techniques and is designed for implementation on massively parallel machines. The method is multiscale in nature and uses an optimal family of spectrally defined local basis functions over a coarse grid. It is proved that the method has an exponential rate of convergence. To fix ideas we describe its implementation for a two dimensional plane strain problem inside a fiber reinforced composite. Here fibers are separated by a minimum distance however no special assumption on the fiber configuration such as periodicity or ergodicity is made. The implementation of MS-GFEM delivers the discrete solution operator using the same order of operations as the number of fibers inside the computational domain. This implementation is optimal in that the number of operations for solution is of the same order as the input data for the problem. The size of the MS-GFEM matrix used to represent the discrete inverse operator is controlled by the scale of the coarse grid and the convergence rate of the spectral basis and can be of order far less than the number of fibers. This strategy is general and can be applied to the solution of very large FE systems associated with the discrete solution of elliptic PDE.

DOI : https://doi.org/10.1051/m2an/2013117
Classification:  65N30,  74S05,  74Q05
Keywords: generalized finite elements, multiscale method, spectral method, heterogeneous media, fiber reinforced composites
@article{M2AN_2014__48_2_493_0,
author = {Babu\v ska, Ivo and Huang, Xu and Lipton, Robert},
title = {Machine Computation Using the Exponentially Convergent Multiscale Spectral Generalized Finite Element Method},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
publisher = {EDP-Sciences},
volume = {48},
number = {2},
year = {2014},
pages = {493-515},
doi = {10.1051/m2an/2013117},
mrnumber = {3177855},
language = {en},
url = {http://www.numdam.org/item/M2AN_2014__48_2_493_0}
}

Babuška, Ivo; Huang, Xu; Lipton, Robert. Machine Computation Using the Exponentially Convergent Multiscale Spectral Generalized Finite Element Method. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Volume 48 (2014) no. 2, pp. 493-515. doi : 10.1051/m2an/2013117. http://www.numdam.org/item/M2AN_2014__48_2_493_0/

[1] T. Arbogast and K.J. Boyd, Subgrid upscaling and mixed multiscale finite elements. SIAM J. Numer. Anal. 44 (2006) 1150-1171. | MR 2231859 | Zbl 1120.65122

[2] I. Babuška, Homogenization and Its Application. Mathematical and Computational Problems. SYNSPADE 1975, Numer. Solution Part. Differ. Eqs. lll, edited by B. Hubbard. Academic Press (1976) 89-116. | MR 502025 | Zbl 0346.65064

[3] I. Babuška, B. Anderson, P. Smith and K. Levin, Damage analysis of fiber composites, Part I Statistical analysis on fiber scale. Comput. Methods Appl. Mech Engrg. 172 (1999) 27-77. | MR 1685902 | Zbl 0956.74048

[4] I. Babuška, U. Banerjee and J. Osborn, Generalized Finite Element Methods-Main Ideas, Results and Perspective. Int. J. Comput. Methods 1 (2004) 67-103. | Zbl 1081.65107

[5] I. Babuška and U. Banerjee, Stable Generalized Finiter Element Methods (SGFEM). Comput. Meth. Appl. Mech. Eng. 201-204 (2012) 91-111. | MR 2862999 | Zbl 1239.74093

[6] 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. | MR 1286212 | Zbl 0807.65114

[7] I. Babuška and R. Lipton, Optimal local approximation spaces for Generalized Finite Element Methods with application to multiscale problems. Multiscale Model. Simul., SIAM 9 (2011) 373-406. | MR 2801210 | Zbl 1229.65195

[8] I. Babuška and R. Lipton, L2 global to local projection: an approach to multiscale analysis. M3AS 21 (2011) 2211-2226. | MR 2860673 | Zbl 1242.65234

[9] I. Babuška and J. Melenk, The Partition of Unity Finite Element Method. Internat. J. Numer. Methods Engrg. 40 (1997) 727-758. | MR 1429534 | Zbl 0949.65117

[10] I. Babuška, J, E. Osborn, Generalized finite element methods:Their performance and their relation to the mixed methods. SIAM, J. Numer. Anal. 20 (1983) 510-536. | MR 701094 | Zbl 0528.65046

[11] I. Babuška and J.E. Osborn, Eigenvalue Problems. Handbook of Numerical Analysis, Finite Element Methods (Part 1), Vol. II, edited by P.G. Ciarlet and J.L. Lions. Elsevier Science Publishers, Amsterdam (1991). | MR 1115240 | Zbl 0875.65087

[12] N.S. Bakhvalov and G. Panasenko, Homogenization Processes in Periodic Media. Nauka, Moscow (1984). | MR 797571 | Zbl 0692.73012

[13] R.M. Barrer, Diffusion and permeation in heterogenous media. Diffusion in Polymers, edited by J. Crank, G.S. Park. Academic Press (1968).

[14] M. Bebendorf and W. Hackbusch, Existence of ℋ-matrix approximants to the inverse FE-matrix of elliptic operators with L∞ coefficients. Numer. Math. 95 (2003) 1-28. | MR 1993936 | Zbl 1033.65100

[15] L. Berlyand and H. Owhadi, Flux norm approach to finite dimensional homogenization approximations with nonseparated length scales and high contrast. Arch. Rat. Mech. Anal. 198 (2010) 177-221. | MR 2721592 | Zbl 1229.35009

[16] A. Besounssan, J.L. Lions and G.C. Papanicolau, Asymptotic Analysis for Periodic Structures. North Holland Pub., Amsterdam (1978). | Zbl 0404.35001

[17] T. Burchuladze and R. Rukhadze, Asymptotic distribution of eigenfunctions and eigenvalues of the basic boundary-contact oscillation problems of the classical theory of elasticity. Georgian Math. J. 6 (1999) 107-126. | MR 1675486 | Zbl 0926.74032

[18] C.C. Chams and G.P. Sendeckij, Critique on theories predicting thermoelastic properties of fibrous composites. J. Comput. Mat. 2 (1968) 332-358.

[19] W. E, B. Engquist, The heterogeneous multiscale methods. Commun. Math. Sci. 1 (2003) 87-132. | MR 1979846 | Zbl 1093.35012

[20] Weinan E, P. Ming and P. Zhang, Analysis of the heterogeneous multiscale method for elliptic homogenization problems. J. Amer. Math. Soc. 18 (2005) 121-156. | MR 2114818 | Zbl 1060.65118

[21] Y. Efendiev and T.Y. Hou, Multiscale Finite Element Methods. Springer (2009). | MR 2477579 | Zbl 1163.65080

[22] Y.R. Efendiev, T.Y. Hou and X.H. Wu, Convergence of a nonconforming mutiscale finite element method. SIAM J. Numer. Anal. 37 (2000) 888-910. | MR 1740386 | Zbl 0951.65105

[23] Y. Efendiev and T. Hou, Multiscale finite element methods for porous media flows and their applications. Appl. Numer. Math. 57 (2007) 577-596. | MR 2322432 | Zbl 1112.76046

[24] B. Engquist and P.E. Souganidis, Asymptotic and numerical homogenization. Acta Numer. 17 (2008) 147-190. | MR 2436011 | Zbl 1179.65142

[25] J. Fish and Z. Huan, Multiscale enrichment based on partition unity. Int. J. Num. Mech. Eng. 62 (2005) 1341-1359. | Zbl 1078.74637

[26] S.K. Garg, V. Svalbonas and G.A. Gurtman, Analysis of Structural Composite Materials. Marcel Dekker, New York (1973).

[27] L. Grasedyck, I. Greff and S. Sauter, The AL basis for the solution of elliptic problems in heterogeneous media. Multiscale Model. Simul. 10 (2012) 245-258. | MR 2902606 | Zbl 1250.65140

[28] L.J. Gurtman and R.H. Krock, Composite Materials, in vol II of Mechanics of composite materials, edited by G.P. Sendeckyj. Academic Press (1974).

[29] Z. Hashin, Theory of Fiber reinforced materials, NASA Report CR-1974 (1972) 1-704.

[30] T.Y. Hou and Xiao-Hui Wu, 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

[31] T.Y. Hou, Xiao-Hui Wu and Yu Zhang, Removing the cell resonance error in the multiscale finite element method via a Petrov-Galerkin formulation. Commun. Math. Sci. 2 (2004) 185-205. | MR 2119937 | Zbl 1085.65109

[32] T.J.R. Hughes, Multiscale phenomena: Green's functions, the Dirichlet-to-Neumann formulaion, subgrid scale models, bubbles and the origins of stabilized methods. Comput. Methods Appl. Mech. Engrg. 127 (1995) 387-401. | MR 1365381 | Zbl 0866.76044

[33] T.J.R. Hughes, G.R. Feijoo, L. Mazzei and J.B. Quincy, The variational multiscale method. A Paradigm for computational mechanics. Comput. Meth. Appl. Mech. Eng. 166 (1998) 3-24. | MR 1660141 | Zbl 1017.65525

[34] K. Lichtenecker, Die Electrizitatskonstante naturlicher und kustlicher Mischkorper. Phys. Zeitschr. XXVII (1926) 115-158. | JFM 52.0914.17

[35] A. Malquist, Multiscale methods for elliptic problems. Multiscale Model. Simul. 9 (2011) 1064-1086. | MR 2831590 | Zbl 1248.65124

[36] G.F. Masotti, Discussione analitica sul influenze che L'azione di mezo dialettrico hu sulla distribuziione dell' electtricita alla superficie di pin corpi ellecttici diseminati in esso. Mem.Di Math. et di Fisica in Modena 24 (1850) 49.

[37] G. Maxwell, Trestise on Electricity and Magnetisum, vol. 1. Oxford Univ. Press (1873) 62. | Zbl 1049.01021

[38] J. Melenk and I. Babuška, The Partion of Unity Method Basic Theory and Applications, Comput. Meth. Appl. Mech. Eng. 139 (1996) 289-314. | Zbl 0881.65099

[39] J.M. Melenk, On n-widths for elliptic problems. J. Math. Anal. Appl. 247 (2000) 272-289. | MR 1766938 | Zbl 0963.35047

[40] G.W. Milton. The Theory of Composites. Cambridge University Press, Cambridge (2002). | MR 1899805 | Zbl 0993.74002

[41] F. Murat, H-convergence, Séminaire d'Analyse Fonctionelle et Numérique de l'Université d'Alger, mimeographed notes, 1978. L. Tartar Cours Peccot, College de France (1977). Translated into English as F. Murat L. Tartar, H- convergence, in Topics in the Mathematical Modeling of Composite Materials, Progress in Nonlinear Differential Equations and their Applications, in vol. 31, edited by A.V. Cherkaev, R.V. Kohn. Birkhäuser, Boston (1997) 21-43. | Zbl 0920.35019

[42] J. Nolen, G. Papanicolaou and O. Pironneau, A framework for adaptive multiscale methods for elliptic problems. Multiscale Model. Simul. 7 (2008) 171-196. | MR 2399542 | Zbl 1160.65342

[43] H. Owhadi and L. Zhang, Metric-based upscaling. Commun. Pure Appl. Math. 60 (2007) 675-723. | MR 2292954 | Zbl 1190.35070

[44] H. Owhadi and L. Zhang, Localized bases for finite-dimensional homogenization approximations with nonseparated scales and high contrast. Multiscale Model. Simul. 9 (2011) 1373-1398. | MR 2861243 | Zbl 1244.65140

[45] A. Pinkus, n-Widths in Approximation Theory. Springer-Verlag, Berlin, Heidelberg, New York 7 (1985). | MR 774404 | Zbl 0551.41001

[46] S.D. Poisson, Second mem. sur la theorie de magnetism, Mem. de L Acad. de France (1822) 5.

[47] J.W. Rayleigh, On the influence of obstacles in rectangular order upon the properties of the medium. Philos. Mag. 50 (1892) 481. | JFM 24.1015.02

[48] E. Sanchez-Palencia. Non-Homogeneous Media and Vibration Theory, in vol. 127 of Lecture Notes in Physics. Springer-Verlag (1980). | MR 578345 | Zbl 0432.70002

[49] S. Spagnolo, Sul limite delle soluzioni di problemi di Cauchy relativi all'equazione del calore. Ann Scu. Norm. Pisa 21 (1967) 657-699. | Numdam | MR 225015 | Zbl 0153.42103

[50] S. Spagnolo, Sulla convergenza di soluzioni di equazioni paraboliche ed ellittiche. Ann. Sc. Norm. Sup. Pisa 22 (1968) 517-597. | Numdam | MR 240443 | Zbl 0174.42101

[51] S. Spagnolo, Convergence in Energy for Elliptic Operators, edited by B. Hubbard. Numer. Solutions Partial Differ Eqs. III, (Synspade 1975, College Park, Maryland 1975). Academic Press, New York (1975). | MR 477444 | Zbl 0347.65034

[52] W. Streider and R. Aris, Variational Methods Applied to Problems of Diffusion and Reaction, Springer Tracts in Natural Philosophy. Springer-Verlag (1973). | Zbl 0273.49067

[53] T. Strouboulis, L. Zhang and I Babuška, Generalized finite element method using mesh-based handbooks application to problem in domains with many voids. Comput. Methods Appl. Mechanics Engrg. 192 (2003) 3109-3161. | MR 2007029 | Zbl 1054.74059

[54] T. Strouboulis, I. Babuška and K. Copps, The design and analysis of the generalized finite element method. Comput. Methods Appl. Mech. Engrg. 181 (2001) 43-69. | MR 1734667 | Zbl 0983.65127

[55] T. Strouboulis, L. Zhang and I. Babuška, p-version of generalized FEM using mesh based handbooks with applications to multiscale problems. Int. J. Num. Meth. Engrg. 60 (2004) 1639-1672. | MR 2069141 | Zbl 1059.65106

[56] S. Torquato, Random Heterogeneous Materials, Microstructure and Macroscopic Properties. Springer, New York (2002). | MR 1862782 | Zbl 0988.74001