Do you want to **read the rest** of this article?

# Residual-driven online Generalized Multiscale Finite Element Methods

**Article**

*in*Journal of Computational Physics 302 · January 2015

*with*42 Reads

**How we measure 'reads'**

A 'read' is counted each time someone views a publication summary (such as the title, abstract, and list of authors), clicks on a figure, or views or downloads the full-text. Learn more

DOI: 10.1016/j.jcp.2015.07.068 · Source: arXiv

Cite this publicationAbstract

The construction of local reduced-order models via multiscale basis functions
has been an area of active research. In this paper, we propose online
multiscale basis functions which are constructed using the offline space and
the current residual. Online multiscale basis functions are constructed
adaptively in some selected regions based on our error indicators. We derive an
error estimator which shows that one needs to have an offline space with
certain properties to guarantee that additional online multiscale basis
function will decrease the error. This error decrease is independent of
physical parameters, such as the contrast and multiple scales in the problem.
The offline spaces are constructed using Generalized Multiscale Finite Element
Methods (GMsFEM). We show that if one chooses a sufficient number of offline
basis functions, one can guarantee that additional online multiscale basis
functions will reduce the error independent of contrast. We note that the
construction of online basis functions is motivated by the fact that the
offline space construction does not take into account distant effects. Using
the residual information, we can incorporate the distant information provided
the offline approximation satisfies certain properties. In the paper,
theoretical and numerical results are presented. Our numerical results show
that if the offline space is sufficiently large (in terms of the dimension)
such that the coarse space contains all multiscale spectral basis functions
that correspond to small eigenvalues, then the error reduction by adding online
multiscale basis function is independent of the contrast. We discuss various
ways computing online multiscale basis functions which include a use of small
dimensional offline spaces.

- ... On the other hand, we remark that other adaptive methods are available [12, 13, 1, 27, 29, 31, 4]. Also, we remark that online basis functions within continuous Galerkin GMsFEM is studied in [8]. The rest of the paper is organized in the following way. ...... In particular, the convergence rate is affected by the quantity Λ min = min 1≤i≤Nc λ ωi Li+1 . The convergence is slow when Λ min is small (cf. [8, 24]). We also remark that one can add online basis functions in multiple coarse neighborhoods to speed up the convergence. ...... The construction of online basis functions for various applications and discretizations require a careful analysis. In particular, as we have shown earlier [8] for GMsFEM within continuous Galerkin framework that one needs a certain number of offline basis functions in order to guarantee that the online basis functions can result to a convergence independent of physical parameters. In this paper, we develop an online basis procedure for GMsDGM that can provide a convergence independent of the contrast and small scales. ...Offline computation is an essential component in most multiscale model reduction techniques. However, there are multiscale problems in which offline procedure is insufficient to give accurate representations of solutions, due to the fact that offline computations are typically performed locally and global information is missing in these offline information. To tackle this difficulty, we develop an online local adaptivity technique for local multiscale model reduction problems. We design new online basis functions within Discontinuous Galerkin method based on local residuals and some optimally estimates. The resulting basis functions are able to capture the solution efficiently and accurately, and are added to the approximation iteratively. Moreover, we show that the iterative procedure is convergent with a rate independent of physical scales if the initial space is chosen carefully. Our analysis also gives a guideline on how to choose the initial space. We present some numerical examples to show the performance of the proposed method.
- ... In the online stage, we add more online multiscale basis functions that are constructed using the offline space. These online basis functions are computed adaptively in some selected spatial regions based on the current local residuals and their construction is motivated by the analysis in [10]. In general, the algorithm can guarantee that additional online multiscale basis functions will reduce the error rapidly if one chooses a sufficient number of offline basis functions. ...... Suppose that one needs to add an online basis φ into the space V i . The analysis in [10] suggests that the required online basis φ ∈ V i is the solution to the following equation ...... After that, solve (17) in V n,τ +1 off to get u n,τ +1 off . Consequently, following the arguments in [10], we have at time t = t n , ...Preprint
- Dec 2018

In this paper, we propose a dynamically low-dimensional approximation method to solve a class of time-dependent multiscale stochastic diffusion equations. A dynamically bi-orthogonal (DyBO) method was developed to explore low-dimensional structures of stochastic partial differential equations (SPDEs) and solve them efficiently. However, when the SPDEs have multiscale features in physical space, the original DyBO method becomes expensive. To address this issue, we construct multiscale basis functions within each coarse grid block for dimension reduction in the physical space. To further improve the accuracy, we also perform online procedure to construct online adaptive basis functions. In the stochastic space, we use the generalized polynomial chaos (gPC) basis functions to represent the stochastic part of the solutions. Numerical results are presented to demonstrate the efficiency of the proposed method in solving time-dependent PDEs with multiscale and random features. - ... As an interesting case of the considered nonlinear poroelasticity, a static strain-limiting nonlinear elasticity model (as in [18]) is also investigated by similar strategy and via the CEM-GMsFEM. To take into consideration the influence of source and global information, as in the linear elasticity case ( [19]), we use more efficient residual based online basis functions (via adaptive enrichment procedure [10]), which are not used in the poroelasticity case (where only offline multiscale basis functions are applied). The online basis of the CEM-GMsFEM [12] will be computed in an oversampled domain, which is different from the original online approach [10]. ...... To take into consideration the influence of source and global information, as in the linear elasticity case ( [19]), we use more efficient residual based online basis functions (via adaptive enrichment procedure [10]), which are not used in the poroelasticity case (where only offline multiscale basis functions are applied). The online basis of the CEM-GMsFEM [12] will be computed in an oversampled domain, which is different from the original online approach [10]. We will also provide a proof of global convergence of the Picard iteration procedure in Appendix A. ...... General idea of the CEM-GMsFEM for nonlinear poroelasticity. For details of the GMsFEM and CEM-GMsFEM, we refer the readers to [18,15,16,13,10,9] and [11,12], respectively. In this paper, we follow the procedure in Section 3, provided (u s,ms , p s,ms ) in the multiscale space V ms × Q ms (⊂ V × Q) (to be discussed later). ...Preprint
- Sep 2019

In this paper, we apply the constraint energy minimizing generalized multiscale finite element method (CEM-GMsFEM) to first solving a nonlinear poroelasticity problem. The arising system consists of a nonlinear pressure equation and a nonlinear stress equation in strain-limiting setting, where strains keep bounded while stresses can grow arbitrarily large. After time discretization of the system, to tackle the nonlinearity, we linearize the resulting equations by Picard iteration. To handle the linearized equations, we employ the CEM-GMsFEM and obtain appropriate offline multiscale basis functions for the pressure and the displacement. More specifically, first, auxiliary multiscale basis functions are generated by solving local spectral problems, via the GMsFEM. Then, multiscale spaces are constructed in oversampled regions, by solving a constraint energy minimizing (CEM) problem. After that, this strategy (with the CEM-GMsFEM) is also applied to a static case of the above nonlinear poroelasticity problem, that is, elasticity problem, where the residual based online multiscale basis functions are generated by an adaptive enrichment procedure, to further reduce the error. Convergence of the two cases is demonstrated by several numerical simulations, which give accurate solutions, with converging coarse-mesh sizes as well as few basis functions (degrees of freedom) and oversampling layers. - ... One can use local oversampling techniques [22]; however, the global effects are still not used. One can accelerate the convergence by computing multiscale basis functions using a residual at the online stage [16,11,39]. This is done by designing new multiscale basis functions, which solve local problems using the global residual information. ...... Now, we present the general idea of GMsFEM [21,30,16]. We divide the computations into offline and online stages. ...... By the offline computation, we construct multiscale basis functions that can be used for any input parameters to solve the problem on the coarse grid. In the earlier works [15,16], the online method for the diffusion equation with heterogeneous coefficients has been proposed. In this section, we consider the construction of the online basis functions for elasticity problem in perforated domains and present an adaptive enrichment algorithm. ...In this paper, we develop and analyze an adaptive multiscale approach for heterogeneous problems in perforated domains. In many applications, these problems have a multiscale nature arising because of the perforations, their geometries, the sizes of the perforations, and configurations. In this paper, we present a general offline/online procedure, which can adequately and adaptively represent the local degrees of freedom and derive appropriate coarse-grid equations. The main contributions of this paper are (1) the rigorous analysis of the offline approach (2) the development of the online procedures and their analysis (3) the development of adaptive strategies. We present an online procedure, which allows adaptively incorporating global information and is important for a fast convergence when combined with the adaptivity. Our methodology allows adding and guides constructing new online multiscale basis functions adaptively in appropriate regions. We present the convergence analysis of the online adaptive enrichment algorithm for the Stokes system. In particular, we show that the online procedure has a rapid convergence with a rate related to the number of offline basis functions, and one can obtain fast convergence by a sufficient number of offline basis functions, which are computed in the offline stage. To illustrate the performance of our method, we present numerical results with both small and large perforations. We see that only a few (1 or 2) online iterations can significantly improve the offline solution.
- ... Then we iteratively compute basis functions based on the previous solution in the online stage, thus we call it an online method. The method in this paper is an extension of the online Generalized Multiscale Finite Element Methods (GMsFEM)[10,7,11]to the mortar mixed case. Mortar mixed finite element methods[19,2]are a modification of mixed finite element methods by introducing a Lagrange multiplier to impose the continuity of flux. ...... Online basis functions developed in this paper are able to keep global information of complicated media, and we can use multiple online basis functions to compute the velocity for the transport equation. Residual driven GMsFEM is an iterative algorithm that drives coarse-grid solutions converging to the fine-grid solutions, see[10,7,11]for the case of finite element coupling method. The algorithm essentially includes the following steps: (1) compute an initial coarse grid solution with offline basis which can be polynomials or multiscale basis functions, (2) for each edge-wised coarse neighborhood, compute online basis by solving a homogeneous Dirichlet problem with local residual as source, (3) compute new solution with updated basis space and then return to step (2) until a residual is less than the use-defined threshold. ...... Then we iteratively compute basis functions based on the previous solution in the online stage, thus we call it an online method. The method in this paper is an extension of the online Generalized Multiscale Finite Element Methods (GMsFEM) [10,7,11] to the mortar mixed case. Mortar mixed finite element methods [19,2] are a modification of mixed finite element methods by introducing a Lagrange multiplier to impose the continuity of flux. ...In this paper, we develop an online basis enrichment method with the mortar mixed finite element method, using the oversampling technique, to solve for flow problems in highly heterogeneous media. We first compute a coarse grid solution with a certain number of offline basis functions per edge, which are chosen as standard polynomials basis functions. We then iteratively enrich the multiscale solution space with online multiscale basis functions computed by using residuals. The iterative solution converges to the fine scale solution rapidly. We also propose an oversampling online method to achieve faster convergence speed. The oversampling refers to using larger local regions in computing the online multiscale basis functions. We present extensive numerical experiments(including both 2D and 3D) to demonstrate the performance of our methods for both steady state flow, and two-phase flow and transport problems. In particular, for the time dependent two-phase flow and transport problems, we apply the online method to the initial model, without updating basis along the time evolution. Our numerical results demonstrate that by using a few number of online basis functions, one can achieve a fast convergence.
- ... This slow down is due to some slow decay after certain eigenvalue. To improve this, in[3,6,1,5], the authors propose an online approach. The main idea of online approaches is to add multiscale basis functions using the residual information after computing the coarse-grid solution. ...... They are solutions of local problems. Our analysis in[3,6]shows that the error decay is proportional to 1 − CΛ, where C is the constant (independent of scales and contrast) that guarantees the positivity of this quantity. This indicates that the error is not reduced unless Λ is sufficiently away from 0, i.e., we have suffcient number of offline basis functions. ...... This indicates that the error is not reduced unless Λ is sufficiently away from 0, i.e., we have suffcient number of offline basis functions. This was demonstrated analytically and numerically in our papers[3,6]. Since the online procedure can be costly, our goal is to perform only 1-2 iterations. ...Article
- Jun 2017
- J COMPUT PHYS

