Machine Computation Using the Exponentially Convergent Multiscale Spectral Generalized Finite Element Method

Babuška, Ivo; Huang, Xu; Lipton, Robert

ESAIM: Mathematical Modelling and Numerical Analysis , Multiscale problems and techniques. Special Issue, Tome 48 (2014) no. 2, pp. 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.

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

[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 | Zbl

[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 | Zbl

[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

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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

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

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

[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

[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

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

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

[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

[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 | Zbl

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

[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 | Zbl

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

[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

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

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

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