Local multiscale methods often construct multiscale basis functions in the offline stage without taking into account input parameters, such as source terms, boundary conditions, and so on. These basis functions are then used in the online stage with a specific input parameter to solve the global problem at a reduced computational cost. Recently, online approaches have been introduced, where multiscale basis functions are adaptively constructed in some regions to reduce the error significantly. In multiscale methods, it is desired to have only 1-2 iterations to reduce the error to a desired threshold. Using Generalized Multiscale Finite Element Framework, it was shown that by choosing sufficient number of offline basis functions, the error reduction can be made independent of physical parameters, such as scales and contrast. In this paper, our goal is to improve this. Using our recently proposed approach and special online basis construction in oversampled regions, we show that the error reduction can be made sufficiently large by appropriately selecting oversampling regions. Our numerical results show that one can achieve a three order of magnitude error reduction, which is better than our previous methods. We also develop an adaptive algorithm and enrich in selected regions with large residuals. In our adaptive method, we show that the convergence rate can be determined by a user-defined parameter and we confirm this by numerical simulations. The analysis of the method is presented. - ... On the other hand, for some applications it can be beneficial to adaptively construct new online basis functions during the course of the adaptive algorithm to capture distant effects. In [8], such online adaptivity is proposed and mathematically analyzed. More precisely, when the local residual related to some coarse neighborhood ω i is large, one may construct a new basis function φ i ∈ V i in the online stage by solving ...... For analytical convergence of the method we rely on the pre-computed basis functions from V off satisfying the online error reduction property (ONERP) (see [8], and Section 3.2, below), meaning sufficiently many offline basis functions are used in the approxima- tion. Then, the addition of the constructed online basis functions yields provable error reduction, at a guaranteed rate. ...... Then, the addition of the constructed online basis functions yields provable error reduction, at a guaranteed rate. As in [8], the ONERP is required in order to archive rapid analytical and numerical convergence independent of the contrast in the permeability field for general quantities of interest. While our numerical results indicate fast convergence for certain (highly localized) quantities of interest may occur even without this property, the convergence is not robust with respect to the contrast without the satisfaction of the ONERP. ...Preprint
- Dec 2018

In this research, we develop an online enrichment framework for goal-oriented adaptivity within the generalized multiscale finite element method for flow problems in heterogeneous media. The method for approximating the quantity of interest involves construction of residual-based primal and dual basis functions used to enrich the multiscale space at each stage of the adaptive algorithm. Three different online enrichment strategies based on the primal-dual online basis construction are proposed: standard, primal-dual combined and primal-dual product based. Numerical experiments are performed to illustrate the efficiency of the proposed methods for high-contrast heterogeneous problems. - ... Here, our paper will combine the ideas of Picard iteration and the GMsFEM in [9] to solve a strain-limiting nonlinear elasticity problem [21,20]. At each Picard iteration, we will either apply the offline GMsFEM or the residual based online adaptive GMsFEM. ...... At each Picard iteration, we will either apply the offline GMsFEM or the residual based online adaptive GMsFEM. In the latter approach, we study the proposed online basis construction in conjunction with adaptivity ( [7,9,12]), which means that online basis functions are added in some selected regions. Adaptivity is an important step to obtain an effective local multiscale model reduction as it is crucial to reduce the cost of online multiscale basis computations. ...... General idea of GMsFEM. For details of GMsFEM, we refer the readers to [16,12,9,5]. In this paper, at the current n-th Picard iteration, we will consider the continuous Galerkin (CG) formulation, having a similar form to the fine-scale problem (4.1). ...Preprint
- Dec 2018

In this paper, we consider multiscale methods for nonlinear elasticity. In particular, we investigate the Generalized Multiscale Finite Element Method (GMsFEM) for a strain-limiting elasticity problem. Being a special case of the naturally implicit constitutive theory of nonlinear elasticity, strain-limiting relation has presented an interesting class of material bodies, for which strains remain bounded (even infinitesimal) while stresses can become arbitrarily large. The nonlinearity and material heterogeneities can create multiscale features in the solution, and multiscale methods are therefore necessary. To handle the resulting nonlinear monotone quasilinear elliptic equation, we use linearization based on the Picard iteration. We consider two types of basis functions, offline and online basis functions, following the general framework of GMsFEM. The offline basis functions depend nonlinearly on the solution. Thus, we design an indicator function and we will recompute the offline basis functions when the indicator function predicts that the material property has significant change during the iterations. On the other hand, we will use the residual based online basis functions to reduce the error substantially when updating basis functions is necessary. Our numerical results show that the above combination of offline and online basis functions is able to give accurate solutions with only a few basis functions per each coarse region and updating basis functions in selected iterations. - ... To reduce the computational cost associated with constructing the snapshot space, we follow [5] and use randomized boundary conditions. One of other novel components of the paper is the use of online basis functions (see [8] for online basis functions for steady state problems) for the time-dependent nonlinear problems. The online basis functions are constructed during the simulation using the residual and they can reduce the error significantly. ...... After that we can solve our problem in the constructed offline space. Moreover, we will construct online basis functions that are problem dependent and are computed locally based on some local residuals [9, 8]. We now present the construction of the offline basis functions and the corresponding spectral problems for obtaining a space reduction. ...... In this section, we consider the construction of the online basis functions that are used in some regions adaptively to reduce the error significantly. We follow earlier works [9, 8] , which were done for linear timeindependent problems. The online basis functions are constructed based on a residual and take into account distant effects. ...In this paper, we develop a multiscale model reduction technique that describes shale gas transport in fractured media. Due to the pore-scale heterogeneities and processes, we use upscaled models to describe the matrix. We follow our previous work \cite{aes14}, where we derived an upscaled model in the form of generalized nonlinear diffusion model to describe the effects of kerogen. To model the interaction between the matrix and the fractures, we use Generalized Multiscale Finite Element Method. In this approach, the matrix and the fracture interaction is modeled via local multiscale basis functions. We developed the GMsFEM and applied for linear flows with horizontal or vertical fracture orientations on a Cartesian fine grid. In this paper, we consider arbitrary fracture orientations and use triangular fine grid and developed GMsFEM for nonlinear flows. Moreover, we develop online basis function strategies to adaptively improve the convergence. The number of multiscale basis functions in each coarse region represents the degrees of freedom needed to achieve a certain error threshold. Our approach is adaptive in a sense that the multiscale basis functions can be added in the regions of interest. Numerical results for two-dimensional problem are presented to demonstrate the efficiency of proposed approach.
- ... The online basis functions are adaptively constructed using the residual information to improve the convergence. In [8], this algorithm is discussed for deterministic problems. The extension of this approach to stochastic problems will be discussed in this paper. ...... By adding the online basis functions adaptively, we can decrease the error significantly at a cost of reformulating the coarse-grid problem. We believe the accuracy of the online method depends on the offline spaces as in [8]. ...Article
- Nov 2017
- J COMPUT PHYS

We propose a generalized multiscale finite element method (GMsFEM) based on clustering algorithm to study the elliptic PDEs with random coefficients in the multi-query setting. Our method consists of offline and online stages. In the offline stage, we construct a small number of reduced basis functions within each coarse grid block, which can then be used to approximate the multiscale finite element basis functions. In addition, we coarsen the corresponding random space through a clustering algorithm. In the online stage, we can obtain the multiscale finite element basis very efficiently on a coarse grid by using the pre-computed multiscale basis. The new GMsFEM can be applied to multiscale SPDE starting with a relatively coarse grid, without requiring the coarsest grid to resolve the smallest-scale of the solution. The new method offers considerable savings in solving multiscale SPDEs. Numerical results are presented to demonstrate the accuracy and efficiency of the proposed method for several multiscale stochastic problems without scale separation. - ... Our approach starts with the GMsFEM framework. The GMsFEM was first intro- duced in [18] and further studied in [31,32,19,20,7,14,15,13,12,10]. It is a gener- alization of MsFEM and yields numerical macroscopic equations for problems without scale separation. ...... In this section, we will discuss the problem settings and the key ingredients of Gen- eralized Multiscale Finite Element Methods (GMsFEM) [18,31,32,19,20,7,14,15,13,12,10]. Several approaches for multiscale model reduction by GMsFEM have been proposed for parabolic equation, and we present a unified discussion of GMsFEM in this section. ...Preprint
- Jun 2018

In this paper, we propose a Bayesian approach for multiscale problems with the availability of dynamic observational data. Our method selects important degrees of freedom probabilistically in a Generalized multiscale finite element method framework. Due to scale disparity in many multiscale applications, computational models can not resolve all scales. Dominant modes in the Generalized Multiscale Finite Element Method are used as "permanent" basis functions, which we use to compute an inexpensive multiscale solution and the associated uncertainties. Through our Bayesian framework, we can model approximate solutions by selecting the unresolved scales probabilistically. We consider parabolic equations in heterogeneous media. The temporal domain is partitioned into subintervals. Using residual information and given dynamic data, we design appropriate prior distribution for modeling missing subgrid information. The likelihood is designed to minimize the residual in the underlying PDE problem and the mismatch of observational data. Using the resultant posterior distribution, the sampling process identifies important degrees of freedom beyond permanent basis functions. The method adds important degrees of freedom in resolving subgrid information and ensuring the accuracy of the observations. - ... In the online stage, online basis functions are constructed based on the parameters. However, as pointed out in [9,6,10], there are multiscale problems in which an offline process fails to yield an accurate representations of solutions. The reason for this is that offline computations are carried out locally. ...... In [11], an adaptive algorithm is proposed to enrich the solution space by adding basis functions which are precomputed in the offline stage. In [9], adaptive methods in the continuous Galerkin framework, using the residuals of the previous solutions to form new online basis functions are discussed. Results show that these methods accelerate the convergence rate of GMsFEM significantly. ...PreprintFull-text available
- Jul 2018

In this paper, we consider an online basis enrichment mixed generalized multiscale method with oversampling, for solving flow problems in highly heterogeneous porous media. This is an exten- sion of the online mixed generalized multiscale method [6]. The multiscale online basis functions are computed by solving a Neumann problem in an over-sampled domain, instead of a standard neighborhood of a coarse face. We are motivated by the restricted domain decomposition method. Extensive numerical experiments are presented to demonstrate the performance of our methods for both steady-state flow, and two-phase flow and transport problems. - ... A main difficulty of model order reduction is nonlinear problems. In such problems, modes have to be re-trained or computed in an online process [12,1,6], which is, in many cases, computationally expensive. Moreover, in cases with observed data, the off-line computed modes may not honor the data. ...... In our paper, our main goal was to incorporate the observed data into the dynamical system and modify reduced-order models to take into account the observed data. We have also used deep learning techniques to predict online basis functions [12,1,6], which allow re-constructing the fine-scale solution. ...PreprintFull-text available
- Jul 2018

In this paper, we combine deep learning concepts and some proper orthogonal decomposition (POD) model reduction methods for predicting flow in heterogeneous porous media. Nonlinear flow dynamics is studied, where the dynamics is regarded as a multi-layer network. The solution at the current time step is regarded as a multi-layer network of the solution at the initial time and input parameters. As for input, we consider various sources, which include source terms (well rates), permeability fields, and initial conditions. We consider the flow dynamics, where the solution is known at some locations and the data is integrated to the flow dynamics by modifying the reduced-order model. This approach allows modifying the reduced-order formulation of the problem. Because of the small problem size, limited observed data can be handled. We consider enriching the observed data using the computational data in deep learning networks. The basis functions of the global reduced order model are selected such that the degrees of freedom represent the solution at observation points. This way, we can avoid learning basis functions, which can also be done using neural networks. We present numerical results, where we consider channelized permeability fields, where the network is constructed for various channel configurations. Our numerical results show that one can achieve a good approximation using forward feed maps based on multi-layer networks. - ... In nonlinear problems, one performs local nonlinear interpolation to approximate the Jacobian or other nonlinear terms. The above multiscale procedure can be complemented with online basis functions which helps to converge to the fine-scale solution by constructing multiscale basis functions in the simulations [23, 24] (also, see Figure 2for the ingredients of proposed multiscale method). Limitations. ...... In addition, the residual norm R i V * i provides a measure on the amount of reduction in energy error. In [23, 24], we have studied the convergence of the above online adaptive procedure. To simplify notations, we write ...Article
- Apr 2016
- J COMPUT PHYS

In this paper, we discuss a general multiscale model reduction framework based on multiscale finite element methods. We give a brief overview of related multiscale methods. Due to page limitations, the overview focuses on a few related methods and is not intended to be comprehensive. We present a general adaptive multiscale model reduction framework, the Generalized Multiscale Finite Element Method. Besides the method's basic outline, we discuss some important ingredients needed for the method's success. We also discuss several applications. The proposed method allows performing local model reduction in the presence of high contrast and no scale separation. - ... GMsFEM uses local eigenproblems and a parti- tion of unity for basis generation. Adaptive enrichment for the GMsFEM is presented by Chung et al. in [14, 12] and online-adaptive enrichment in [13]. While an application of the GMsFEM to the problem of arbitrary local modifications would be very interesting, GMsFEM was not designed to be communication avoiding. ...... While an application of the GMsFEM to the problem of arbitrary local modifications would be very interesting, GMsFEM was not designed to be communication avoiding. A parallel implementation of the enrichment described in [13] would require the communication of high dimensional basis representations, which is avoided in ArbiLoMod. ...Finite Element based simulation software is often used in engineering workflows to design structures whose behavior can be modeled by partial differential equations. Engineers manually optimizing a structure using simulation software often employ an iterative approach where in each iteration they change the structure slightly and resimulate. Standard Finite Element based simulation software is usually not well suited for this workflow, as it restarts in each iteration, even for tiny changes. In this paper, we introduce ArbiLoMod, a method designed for improving this manual, iterative workflow. It allows fast recomputation after arbitrary local modifications. It employs a domain decomposition and a localized form of the Reduced Basis Method for model order reduction. It assumes that the reduced basis on many of the unchanged domains can be reused after a localized change. The reduced model is adapted when necessary, steered by a localized error indicator. The global error introduced by the model order reduction is controlled by a rigorous a posteriori error estimator, certifying the quality of the result. As ArbiLoMod is based on the Reduced Basis Method, it inherits its advantages for parameterized problems. We demonstrate ArbiLoMod for a coercive, parameterized example with changing structure.
- ... We plan to address these application problems in our future works. Computations of multiscale basis functions for the time-dependent velocity field can be performed offline [16,34] or using the residuals in the online stage [12,13]. For the offline computations, one needs a richer class of snapshot vectors, which can span possible velocity fields and perform the same local spectral decompositions and global coupling framework, as we discussed above. ...... All these approaches can be used adaptively in space and time. Finally, one can use residual-based online basis functions [12,13], where one additional multiscale basis function is computed adaptively using the residual information. The success of these approaches depends on the offline space as it is shown, thus a good offline space is needed to achieve a high accuracy. ...ArticleFull-text available
- Dec 2015

In this paper, we develop a mass conservative multiscale method for coupled flow and transport in heterogeneous porous media. We consider a coupled system consisting of a convection-dominated transport equation and a flow equation. We construct a coarse grid solver based on the Generalized Multiscale Finite Element Method (GMsFEM) for a coupled system. In particular, multiscale basis functions are constructed based on some snapshot spaces for the pressure and the concentration equations and some local spectral decompositions in the snapshot spaces. The resulting approach uses a few multiscale basis functions in each coarse block (for both the pressure and the concentration) to solve the coupled system. We use the mixed framework, which allows mass conservation. Our main contributions are: (1) the development of a mass conservative GMsFEM for the coupled flow and transport; (2) the development of a robust multiscale method for convection-dominated transport problems by choosing appropriate test and trial spaces within Petrov-Galerkin mixed formulation. We present numerical results and consider several heterogeneous permeability fields. Our numerical results show that with only a few basis functions per coarse block, we can achieve a good approximation. - ... This is due to some slow decay after certain eigenvalues. To improve the convergency, the researchers in [9,11,12] propose online construction for the multiscale basis functions. In the online stage of the simulation, one may construct new basis functions with local support, using the residual once a coarse-grid approximation is computed. ...... In the online stage of the simulation, one may construct new basis functions with local support, using the residual once a coarse-grid approximation is computed. The analysis in [11,12] shows that the error decay is proportional to 1 − CΛ, where C is a constant independent of scales and contrast and guarantees the positivity of the convergence rate. ...Preprint
- Oct 2018

In this paper, an online basis construction for constraint energy minimizing generalized multiscale finite element method (CEM-GMsFEM) in mixed formulation is proposed. The online approach is based on the strategy of oversampling and makes use of the information of residual and the parameters in the partial differential equation such as the source function. The analysis presented shows that the error reduction can be made sufficiently large by suitably selecting oversampling regions and the number of oversampling layers. We show that the convergence rate is also determined by a user-defined parameter. Numerical results are provided to illustrate the efficiency of the proposed method. - ... On the other hand, for some applications one needs to adaptively construct new basis functions in the online stage in order to capture distant effects. In [15], such online adaptivity is proposed and mathematically analyzed. More precisely, when the local residual r i is large, one can construct a new basis function φ ∈ V 0 (ω i ) in the online stage by solving ...... where V 0 (ω i ) is the restriction of V in ω i with zero trace on ∂ω i . Numerical results in [15] show that a couple of these online basis functions can help to reduce the error by a large amount. The adaptivity procedures discussed above are designed with the aim of reducing the error in the energy norm. ...Article
- Sep 2015
- J COMPUT APPL MATH

In this paper we develop two goal-oriented adaptive strategies for a posteriori error estimation within the generalized multiscale finite element framework. In this methodology, one seeks to determine the number of multiscale basis functions adaptively for each coarse region to efficiently reduce the error in the goal functional. Our first error estimator uses a residual based strategy where local indicators on each coarse neighborhood are the product of local indicators for the primal and dual problems, respectively. In the second approach, viewed as the multiscale extension of the dual weighted residual method (DWR), the error indicators are computed as the pairing of the local H^{-1} residual of the primal problem weighed by a projection into the primal space of the H_0^1 dual solution from an enriched space, over each coarse neighborhood. In both of these strategies, the goal-oriented indicators are then used in place of a standard residual-based indicator to mark coarse neighborhoods of the mesh for further enrichment in the form of additional multiscale basis functions. The method is demonstrated on high-contrast problems with heterogeneous multiscale coefficients, and is seen to outperform the standard residual based strategy with respect to efficient reduction of error in the goal function. - ... To incorporate the influence of source and global media information, we also propose the construction of online multiscale basis. The idea of online approach was first proposed in [6] and has been extended to various other cases (see [7,3,21]). The key idea is using the residual information of the coarse-grid solution to construct multiscale basis. ...... These online multiscale basis functions can also be computed adaptively so that the error can be decreased the most. The online basis of CEM-GMsFEM [10] will be computed in a oversampled domain, which is different from the original online approach [6]. We test our methods on 2D and 3D media with channels and inclusions. ...Preprint
- Sep 2018

In this paper, we consider the offline and online Constraint Energy Minimizing Generalized Mul- tiscale Finite Element Method (CEM-GMsFEM) for high-contrast linear elasticity problem. Offline basis construction starts with an auxiliary multiscale space by solving local spectral problems. We select eigenfunctions that correspond to a few small eigenvalues to form the auxiliary space. Using the auxiliary space, we solve a constraint energy minimization problem to construct offline multiscale spaces. The minimization problem is defined in the oversampling domain, which is larger than the target coarse block. To get a good approximation space, the oversampling domain should be large enough. We also propose a relaxed minimization problem to construct multiscale basis functions, which will yield more accurate and robust solution. To take into account the influence of input pa- rameters, such as source terms, we propose the construction of online multiscale basis and an adaptive enrichment algorithm. We provide extensive numerical experiments on 2D and 3D models to show the performance of the proposed method. - ... As we observe in the previous examples, the offline errors do not decrease rapidly after several multiscale functions are selected. In these cases, online basis functions can help to reduce the error and obtain an accurate approximation of the fine-scale solution [11]. The use of online basis functions gives a rapid convergence. ...Article
- May 2016

In this paper, we consider local multiscale model reduction for problems with multiple scales in space and time. We developed our approaches within the framework of the Generalized Multiscale Finite Element Method (GMsFEM) using space-time coarse cells. The main idea of GMsFEM is to construct a local snapshot space and a local spectral decomposition in the snapshot space. Previous research in developing multiscale spaces within GMsFEM focused on constructing multiscale spaces and relevant ingredients in space only. In this paper, our main objective is to develop a multiscale model reduction framework within GMsFEM that uses space-time coarse cells. We construct space-time snapshot and offline spaces. We compute these snapshot solutions by solving local problems. A complete snapshot space will use all possible boundary conditions; however, this can be very expensive. We propose using randomized boundary conditions and oversampling. We construct the local spectral decomposition based on our analysis, as presented in the paper. We present numerical results to confirm our theoretical findings and to show that using our proposed approaches, we can obtain an accurate solution with low dimensional coarse spaces. We remark that the proposed method is a significant extension compared to existing methods, which use coarse cells in space only because of (1) the parabolic nature of cell solutions, (2) extra degrees of freedom associated with space-time cells, and (3) local boundary conditions in space-time cells. - ... In the online stage, when a given source term or boundary condition is given, the above offline basis functions are used to obtain an approximate solution. One can also adaptively select the basis functions in various coarse elements in order to obtain better efficiency and accuracy [16, 15]. The purpose of this paper is to develop a new GMsFEM for the wave equation. ...Article
- Sep 2015
- J COMPUT APPL MATH

Numerical simulations of waves in highly heterogeneous media have important applications, but direct computations are prohibitively expensive. In this paper, we develop a new generalized multiscale finite element method with the aim of simulating waves at a much lower cost. Our method is based on a mixed Galerkin type method with carefully designed basis functions that can capture various scales in the solution. The basis functions are constructed based on some local snapshot spaces and local spectral problems defined on them. The spectral problems give a natural ordering of the basis functions in the snapshot space and allow systematically enrichment of basis functions. In addition, by using a staggered coarse mesh, our method is energy conserving and has block diagonal mass matrix, which are desirable properties for wave propagation. We will prove that our method has spectral convergence, and present numerical results to show the performance of the method. - ... In [14], an adaptive algorithm is developed to enrich the space by adding basis functions which are formed in the offline stage. In [13], adaptive methods which involve the formation of new online basis functions based on the previous solution are developed. These methods show significant acceleration in the convergence rate of GMsFEM. ...In this paper, we present two adaptive methods for the basis enrichment of the mixed Generalized Multiscale Finite Element Method (GMsFEM) for solving the flow problem in heterogeneous media. We develop an a-posteriori error indicator which depends on the norm of a local residual operator. Based on this indicator, we construct an offline adaptive method to increase the number of basis functions locally in coarse regions with large local residuals. We also develop an online adaptive method which iteratively enriches the function space by adding new functions computed based on the residual of the previous solution and special minimum energy snapshots. We show theoretically and numerically the convergence of the two methods. The online method is, in general, better than the offline method as the online method is able to capture distant effects (at a cost of online computations), and both methods have faster convergence than a uniform enrichment. Analysis shows that the online method should start with certain number of initial basis functions in order to have the best performance. The numerical results confirm this and show further that with correct selection of initial basis functions, the convergence of the online method can be independent of the contrast of the medium. We consider cases with both very high and very low conducting inclusions and channels in our numerical experiments.
- ... Notice that the above adaptive process can be easily generalized to the multi-level case. Finally, we remark that one can also consider the goal-oriented adaptivity [12] or the residual-driven online adaptivity [10]. ...ArticleFull-text available
- Jun 2016

Numerical homogenization and multiscale finite element methods construct effective properties on a coarse grid by solving local problems and extracting the average effective properties from these local solutions. In some cases, the solutions of local problems can be expensive to compute due to scale disparity. In this setting, one can basically apply a homogenization or multiscale method re-iteratively to solve for the local problems. This process is known as re-iterated homogenization and has many variations in the numerical context. Though the process seems to be a straightforward extension of two-level process, it requires some careful implementation and the concept development for problems without scale separation and high contrast. In this paper, we consider the Generalized Multiscale Finite Element Method (GMsFEM) and apply it iteratively to construct its multiscale basis functions. The main idea of the GMsFEM is to construct snapshot functions and then extract multiscale basis functions (called offline space) using local spectral decompositions in the snapshot spaces. The extension of this construction to several levels uses snapshots and offline spaces interchangebly to achieve this goal. At each coarse-grid scale, we assume that the offline space is a good approximation of the solution and use all possible offline functions or randomization as boundary conditions and solve the local problems in the offline space at the previous (finer) level, to construct snapshot space. We present an adaptivity strategy and show numerical results for flows in heterogeneous media and in perforated domains. - ... Our approach starts with the Generalized Multiscale Finite Element framework. The GMsFEM was first presented in [29] and later investigated in several other papers (e.g., [30,31,32,33,34,35,36,37,38]). It is a gen- eralization of the MsFEM and defines appropriate local snapshots and local spectral decompositions. ...In this paper, we develop a Bayesian multiscale approach based on a multiscale finite element method. Because of scale disparity in many multiscale applications, computational models can not resolve all scales. Various subgrid models are proposed to represent un-resolved scales. Here, we consider a probabilistic approach for modeling un-resolved scales using the Multiscale Finite Element Method (cf., [1, 2]). By representing dominant modes using the Generalized Multiscale Finite Element, we propose a Bayesian framework, which provides multiple inexpensive (computable) solutions for a deterministic problem. These approximate probabilistic solutions may not be very close to the exact solutions and, thus, many realizations are needed. In this way, we obtain a rigorous probabilistic description of approximate solutions. In the paper, we consider parabolic and wave equations in heterogeneous media. In each time interval, the domain is divided into subregions. Using residual information, we design appropriate prior and posterior distributions. The likelihood consists of the residual minimization. To sample from the resulting posterior distribution, we consider several sampling strategies. The sampling involves identifying important regions and important degrees of freedom beyond permanent basis functions, which are used in residual computation. Numerical results are presented. We consider two sampling algorithms. The first algorithm uses sequential sampling and is inexpensive. In the second algorithm, we perform full sampling using the Gibbs sampling algorithm, which is more accurate compared to the sequential sampling. The main novel ingredients of our approach consist of: defining appropriate permanent basis functions and the corresponding residual; setting up a proper posterior distribution; and sampling the posteriors.
- ... In addition, we prove the convergence of this approach, and show that the convergence rate is independent of the heterogeneities of the coefficients. The last component is online adaptivity [10]. The goal of online basis functions is to capture some components, such as global feature, of the solution that are not representable by offline basis functions. ...Article
- Feb 2018
- J COMPUT APPL MATH

In this paper, we construct an adaptive multiscale method for solving H(curl)-elliptic problems in highly heterogeneous media. Our method is based on the generalized multiscale finite element method. We will first construct a suitable snapshot space, and a dimensional reduction procedure to identify important modes of the solution. We next develop and analyze an a posteriori error indicator, and the corresponding adaptive algorithm. In addition, we will construct a coupled offline-online adaptive algorithm, which provides an adaptive strategy to the selection of offline and online basis functions. Our theory shows that the convergence is robust with respect to the heterogeneities and contrast of the media. We present several numerical results to illustrate the performance of our method. - ... In this section, we consider the construction of the online basis functions ( [8,16,13]) for transport equation in perforated domains and present numerical results for different geometries. We use the index m ≥ 1 to represent the enrichment level. ...Convection-dominated transport phenomenon is important for many applications. In these applications, the transport velocity is often a solution of heterogeneous flow problems, which results to a coupled flow and transport phenomena. In this paper, we consider a coupled flow (Stokes problem) and transport (unsteady convection–diffusion problem) in perforated domains. Perforated domains (see Fig. 1) represent void space outside hard inclusions as in porous media, filters, and so on. We construct a coarse-scale solver based on Generalized Multiscale Finite Element Method (GMsFEM) for a coupled flow and transport. The main idea of the GMsFEM is to develop a systematic approach for computing multiscale basis functions. We use a mixed formulation and appropriate multiscale basis functions for both flow and transport to guarantee a mass conservation. For the transport problem, we use Petrov–Galerkin mixed formulation, which provides a stability. As a first approach, we use the multiscale flow solution in constructing the basis functions for the transport equation. In the second approach, we construct multiscale basis functions for coupled flow and transport without solving global flow problem. The novelty of this approach is to construct a coupled multiscale basis function. Numerical results are presented for computations using offline basis. We also present an algorithm for adaptively adding online multiscale basis functions, which are computed using the residual information. Numerical examples using online GMsFEM show the speed up of convergence.
- ... The main idea of GMsFEM is to extract local dominant modes by carefully designed local spectral problems in coarse regions, and the convergence of the GMsFEM is related to eigenvalue decay of local spectral problems. For a more detailed discussion on GMsFEM, we refer the readers to [21,18,20,15,11,8,25,6,36,38] and the references therein. Our method developed in this work is motivated by GMsFEM and achieves spectral convergence. ...Preprint
- Sep 2019

Numerical simulation of flow problems and wave propagation in heterogeneous media has important applications in many engineering areas. However, numerical solutions on the fine grid are often prohibitively expensive, and multiscale model reduction techniques are introduced to efficiently solve for an accurate approximation on the coarse grid. In this paper, we propose an energy minimization based multiscale model reduction approach in the discontinuous Galerkin discretization setting. The main idea of the method is to extract the non-decaying component in the high conductivity regions by identifying dominant modes with small eigenvalues of local spectral problems, and define multiscale basis functions in coarse oversampled regions by constraint energy minimization problems. The multiscale basis functions are in general discontinuous on the coarse grid and coupled by interior penalty discontinuous Galerkin formulation. The minimal degree of freedom in representing high-contrast features is achieved through the design of local spectral problems, which provides the most compressed local multiscale space. We analyze the method for solving Darcy flow problem and show that the convergence is linear in coarse mesh size and independent of the contrast, provided that the oversampling size is appropriately chosen. Numerical results are presented to show the performance of the method for simulation on flow problem and wave propagation in high-contrast heterogeneous media. - ... For coarse-scale coupling, we use discontinuous Galerkin method, that gives several advantages: (1) the construction of the multiscale basis functions can performed in non-overlapping local domains, (2) it avoids partition of unity functions, (2) as partitioning to the local do- mains we can use any shapes of the local domains. In general, we can improve the accuracy of our approach by using adaptivity and online techniques [39,40]. For the real world 3D problems, a high performance computations can be used, where construction of the coarse-scale system and local problem solutions can be carried out in parallel with very high efficiency of parallelization. ...In this work, we consider electrochemical processes for the pore-scale simulation of Lithium-ion batteries (LIBs). Mathematical model consists of the coupled system of the equations for the concentration and electric potential. We develop fine-scale approximation using discontinuous Galerkin approach, where interface condition is imposed weakly. We present novel multiscale model reduction technique based on the GMsFEM, where multiscale basis functions are constructed using information about variation of the medium at the micro level. We present numerical results for two cases of the boundary conditions and compare errors for different coarse grids for testing the proposed computational multiscale method. Numerical results show that the multiscale basis functions can efficiently capture the information of the fine-scale features of the medium with significant dimension reduction of the system and provide accurate solutions.
- ... Here we provide a brief introduction of the main ingredients of GMsFEM. For a more detailed discussion of GMsFEM and related concepts, the reader is referred to [22][23][24][25][26]. ...ArticleFull-text available
- May 2019

In this paper, we propose a deep-learning-based approach to a class of multiscale problems. The generalized multiscale finite element method (GMsFEM) has been proven successful as a model reduction technique of flow problems in heterogeneous and high-contrast porous media. The key ingredients of GMsFEM include mutlsicale basis functions and coarse-scale parameters, which are obtained from solving local problems in each coarse neighborhood. Given a fixed medium, these quantities are precomputed by solving local problems in an offline stage, and result in a reduced-order model. However, these quantities have to be re-computed in case of varying media (various permeability fields). The objective of our work is to use deep learning techniques to mimic the nonlinear relation between the permeability field and the GMsFEM discretizations, and use neural networks to perform fast computation of GMsFEM ingredients repeatedly for a class of media. We provide numerical experiments to investigate the predictive power of neural networks and the usefulness of the resultant multiscale model in solving channelized porous media flow problems. - ... The GMsFEM is a general multiscale procedure, in which the model reduction is based on some local multiscale basis functions. The basis functions are constructed using local spectral decomposition [25,24,15,10,27,9]. The main idea behind the construction of the multiscale space is to design appropriate snapshot spaces and determine an appropriate local spectral problem to select important modes in the snapshot space. ...Preprint
- May 2018

In this paper, we present an upscaling method for problems in perforated domains with non-homogeneous boundary conditions on perforations. Our methodology is based on the recently developed Non-local multicontinuum method (NLMC). The main ingredient of the method is the construction of suitable local basis functions with the capability of capturing multiscale features and non-local effects. We will construct multiscale basis functions for the coarse regions and additional multiscale basis functions for perforations, with the aim of handling non-homogeneous boundary conditions on perforations. We start with describing our method for the Laplace equation, and then extending the framework for the elasticity problem and parabolic equations. The resulting upscaled model has minimal size and the solution has physical meaning on the coarse grid. We will present numerical results (1) for steady and unsteady problems, (2) for Laplace and Elastic operators, and (3) for Neumann and Robin non-homogeneous boundary conditions on perforations. Numerical results show that the proposed method can provide good accuracy and provide significant reduction on the degrees of freedom. - ... Moreover, the resulting multiscale method obtained by a Galerkin formulation has a mesh dependent convergence rate. We remark that one can also perform adaptivity as in [12,9,11]. ...PreprintFull-text available
- Jul 2018

The dual continuum model serves as a powerful tool in the modeling of subsurface applications. It allows a systematic coupling of various components of the solutions. The system is of multiscale nature as it involves high heterogeneous and high contrast coefficients. To numerically compute the solutions, some types of reduced order methods are necessary. We will develop and analyze a novel multiscale method based on the recent advances in multiscale finite element methods. Our method will compute multiple local multiscale basis functions per coarse region. The idea is based on some local spectral problems, which are important to identify high contrast channels, and an energy minimization principle. Using these concepts, we show that the basis functions are localized, even in the presence of high contrast long channels and fractures. In addition, we show that the convergence of the method depends only on the coarse mesh size. Finally, we present several numerical tests to show the performance. - ... There are in literature a wide range of numerical schemes for this problem that are based on constructions of special basis functions on coarse grids [29,56,3,36,32,37,41,40,31,33,38,16,30,12,13,44,34]. These methods include the Multiscale Finite Element Methods (MsFEM) [36,32,37,38,43,2], the Variational Multiscale Methods [48,46,45,6,52,9,47,23,5,1,50] and the Generalized Multiscale Finite Element Method (GMsFEM) [32,42,43,34,35,10,21,17,11,22,19,20]. When the above approaches are used to solve multiscale convection-dominated diffusion problems with a high Peclet number, besides finding a reduced approximate solution space, one needs to stabilize the system to avoid large errors [55]. ...Preprint
- Jul 2018

We present a new stabilization technique for multiscale convection diffusion problems. Stabilization for these problems has been a challenging task, especially for the case with high Peclet numbers. Our method is based on a constraint energy minimization idea and the discontinuous Petrov-Galerkin formulation. In particular, the test functions are constructed by minimizing an appropriate energy subject to certain orthogonality conditions, and are related to the trial space. The resulting test functions have a localization property, and can therefore be computed locally. We will prove the stability, and present several numerical results. Our numerical results confirm that our test space gives a good stability, in the sense that the solution error is close to the best approximation error. - ... The constructed local snapshots contain the information about local heterogeneities. By performing local spectral decomposition, the method identifies multiscale basis functions corresponding to the dominant eigenvalues [33,32,31,18,22]. ...Inherently coupled flow and geomechanics processes in fractured shale media have implications for shale gas production. The system involves highly complex geo-textures comprised of a heterogeneous anisotropic fracture network spatially embedded in an ultra-tight matrix. In addition, nonlinearities due to viscous flow, diffusion, and desorption in the matrix and high velocity gas flow in the fractures complicates the transport. In this paper, we develop a multiscale model reduction approach to couple gas flow and geomechanics in fractured shale media. A Discrete Fracture Model (DFM) is used to treat the complex network of fractures on a fine grid. The coupled flow and geomechanics equations are solved using a fixed stress-splitting scheme by solving the pressure equation using a continuous Galerkin method and the displacement equation using an interior penalty discontinuous Galerkin method. We develop a coarse grid approximation and coupling using the Generalized Multiscale Finite Element Method (GMsFEM). GMsFEM constructs the multiscale basis functions in a systematic way to capture the fracture networks and their interactions with the shale matrix. Numerical results and an error analysis is provided showing that the proposed approach accurately captures the coupled process using a few multiscale basis functions, i.e. a small fraction of the degrees of freedom of the fine-scale problem.
- ... Here we provide a brief introduction of the main ingredients of GMsFEM. For a more detailed discussion of GMsFEM and related concepts, the reader is referred to [6,5,13,1,7]. ...PreprintFull-text available
- Oct 2018

In this paper, we propose a deep-learning-based approach to a class of multiscale problems. THe Generalized Multiscale Finite Element Method (GMsFEM) has been proven successful as a model reduction technique of flow problems in heterogeneous and high-contrast porous media. The key ingredients of GMsFEM include mutlsicale basis functions and coarse-scale parameters, which are obtained from solving local problems in each coarse neighborhood. Given a fixed medium, these quantities are precomputed by solving local problems in an offline stage, and result in a reduced-order model. However, these quantities have to be re-computed in case of varying media. The objective of our work is to make use of deep learning techniques to mimic the nonlinear relation between the permeability field and the GMsFEM discretizations, and use neural networks to perform fast computation of GMsFEM ingredients repeatedly for a class of media. We provide numerical experiments to investigate the predictive power of neural networks and the usefulness of the resultant multiscale model in solving channelized porous media flow problems. - Article
- Sep 2015
- COMPUT METHOD APPL M

We develop a Petrov-Galerkin stabilization method for multiscale convection-diffusion transport systems. Existing stabilization techniques add a limited number of degrees of freedom in the form of bubble functions or a modified diffusion, which may not sufficient to stabilize multiscale systems. We seek a local reduced-order model for this kind of multiscale transport problems and thus, develop a systematic approach for finding reduced-order approximations of the solution. We start from a Petrov-Galerkin framework using optimal weighting functions. We introduce an auxiliary variable to a mixed formulation of the problem. The auxiliary variable stands for the optimal weighting function. The problem reduces to finding a test space (a reduced dimensional space for this auxiliary variable), which guarantees that the error in the primal variable (representing the solution) is close to the projection error of the full solution on the reduced dimensional space that approximates the solution. To find the test space, we reformulate some recent mixed Generalized Multiscale Finite Element Methods. We introduce snapshots and local spectral problems that appropriately define local weight and trial spaces. In particular, we use energy minimizing snapshots and local spectral decompositions in the natural norm associated with the auxiliary variable. The resulting spectral decomposition adaptively identifies and builds the optimal multiscale space to stabilize the system. We discuss the stability and its relation to the approximation property of the test space. We design online basis functions, which accelerate convergence in the test space, and consequently, improve stability. We present several numerical examples and show that one needs a few test functions to achieve an error similar to the projection error in the primal variable irrespective of the Peclet number. - PreprintFull-text available
- Feb 2019

In this contribution we present a survey of concepts in localized model order reduction methods for parameterized partial differential equations. The key concept of localized model order reduction is to construct local reduced spaces that have only support on part of the domain and compute a global approximation by a suitable coupling of the local spaces. In detail, we show how optimal local approximation spaces can be constructed and approximated by random sampling. An overview of possible conforming and non-conforming couplings of the local spaces is provided and corresponding localized a posteriori error estimates are derived. We introduce concepts of local basis enrichment, which includes a discussion of adaptivity. Implementational aspects of localized model reduction methods are addressed. Finally, we illustrate the presented concepts for multiscale, linear elasticity and fluid-flow problems, providing several numerical experiments. This work has been submitted as a chapter in P. Benner, S. Grivet-Talocia, A. Quarteroni, G. Rozza, W.H.A. Schilders, L.M. Sileira. Handbook on Model Order Reduction. Walter De Gruyter GmbH, Berlin, 2019+. - Article
- Jan 2016
- INT J MULTISCALE COM

In a number of previous papers, local (coarse grid) multiscale model reduction techniques are developed using a Generalized Multiscale Finite Element Method. In these approaches, multiscale basis functions are constructed using local snapshot spaces, where a snapshot space is a large space that represents the solution behavior in a coarse block. In a number of applications (e.g., those discussed in the paper), one may have a sparsity in the snapshot space for an appropriate choice of a snapshot space. More precisely, the solution may only involve a portion of the snapshot space. In this case, one can use sparsity techniques to identify multiscale basis functions. In this paper, we consider two such sparse local multiscale model reduction approaches. In the first approach (which is used for parameter-dependent multiscale PDEs), we use local minimization techniques, such as sparse POD, to identify multiscale basis functions, which are sparse in the snapshot space. These minimization techniques use l1minimization to find local multiscale basis functions, which are further used for finding the solution. In the second approach (which is used for the Helmholtz equation), we directly apply l1minimization techniques to solve the underlying PDEs. This approach is more expensive as it involves a large snapshot space; however, in this example, we cannot identify a local minimization principle, such as local generalized SVD. All our numerical results assume the sparsity and we discuss this assumption for the snapshot spaces. Moreover, we discuss the computational savings provided by our approach. The sparse solution allows a fast evaluation of stiffness matrices and downscaling the solution to the fine grid since the reduced dimensional solution representation is sparse in terms of local snapshot vectors. Numerical results are presented, which show the convergence of the proposed method and the sparsity of the solution. - Article
- Sep 2018
- INT J NUMER METH ENG

In this paper, we propose a general concept for constructing multiscale basis functions within GMsFEM, which uses oversampling and stable decomposition. The oversampling refers to using larger regions in constructing multiscale basis functions and stable decomposition allows estimating the local errors. The analysis of multiscale methods involves decomposing the error by coarse regions, where each error contribution is estimated. In this estimate, we often use oversampling techniques to achieve a fast convergence. We demonstrate our concepts in the mixed, the Interior Penalty Discontinuous Galerkin (IPDG), and Hybridized Discontinuous Galerkin (HDG) discretizations. One of the important features of the proposed basis functions is that they can be used in online GMsFEM, where one constructs multiscale basis functions using residuals. In these problems, it is important to achieve a fast convergence, which can be guaranteed if we have a stable decomposition. In our numerical results, we present examples for both offline and online multiscale basis functions. Our numerical results show that one can achieve a fast convergence when using online basis functions. Moreover, we observe that coupling using HDG provides a better accuracy compared to IPDG, which is due to using multiscale glueing functions. - Article
- Sep 2018
- TRANSPORT POROUS MED

The past two decades have borne remarkable progress in our understanding of flow mechanisms and numerical simulation approaches of shale gas reservoir, with much larger number of publications in recent 5 years compared to that before year 2012. In this paper, a review is constructed with three parts: flow mechanism, reservoir models and numerical approaches. In mechanism, it is found that gas adsorption process can be concluded into different isotherm models for various reservoir basins. Multi-component adsorption mechanisms are taken into account in recent years. Flow mechanism and equations vary with different Knudsen numbers, which could be figured out in two ways: molecular dynamics (MD) and lattice Boltzmann method (LBM). MD has been successfully applied in the study of adsorption, diffusion, displacement and other mechanisms. LBM has been introduced in the study of slippage, Knudsen diffusion and apparent permeability correction. The apparent permeability corrections are introduced to improve classic Darcy’s model in matrix with low velocities and fractures with high velocities. At reservoir-scale simulation, gas flow models are presented with multiple porosity classified into organic matrix with nanopores, organic matrix with micropores, inorganic matrix and natural fractures. A popular trend is to incorporate geomechanism with flow model in order to better understand the shale gas production. Finally, to solve the new models based on enhanced flow mechanisms, improved macroscopic numerical approaches, including the finite difference method and finite element method, are commonly used in this area. Other approaches like finite volume method and fast matching method are also developed in recent years. - Article
- Jul 2018

In this paper, we propose a space-time GMsFEM for transport equations. Most of existing multiscale approaches use spatial multiscale basis functions or upscaling, and there are very few works that design space-time multiscale functions to solve the transport equation on a coarse grid. For the time dependent problems, the use of space-time multiscale basis functions offers several advantages as the spatial and temporal scales are intrinsically coupled. By using the GMsFEM idea with a space-time framework, one obtains a better dimensional reduction taking into account features of the solutions in both space and time. In addition, the time-stepping can be performed using much coarser time step sizes compared to the case when spatial multiscale basis are used. Our scheme is based on space-time snapshot spaces and model reduction using space-time spectral problems derived from the analysis. We give the analysis for the well-posedness and the spectral convergence of our method. We also present some numerical examples to demonstrate the performance of the method. In all examples, we observe a good accuracy with a few basis functions. - Article
- Sep 2016
- COMPUT METHOD APPL M

In this paper, we present an approximation of elliptic problems with multiscale and high-contrast diffusion coefficients. A mixed formulation is considered such that both pressure and velocity are approximated simultaneously. This formulation arises naturally in many applications such as flows in porous media. Due to the multiscale nature of the solutions, using model reduction is required to efficiently obtain approximate solutions. There are many multiscale approaches for elliptic problems in mixed formulation. These approaches include numerical homogenization and mixed multiscale finite element method, which aim to obtain a coarse accurate representation of the velocity without using an accurate representation for pressure. It has been a challenging task to construct a method giving accurate representation for both pressure and velocity. The goal in this paper is to construct multiscale basis functions for both pressure and velocity. We will apply the framework of Generalized Multiscale Finite Element Method (GMsFEM), and design systematic strategies for the construction of basis. The construction involves snapshot spaces and dimension reduction via local spectral problems. The mixed formulation is minimized in the sense of least-squares. The compatibility condition for multiscale finite element spaces of the pressure and velocity is not required in the least-squares mixed form. This gives more flexibility for the construction of multiscale basis functions for velocity and pressure. Convergence analysis is carried out for the least-squares mixed GMsFEM. Several numerical examples for various permeability fields are presented to show the performance of the presented method. The numerical results show that the least-squares mixed GMsFEM can give accurate approximation for both pressure and velocity using only a few basis functions per coarse element. - Article
- Mar 2017
- J COMPUT APPL MATH

In this paper, we propose a mixed Generalized Multiscale Finite Element Method (GMsFEM) for solving nonlinear Forchheimer flow in highly heterogeneous porous media. We consider the two term law form of the Forchheimer equation in the case of slightly-compressible single-phase flows. We write the resulting system in terms of a degenerate nonlinear flow equation for pressure when the nonlinearity depends on the pressure gradient. The proposed approach constructs multiscale basis functions for the velocity field following Mixed-GMsFEM as developed in Chung et al. (2015). To reduce the computational cost resulting from solving nonlinear system, we combine the GMsFEM with Discrete Empirical Interpolation Method (DEIM) to compute the nonlinear coefficients in some selected degrees of freedom at each coarse domain. In addition, a global reduction method such as Proper Orthogonal Decomposition (POD) is used to construct the online space to be used for different inputs or initial conditions. We present numerical and theoretical results to show that in addition to speeding up the simulation we can achieve good accuracy with a few basis functions per coarse edge. Moreover, we present an adaptive method for basis enrichment of the offline space based on an error indicator depending on the local residual norm. We use this enrichment method for the multiscale basis functions at some fixed time levels. Our numerical experiments show that these additional multiscale basis functions will reduce the current error if we start with a sufficient number of initial offline basis functions. - Article
- Oct 2019
- J SCI COMPUT

We propose a multiscale hybridizable discontinuous Galerkin method for Darcy flow and two phase flow simulations in highly heterogeneous media. The multiscale space consists of offline and online multiscale basis functions. The offline basis functions are constructed by solving appropriate local spectral problem, and thus contain important local media information. The online basis functions are computed iteratively with the residuals of previous multiscale solution on selected local regions. Typically, the offline basis provides initial multiscale solution for constructing online basis. For the two phase flow simulations, we only compute the basis space for the initial permeability field and keep it fixed as time advancing. Numerical experiments show the multiscale solution can approximate the fine scale solution accurately for both types of flow simulations.

- Article
- Jan 2013
- J COMPUT PHYS

In this paper, we propose a general approach called Generalized Multiscale Finite Element Method (GMsFEM) for performing multiscale simulations for problems without scale separation over a complex input space. As in multiscale finite element methods (MsFEMs), the main idea of the proposed approach is to construct a small dimensional local solution space that can be used to generate an efficient and accurate approximation to the multiscale solution with a potentially high dimensional input parameter space. In the proposed approach, we present a general procedure to construct the offline space that is used for a systematic enrichment of the coarse solution space in the online stage. The enrichment in the online stage is performed based on a spectral decomposition of the offline space. In the online stage, for any input parameter, a multiscale space is constructed to solve the global problem on a coarse grid. The online space is constructed via a spectral decomposition of the offline space and by choosing the eigenvectors corresponding to the largest eigenvalues. The computational saving is due to the fact that the construction of the online multiscale space for any input parameter is fast and this space can be re-used for solving the forward problem with any forcing and boundary condition. Compared with the other approaches where global snapshots are used, the local approach that we present in this paper allows us to eliminate unnecessary degrees of freedom on a coarse-grid level. We present various examples in the paper and some numerical results to demonstrate the effectiveness of our method. - Article
- Jun 1996
- SIAM J NUMER ANAL

we construct a converging adaptive algorithm for linear elements applied to Poisson's equation in two space dimensions. Starting from a macro triangulation, we describe how to construct an initial triangulation from a priori information. Then we use a posteriori error estimators to get a sequence of refined triangulations and approximate solutions. It is proved that the error, measured in the energy norm, decreases at a constant rate in each step until a prescribed error bound is reached. Extensions to higher-order elements in two space dimensions and numerical results are included. - In this paper, we present an efficient computational methodology for diffusion and convection-diffusion problems in highly heterogeneous media as well as convection-dominated diffusion problem. It is well known that the numerical computation for these problems requires a significant amount of computer memory and time. Nevertheless, the solutions to these problems typically contain a coarse component, which is usually the quantity of interest and can be represented with a small number of degrees of freedom. There are many methods that aim at the computation of the coarse component without resolving the full details of the solution. Our proposed method falls into the framework of interior penalty discontinuous Galerkin method, which is proved to be an effective and accurate class of methods for numerical solutions of partial differential equations. A distinctive feature of our method is that the solution space contains two components, namely a coarse space that gives a polynomial approximation to the coarse component in the traditional way and a multiscale space which contains sub-grid structures of the solution and is essential to the computation of the coarse component. In addition, stability of the method is proved. The numerical results indicate that the method can accurately capture the coarse behavior of the solution for problems in highly heterogeneous media as well as boundary and internal layers for convection-dominated problems.
- In this paper, we study the development of efficient multiscale methods for flows in heterogeneous media. Our approach uses the Generalized Multiscale Finite Element (GMsFEM) framework. The main idea of GMsFEM is to approximate the solution space locally using a few multiscale basis functions. This is typically achieved by selecting an appropriate snapshot space and a local spectral decomposition, e.g., the use of oversampled regions in order to achieve an efficient model reduction. However, the successful construction of snapshot spaces may be costly if too many local problems need to be solved in order to obtain these spaces. In this paper, we show that this efficiency can be achieved using a moderate quantity of local solutions (or snapshot vectors) with random boundary conditions on oversampled regions with zero forcing. Motivated by the randomized algorithm presented in [19], we consider a snapshot space which consists of harmonic extensions of random boundary conditions defined in a domain larger than the target region. Furthermore, we perform an eigenvalue decomposition in this small space. We study the application of randomized sampling for GMsFEM in conjunction with adaptivity, where local multiscale spaces are adaptively enriched. Convergence analysis is provided. We present representative numerical results to validate the method proposed.
- In this paper, we develop an adaptive Generalized Multiscale Discontinuous Galerkin Method (GMs-DGM) for a class of high-contrast flow problems, and derive a-priori and a-posteriori error estimates for the method. Based on the a-posteriori error estimator, we develop an adaptive enrichment algorithm for our GMsDGM and prove its convergence. The adaptive enrichment algorithm gives an automatic way to enrich the approximation space in regions where the solution requires more basis functions, which are shown to perform well compared with a uniform enrichment. We also discuss an approach that adaptively selects multiscale basis functions by correlating the residual to multiscale basis functions (cf. [4]). The proposed error indicators are L2-based and can be inexpensively computed which makes our approach efficient. Numerical results are presented that demonstrate the robustness of the proposed error indicators.
- Two overlapping Schwarz algorithms are developed for a discontinuous Galerkin (DG) finite element approximation of second order scalar elliptic problems in both two and three dimensions. The discontinuous Galerkin formulation is based on a staggered discretization introduced by Chung and Engquist [13] for the acoustic wave equation. Two types of coarse problems are introduced for the two-level Schwarz algorithms. The first is built on a nonoverlapping subdomain partition, which allows quite general subdomain partitions, and the second on introducing an additional coarse triangulation that can also be quite independent of the fine triangulation. Condition number bounds are established and numerical results are presented.
- Article
- Jan 2014
- GEOPHYSICS

Conventional finite-difference methods produce accurate solutions to the acoustic and elastic wave equation for many applications, but they face significant challenges when material properties vary significantly over distances less than the grid size. This challenge is likely to occur in reservoir characterization studies, because important reservoir heterogeneity can be present on scales of several meters to ten meters. Here, we describe a new multiscale finite-element method for simulating acoustic wave propagation in heterogeneous media that addresses this problem by coupling fine-and coarse-scale grids. The wave equation is solved on a coarse grid, but it uses basis functions that are generated from the fine grid and allow the representation of the fine-scale variation of the wavefield on the coarser grid. Time stepping also takes place on the coarse grid, providing further speed gains. Another important property of the method is that the basis functions are only computed once, and time savings are even greater when simulations are repeated for many source locations. We first present validation results for simple test models to demonstrate and quantify potential sources of error. These tests show that the fine-scale solution can be accurately approximated when the coarse grid applies a discretization up to four times larger than the original fine model. We then apply the multiscale algorithm to simulate a complete 2D seismic survey for a model with strong, fine-scale scatterers and apply standard migration algorithms to the resulting synthetic seismograms. The results again show small errors. Comparisons to a model that is upscaled by averaging densities on the fine grid show that the multiscale results are more accurate. - Article
- Apr 2014
- COMPUT MATH APPL

A BDDC (Balancing Domain Decomposition by Constraints) algorithm is developed and analyzed for a staggered discontinuous Galerkin (DG) finite element approximation of second order scalar elliptic problems. On a quite irregular subdomain partition, an optimal condition number bound is proved for two-dimensional problems. In addition, a sub-optimal but scalable condition number bound is obtained for three-dimensional problems. These bounds are shown to be independent of coefficient jumps in the subdomain partition. Numerical results are also included to show the performance of the algorithm. - Article
- Jan 2003
- COMMUN MATH SCI

The heterogenous multiscale method (HMM) is presented as a general methodology for the efficient numerical computation of problems with multiscales and multiphysics on multigrids. Both variational and dynamic problems are considered. The method relies on an efficent coupling between the macroscopic and microscopic models. In cases when the macroscopic model is not explicity available or invalid, the microscopic solver is used to supply the necessary data for the microscopic solver. Besides unifying several existing multiscale methods such as the ab initio molecular dynamics [13], quasicontinuum methods [73,69,68] and projective methods for systems with multiscales [34,35], HMM also provides a methodology for designing new methods for a large variety of multiscale problems. A framework is presented for the analysis of the stability and accuracy of HMM. Applications to problems such as homogenization, molecular dynamics, kinetic models and interfacial dynamics are discussed. - Article
- Sep 2013
- J COMPUT PHYS

In this paper, we derive an a-posteriori error indicator for the Generalized Multiscale Finite Element Method (GMsFEM) framework. This error indicator is further used to develop an adaptive enrichment algorithm for the linear elliptic equation with multiscale high-contrast coefficients. The GMsFEM, which has recently been introduced in [12], allows solving multiscale parameter-dependent problems at a reduced computational cost by constructing a reduced-order representation of the solution on a coarse grid. The main idea of the method consists of (1) the construction of snapshot space, (2) the construction of the offline space, and (3) the construction of the online space (the latter for parameter-dependent problems). In [12], it was shown that the GMsFEM provides a flexible tool to solve multiscale problems with a complex input space by generating appropriate snapshot, offline, and online spaces. In this paper, we study an adaptive enrichment procedure and derive an a-posteriori error indicator which gives an estimate of the local error over coarse grid regions. We consider two kinds of error indicators where one is based on the $L^2$-norm of the local residual and the other is based on the weighted $H^{-1}$-norm of the local residual where the weight is related to the coefficient of the elliptic equation. We show that the use of weighted $H^{-1}$-norm residual gives a more robust error indicator which works well for cases with high contrast media. The convergence analysis of the method is given. In our analysis, we do not consider the error due to the fine-grid discretization of local problems and only study the errors due to the enrichment. Numerical results are presented that demonstrate the robustness of the proposed error indicators. - Article
- May 1991
- WATER RESOUR RES

A numerical procedure for the determination of equivalent grid block permeability tensors for heterogeneous porous media is presented. The method entails solution of the fine scale pressure equation subject to periodic boundary conditions to yield, upon appropriate averaging of the fine scale velocity field, the coarse scale or equivalent grid block permeability. When the region over which this coarse scale permeability is computed constitutes a representative elementary volume (REV), the resulting equivalent permeability may be interpreted as the effective permeability of the region. Solution of the pressure equation on the fine scale is accomplished through the application of an accurate triangle-based finite element numerical procedure, which allows for the modeling of geometrically complex features. The specification of periodic boundary conditions is shown to yield symmetric, positive definite equivalent permeability tensors in all cases. The method is verified through application to a periodic model problem and is then applied to the scale up of areal and cross sections with fractally generated permeability fields. The applicability and limitations of the method for these more general heterogeneity fields are discussed. - Numerical modeling of wave propagation in heterogeneous media is important in many applications. Due to the complex nature, direct numerical simulations on the fine grid are prohibitively expensive. It is therefore important to develop efficient and accurate methods that allow the use of coarse grids. In this paper, we present a multiscale finite element method for wave propagation on a coarse grid. The proposed method is based on the Generalized Multiscale Finite Element Method (GMsFEM). To construct multiscale basis functions, we start with two snapshot spaces in each coarse-grid block where one represents the degrees of freedom on the boundary and the other represents the degrees of freedom in the interior. We use local spectral problems to identify important modes in each snapshot space. These local spectral problems are different from each other and their formulations are based on the analysis. To our best knowledge, this is the first time where multiple snapshot spaces and multiple spectral problems are used and necessary for efficient computations. Using the dominant modes from local spectral problems, multiscale basis functions are constructed to represent the solution space locally within each coarse block. These multiscale basis functions are coupled via the symmetric interior penalty discontinuous Galerkin method which provides a block diagonal mass matrix, and, consequently, results in fast computations in an explicit time discretiza- tion. Our methods' stability and spectral convergence are rigorously analyzed. Numerical examples are presented to show our methods' performance. We also test oversampling strategies. In particular, we discuss how the modes from different snapshot spaces can a?ect the proposed methods' accuracy.
- We construct a converging adaptive algorithm for linear elements applied to Poisson's equation in two space dimensions. Starting from a macro triangulation, we describe how to construct an initial triangulation from a priori information. Then we use a posteriori error estimators to get a sequence of refined triangulations and approximate solutions. It is proved that the error, measured in the energy norm, decreases at a constant rate in each step until a prescribed error bound is reached. Extensions to higher-order elements in two space dimensions and numerical results are included.
- In this paper, we propose oversampling strategies in the Generalized Multiscale Finite Element Method (GMsFEM) framework. The GMsFEM, which has been recently introduced in [12], allows solving multiscale parameter-dependent problems at a reduced computational cost by constructing a reduced-order representation of the solution on a coarse grid. The main idea of the method consists of (1) the construction of snapshot space, (2) the construction of the offline space, and (3) construction of the online space (the latter for parameter-dependent problems). In [12], it was shown that the GMsFEM provides a flexible tool to solve multiscale problems with a complex input space by generating appropriate snapshot, offline, and online spaces. In this paper, we develop oversampling techniques to be used in this context (see [19] where oversampling is introduced for multiscale finite element methods). It is known (see [19]) that the oversampling can improve the accuracy of multiscale methods. In particular, the oversampling technique uses larger regions (larger than the target coarse block) in constructing local basis functions. Our motivation stems from the analysis presented in this paper which show that when using oversampling techniques in the construction of the snapshot space and offline space, GMsFEM will converge independent of small scales and high-contrast under certain assumptions. We consider the use of multiple eigenvalue problem to improve the convergence and discuss their relation to single spectral problems that use oversampled regions. The oversampling procedures proposed in this paper differ from those in [19]. In particular, the oversampling domains are partially used in constructing local spectral problems. We present numerical results and compare various oversampling techniques in order to complement the proposed technique and analysis.
- Article
- Feb 2013
- J COMPUT PHYS

Motivated by applications to numerical simulation of flows in highly heterogeneous porous media, we develop multiscale finite element methods for second order elliptic equations. We discuss a multiscale model reduction technique in the framework of the discontinuous Galerkin finite element method. We propose three different finite element spaces on the coarse mesh. The first space is based on a local eigenvalue problem that uses a weighted $L_2-$norm for computing the "mass" matrix. The second space is generated by amending the eigenvalue problem of the first case with a term related to the penalty. The third choice is based on generation of a large space of snapshots and subsequent selection of a subspace of a reduced dimension. The approximation with these spaces is based on the discontinuous Galerkin finite element method framework. We investigate the stability and derive error estimates for the methods and further experimentally study their performance on a representative number of numerical examples. - Book
- Jan 2009

This expository book surveys the main concepts and recent advances in multiscale finite element methods. This monograph is intended for the broader audiences including engineers, applied scientists and those who are interested in multiscale simulations. The book is self-contained, starts from the basic concepts and proceeds to the latest developments in the field. Each chapter of the book starts with a simple introduction and the description of the proposed methods as well as with motivating examples. Numerical examples demonstrating the significance of the proposed methods are presented in each chapter. The book addresses mathematical and numerical issues in multiscale finite element methods and connects them to real-world applications. Narrative introduction provides a key to the book's organization and its scope. To make the presentation accessible to a broader audience, the analyses of the methods are given in the last chapter. - Article
- Jan 2005
- MULTISCALE MODEL SIM

This paper is concerned with a multiscale finite element method for numerically solving second-order scalar elliptic boundary value problems with highly oscillating coefficients. In the spirit of previous other works, our method is based on the coupling of a coarse global mesh and a. ne local mesh, the latter being used for computing independently an adapted finite element basis for the coarse mesh. The main idea is the introduction of a composition rule, or change of variables, for the construction of this finite element basis. In particular, this allows for a simple treatment of high-order finite element methods. We provide optimal error estimates in the case of periodically oscillating coefficients. We illustrate our method in various examples. - Article
- Jan 2013
- J COMPUT PHYS

In this paper, we combine concepts of the generalized multiscale finite element method and mode decomposition methods to construct a robust local-global approach for model reduction of flows in high-contrast porous media. This is achieved by implementing proper orthogonal decomposition (POD) and dynamic mode decomposition (DMD) techniques on a coarse grid. The resulting reduced-order approach enables a significant reduction in the flow problem size while accurately capturing the behavior of fully resolved solutions. We consider a variety of high-contrast coefficients and present the corresponding numerical results to illustrate the effectiveness of the proposed technique. This paper is a continuation of the first part where we examine the applicability of POD and DMD to derive simplified and reliable representations of flows in high-contrast porous media. In the current paper, we discuss how these global model reduction approaches can be combined with local techniques to speed-up the simulations. The speed-up is due to inexpensive, while sufficiently accurate, computations of global snapshots. - Flow based upscaling of absolute permeability has become an im-portant step in practical simulations of flow through heterogeneous formations. The central idea is to compute upscaled, grid-block permeability from fine scale solutions of the flow equation. Such solutions can be either local in each grid-block or global in the whole domain. It is well-known that the grid-block permeability may be strongly influenced by the boundary conditions imposed on the flow equations and the size of the grid-blocks. We show that the up-scaling errors due to both effects manifest as the resonance between the small physical scales of the media and the artificial size of the grid blocks. To ob-tain precise error estimates, we study the scale-up of single phase steady flows through media with periodic small scale heterogeneity. As demonstrated by our numerical experiments, these estimates are also useful for understanding the upscaling of general random media. It is further shown that the over-sampling technique introduced in our previous work can be used to reduce the resonance error and obtain boundary-condition independent, grid-block per-meability. Some misunderstandings in scale up studies are also clarified in this work.
- Article
- May 2007
- Comm Pure Appl Math

We consider divergence form elliptic operators in dimension n ge; 2 with L∞ coefficients. Although solutions of these operators are only Hölder-continuous, we show that they are differentiable (C1, α) with respect to harmonic coordinates. It follows that numerical homogenization can be extended to situations where the medium has no ergodicity at small scales and is characterized by a continuum of scales. This new numerical homogenization method is based on the transfer of a new metric in addition to traditional averaged (homogenized) quantities from subgrid scales into computational scales. Error bounds can be given and this method can also be used as a compression tool for differential operators. © 2006 Wiley Periodicals, Inc. - ChapterFull-text available
- Jan 2005

Proper orthogonal decomposition (POD) provides a method for deriving low order models of dynamical systems. In our application we apply POD to derive a Galerkin approximation in the spatial variable, with basis functions corresponding to the solution of the physical system at pre-specified time instances. These are called the snapshots. Due to possible linear dependence or almost linear dependence, the snapshots themselves are not appropriate as a basis. Rather a singular value decomposition is carried out and the leading generalized eigenfunctions are chosen as a basis, referred to as the POD basis. - ChapterFull-text available
- Oct 2011

We present a new class of coarse spaces for two-level additive Schwarz preconditioners that yield condition number bound independent of the contrast in the media properties. These coarse spaces are an extension of the spaces discussed in [3]. Second order elliptic equations are considered. We present theoretical and numerical results. Detailed description of the results and numerical studies will be presented elsewhere. - In this contribution we analyze a generalization of the heterogeneous multiscale finite element method for elliptic homogenization problems in perforated domains. The method was originally introduced by E and Engquist (Commun Math Sci 1(1):87–132, 2003) for homogenization problems in fixed domains. It is based on a standard finite element approach on the macroscale, where the stiffness matrix is computed by solving local cell problems on the microscale. A-posteriori error estimates are derived in L 2(Ω) by reformulating the problem into a discrete two-scale formulation (see also, Ohlberger in Multiscale Model Simul 4(1):88–114, 2005) and using duality methods afterwards. Numerical experiments are given in order to numerically evaluate the efficiency of the error estimate.
- Article
- Feb 2011
- J COMPUT PHYS

In this paper we study multiscale finite element methods (MsFEMs) using spectral multiscale basis functions that are designed for high-contrast problems. Multiscale basis functions are constructed using eigenvectors of a carefully selected local spectral problem. This local spectral problem strongly depends on the choice of initial partition of unity functions. The resulting space enriches the initial multiscale space using eigenvectors of local spectral problem. The eigenvectors corresponding to small, asymptotically vanishing, eigenvalues detect important features of the solutions that are not captured by initial multiscale basis functions. Multiscale basis functions are constructed such that they span these eigenfunctions that correspond to small, asymptotically vanishing, eigenvalues. We present a convergence study that shows that the convergence rate (in energy norm) is proportional to (H/Λ∗)1/2, where Λ∗ is proportional to the minimum of the eigenvalues that the corresponding eigenvectors are not included in the coarse space. Thus, we would like to reach to a larger eigenvalue with a smaller coarse space. This is accomplished with a careful choice of initial multiscale basis functions and the setup of the eigenvalue problems. Numerical results are presented to back-up our theoretical results and to show higher accuracy of MsFEMs with spectral multiscale basis functions. We also present a hierarchical construction of the eigenvectors that provides CPU savings. - Article
- Feb 2011
- J COMPUT PHYS

The multiscale finite volume (MSFV) method is a computationally efficient numerical method for the solution of elliptic and parabolic problems with heterogeneous coefficients. It has been shown for a wide range of test cases that the MSFV results are in close agreement with those obtained with a classical (computationally expensive) technique. The method, however, fails to give accurate results for highly anisotropic heterogeneous problems due to weak localization assumptions. Recently, a convergent iterative MSFV (i-MSFV) method was developed to enhance the quality of the multiscale results by improving the localization conditions. Although the i-MSFV method proved to be efficient for most practical problems, it is still favorable to improve the localization condition adaptively, i.e. only for a sub-domain where the original MSFV localization conditions are not acceptable, e.g. near shale layers and long coherent structures with high permeability contrasts. In this paper, a space–time adaptive i-MSFV (ai-MSFV) method is introduced. It is shown how to improve the MSFV results adaptively in space and simulation time. The fine-scale smoother, which is necessary for convergence of the i-MSFV method, is also applied locally. Finally, for multiphase flow problems, two criteria are investigated for adaptively updating the MSFV interpolation functions: (1) a criterion based on the total mobility change for the transient coefficients and (2) a criterion based on the pressure equation residual for the accuracy of the results. For various challenging test cases it is demonstrated that iterations in order to obtain accurate results even for highly anisotropic heterogeneous problems are required only in small sub-domains and not everywhere. The findings show that the error introduced in the MSFV framework can be controlled and improved very efficiently with very little additional computational cost compared to the original, non-iterative MSFV method. - Article
- May 2003
- J COMPUT PHYS

In this paper we present a multi-scale finite-volume (MSFV) method to solve elliptic problems with many spatial scales arising from flow in porous media. The method efficiently captures the effects of small scales on a coarse grid, is conservative, and treats tensor permeabilities correctly. The underlying idea is to construct transmissibilities that capture the local properties of the differential operator. This leads to a multi-point discretization scheme for the finite-volume solution algorithm. Transmissibilities for the MSFV have to be constructed only once as a preprocessing step and can be computed locally. Therefore this step is perfectly suited for massively parallel computers. Furthermore, a conservative fine-scale velocity field can be constructed from the coarse-scale pressure solution. Two sets of locally computed basis functions are employed. The first set of basis functions captures the small-scale heterogeneity of the underlying permeability field, and it is computed in order to construct the effective coarse-scale transmissibilities. A second set of basis functions is required to construct a conservative fine-scale velocity field. The accuracy and efficiency of our method is demonstrated by various numerical experiments. - Article
- Sep 2006
- J COMPUT PHYS

We describe a sequential fully implicit (SFI) multi-scale finite volume (MSFV) algorithm for nonlinear multi-phase flow and transport in heterogeneous porous media. The method extends the recently developed multiscale approach, which is based on an IMPES (IMplicit Pressure, Explicit Saturation) scheme [P. Jenny, S.H. Lee, H.A. Tchelepi, Adaptive multiscale finite volume method for multi-phase flow and transport, Multiscale, Model. Simul. 3 (2005) 50–64]. That previous method was tested extensively and with a series of difficult test cases, where it was clearly demonstrated that the multiscale results are in excellent agreement with reference fine-scale solutions and that the computational efficiency of the MSFV algorithm is much higher than that of standard reservoir simulators. However, the level of detail and range of property variability included in reservoir characterization models continues to grow. For such models, the explicit treatment of the transport problem (i.e. saturation equations) in the IMPES-based multiscale method imposes severe restrictions on the time step size, and that can become the major computational bottleneck. Here we show how this problem is resolved with our sequential fully implicit (SFI) MSFV algorithm. Simulations of large (million cells) and highly heterogeneous problems show that the results obtained with the implicit multi-scale method are in excellent agreement with reference fine-scale solutions. Moreover, we demonstrate the robustness of the coupling scheme for nonlinear flow and transport, and we show that the MSFV algorithm offers great gains in computational efficiency compared to standard reservoir simulation methods. - Article
- Jun 1997
- J COMPUT PHYS

In this paper, we study a multiscale finite element method for solving a class of elliptic problems arising from composite materials and flows in porous media, which contain many spatial scales. The method is designed to efficiently capture the large scale behavior of the solution without resolving all the small scale features. This is accomplished by constructing the multiscale finite element base functions that are adaptive to the local property of the differential operator. Our method is applicable to general multiple-scale problems without restrictive assumptions. The construction of the base functions is fully decoupled from element to element; thus, the method is perfectly parallel and is naturally adapted to massively parallel computers. For the same reason, the method has the ability to handle extremely large degrees of freedom due to highly heterogeneous media, which are intractable by conventional finite element (difference) methods. In contrast to some empirical numerical upscaling methods, the multiscale method is systematic and self- consistent, which makes it easier to analyze. We give a brief analysis of the method, with emphasis on the “resonant sampling” effect. Then, we propose an oversampling technique to remove the resonance effect. We demonstrate the accuracy and efficiency of our method through extensive numerical experiments, which include problems with random coefficients and problems with continuous scales. Parallel implementation and performance of the method are also addressed. - Article
- Dec 2006
- J COMPUT PHYS

In this paper we propose a modified multiscale finite element method for two-phase flow simulations in heterogeneous porous media. The main idea of the method is to use the global fine-scale solution at initial time to determine the boundary conditions of the basis functions. This method provides a significant improvement in two-phase flow simulations in porous media where the long-range effects are important. This is typical for some recent benchmark tests, such as the SPE comparative solution project [M. Christie, M. Blunt, Tenth spe comparative solution project: a comparison of upscaling techniques, SPE Reser. Eval. Eng. 4 (2001) 308–317], where porous media have a channelized structure. The use of global information allows us to capture the long-range effects more accurately compared to the multiscale finite element methods that use only local information to construct the basis functions. We present some analysis of the proposed method to illustrate that the method can indeed capture the long-range effect in channelized media. - ArticleFull-text available
- Apr 2011

Seismic data are routinely used to infer in situ properties of earth materials on many scales, ranging from global studies to investigations of surficial geological formations. While inversion and imaging algorithms utilizing these data have improved steadily, there are remaining challenges that make detailed measurements of the properties of some geologic materials very difficult. For example, the determination of the concentration and orientation of fracture systems is prohibitively expensive to simulate on the fine grid and, thus, some type of coarse-grid simulations are needed. In this paper, we describe a new multiscale finite element algorithm for simulating seismic wave propagation in heterogeneous media. This method solves the wave equation on a coarse grid using multiscale basis functions and a global coupling mechanism to relate information between fine and coarse grids. Using a mixed formulation of the wave equation and staggered discontinuous basis functions, the proposed multiscale methods have the following properties. • The total wave energy is conserved. • Mass matrix is diagonal on a coarse grid and explicit energy-preserving time discretization does not require solving a linear system at each time step. • Multiscale basis functions can accurately capture the subgrid variations of the solution and the time stepping is performed on a coarse grid. We discuss various subgrid capturing mechanisms and present some preliminary numerical results. - Article
- Jan 2010
- MULTISCALE MODEL SIM

In this paper, we study multiscale methods for high-contrast elliptic problems where the media properties change dramatically. The disparity in the media properties (also referred to as high contrast in the paper) introduces an additional scale that needs to be resolved in multiscale simulations. First, we present a construction that uses an integral equation to represent the highcontrast component of the solution. This representation involves solving an integral equation along the interface where the coefficients are discontinuous. The integral representation suggests some multiscale approaches that are discussed in the paper. One of these approaches entails the use of interface functions in addition to multiscale basis functions representing the heterogeneities without high contrast. In this paper, we propose an approximation for the solution of the integral equation using the interface problems in reduced-contrast media. Reduced-contrast media are obtained by lowering the variance of the coefficients. We also propose a similar approach for the solution of the elliptic equation without using an integral representation. This approach is simpler to use in the computations because it does not involve setting up integral equations. The main idea of this approach is to approximate the solution of the high-contrast problem by the solutions of the problems formulated in reduced-contrast media. In this approach, a rapidly converging sequence is proposed where only problems with lower contrast are solved. It was shown that this sequence possesses the convergence rate that is inversely proportional to the reduced contrast. This approximation allows choosing the reduced-contrast problem based on the coarse-mesh size as discussed in this paper. We present a simple application of this approach to homogenization of elliptic equations with high-contrast coefficients. The presented approaches are limited to the cases where there are sharp changes in the contrast (i.e., the high contrast can be represented by piecewise constant functions with disparate values). We present analysis for the proposed approaches and the estimates for the approximations used in multiscale algorithms. Numerical examples are presented. - Article
- Jan 2010
- MULTISCALE MODEL SIM

In this paper, robust preconditioners for multiscale flow problems are investigated. We consider elliptic equations with highly varying coefficients. We design and analyze two-level domain decomposition preconditioners that converge independent of the contrast in the media properties. The coarse spaces are constructed using selected eigenvectors of a local spectral problem. Our new construction enriches any given initial coarse space to make it suitable for high-contrast problems. Using the initial coarse space we construct local mass matrices for the local eigenvalue problems. We show that there is a gap in the spectrum of the eigenvalue problem when high-conductivity regions are disconnected. The eigenvectors corresponding to small, asymptotically vanishing eigenvalues are chosen to construct an enrichment of the initial coarse space. Only via a judicious choice of the initial space do we reduce the dimension of the resulting coarse space. Classical coarse basis functions such as multiscale or energy minimizing basis functions can be taken as the basis for the initial coarse space. In particular, if we start with classical multiscale basis, the selected eigenvectors represent only high-conductivity features that cannot be localized within a coarse-grid block, e.g., high-conductivity channels that connect the boundaries of a coarse-grid block. Numerical experiments are presented. The new construction presented here can handle tensor coefficients. The results of this paper substantially extend those presented in [J. Galvis and Y. Efendiev, Multiscale Model. Simul., 8 (2010), pp. 1461-1483], where only scalar coefficients are considered and the coarse space dimension can be very large because the coarse space includes all isolated high-conductivity features that are within a coarse block. - Article
- Jan 2004
- SIAM J NUMER ANAL

We present a two-scale theoretical framework for approximating the solution of a second order elliptic problem. The elliptic coefficient is assumed to vary on a scale that can be resolved on a fine numerical grid, but limits on computational power require that computations be performed on a coarse grid. We consider the elliptic problem in mixed variational form over W × V ⊂ L2 × H(div). We base our scale expansion on local mass conservation over the coarse grid. It is used to define a direct sum decomposition of W × V into coarse and "subgrid" subspaces Wc × Vc and δW × δV such that (1) ∇· Vc = Wc and ∇· δV = δW, and (2) the space δV is locally supported over the coarse mesh. We then explicitly decompose the variational problem into coarse and subgrid scale problems. The subgrid problem gives a well-defined operator taking Wc × Vc to δW × δV, which is localized in space, and it is used to upscale, that is, to remove the subgrid from the coarse-scale problem. Using standard mixed finite element spaces, two-scale mixed spaces are defined. A mixed approximation is defined, which can be viewed as a type of variational multiscale method or a residual-free bubble technique. A numerical Green's function approach is used to make the approximation to the subgrid operator efficient to compute. A mixed method π-operator is defined for the two-scale approximation spaces and used to show optimal order error estimates. - Article
- Oct 2010
- MATH COMPUT

We introduce a new multiscale finite element method which is able to accurately capture solutions of elliptic interface problems with high contrast coefficients by using only coarse quasiuniform meshes, and without resolving the interfaces. A typical application would be the modelling of flow in a porous medium containing a number of inclusions of low (or high) permeability embedded in a matrix of high (respectively low) permeability. Our method is H^1- conforming, with degrees of freedom at the nodes of a triangular mesh and requiring the solution of subgrid problems for the basis functions on elements which straddle the coefficient interface but which use standard linear approximation otherwise. A key point is the introduction of novel coefficientdependent boundary conditions for the subgrid problems. Under moderate assumptions, we prove that our methods have (optimal) convergence rate of O(h) in the energy norm and O(h^2) in the L_2 norm where h is the (coarse) mesh diameter and the hidden constants in these estimates are independent of the “contrast” (i.e. ratio of largest to smallest value) of the PDE coefficient. For standard elements the best estimate in the energy norm would be O(h^(1/2−ε)) with a hidden constant which in general depends on the contrast. The new interior boundary conditions depend not only on the contrast of the coefficients, but also on the angles of intersection of the interface with the element edges. - Article
- Nov 2006

Numerical approximation of the solution of partial differential equations plays an important role in many areas such as engineering, mechanics, physics, chemistry, biology � for computer-aided design-analysis, computer-aided decision-making or simply better understanding. The fidelity of the simulations with respect to reality is achieved through the combined efforts to derive: (i) better models, (ii) faster numerical algorithm, (iii) more accurate discretization methods and (iv) improved large scale computing resources. In many situations, including optimization and control, the same model, depending on a parameter that is changing, has to be simulated over and over, multiplying by a large factor (up to 100 or 1000) the solution procedure cost of one single simulation. The reduced basis method allows to define a surrogate solution procedure, that, thanks to the complementary design of fidelity certificates on outputs, allows to speed up the computations by two to three orders of magnitude while maintaining a sufficient accuracy. We present here the basics of this approach for linear and non linear elliptic and parabolic PDE�s. - Article
- Dec 2004
- COMMUN MATH SCI

In this paper we propose a generalization of multiscale finite element methods (Ms-FEM) to nonlinear problems. We study the convergence of the proposed method for nonlinear elliptic equations and propose an oversampling technique. Numerical examples demonstrate that the over-sampling technique greatly reduces the error. The application of MsFEM to porous media flows is considered. Finally, we describe further generalizations of MsFEM to nonlinear time-dependent equations and discuss the convergence of the method for various kinds of heterogeneities. - . The multiscale finite element method (MsFEM) [T. Y. Hou, X. H. Wu, and Z. Cai, Math. Comp., 1998, to appear; T. Y. Hou and X. H. Wu, J. Comput. Phys., 134 (1997), pp. 169--189] has been introduced to capture the large scale solutions of elliptic equations with highly oscillatory coe#cients. This is accomplished by constructing the multiscale base functions from the local solutions of the elliptic operator. Our previous study reveals that the leading order error in this approach is caused by the "resonant sampling," which leads to large error when the mesh size is close to the small scale of the continuous problem. Similar di#culty also arises in numerical upscaling methods. An oversampling technique has been introduced to alleviate this di#culty [T. Y. Hou and X. H. Wu, J. Comput. Phys., 134 (1997), pp. 169--189]. A consequence of the oversampling method is that the resulting finite element method is no longer conforming. Here we give a detailed analysis of the nonconforming error....