key: cord-0045964-41gqaude
authors: Wang, Yiran; Chung, Eric; Fu, Shubin
title: Adaptive Multiscale Model Reduction for Nonlinear Parabolic Equations Using GMsFEM
date: 2020-05-25
journal: Computational Science - ICCS 2020
DOI: 10.1007/978-3-030-50436-6_9
sha: 3c3a89c0f8130444c343cfbabfb04862132aa3ae
doc_id: 45964
cord_uid: 41gqaude

In this paper, we propose a coupled Discrete Empirical Interpolation Method (DEIM) and Generalized Multiscale Finite element method (GMsFEM) to solve nonlinear parabolic equations with application to the Allen-Cahn equation. The Allen-Cahn equation is a model for nonlinear reaction-diffusion process. It is often used to model interface motion in time, e.g. phase separation in alloys. The GMsFEM allows solving multiscale problems at a reduced computational cost by constructing a reduced-order representation of the solution on a coarse grid. In [14], it was shown that the GMsFEM provides a flexible tool to solve multiscale problems by constructing appropriate snapshot, offline and online spaces. In this paper, we solve a time dependent problem, where online enrichment is used. The main contribution is comparing different online enrichment methods. More specifically, we compare uniform online enrichment and adaptive methods. We also compare two kinds of adaptive methods. Furthermore, we use DEIM, a dimension reduction method to reduce the complexity when we evaluate the nonlinear terms. Our results show that DEIM can approximate the nonlinear term without significantly increasing the error. Finally, we apply our proposed method to the Allen Cahn equation.

In this paper, we consider the Generalized Multiscale Finite element method (GMsFEM) for solving nonlinear parabolic equations. The main objectives of the paper are the following: (1) to demonstrate the main concepts of GMsFEM and brief review of the techniques; (2) to compare various online enrichment techniques; (3) to discuss the use of the Discrete Empirical Interpolation Method (DEIM) and present its performance in reducing complexity. GMsFEM is a flexible general framework that generalizes the Multiscale Finite Element Method (MsFEM) by systematically enriching the coarse spaces. The main idea of this enrichment is to add extra basis functions that are needed to reduce the error substantially. Once the offline space is derived, it stays fixed and unchanged in the online stage. In [3, 4] , it is shown that a good approximation from the reduced model can be expected only if the offline information is a good representation of the problem. For time dependent problems, online enrichment is necessary. We compare two kinds of online enrichment methods: uniform and adaptive enrichment, where the latter focuses on where to add online basis. We will discuss it in numerical results with more details. When a general nonlinearity is present, the cost to evaluate the projected nonlinear function still depends on the dimension of the original system, resulting in simulation times that can hardly improve over the original system. One approach to reduce computational cost is the POD-Galerkin method [5] [6] [7] [8] , which is applied to many applications, for example, in [9] [10] [11] [12] [13] . DEIM focuses on approximating each nonlinear function so that a certain coefficient matrix can be precomputed and, as a result, the complexity in evaluating the nonlinear term becomes proportional to the small number of selected spatial indices. In this paper, we will compare various approximations of the DEIM projection. We will illustrate these concepts by applying our proposed method to the Allen Cahn equation. The remainder of the paper is organized as follows. In Sect. 2, we present the problem setting and main ingredients of GMsFEM. In Sect. 3, we consider the methods to solve the Allen-Cahn equation.

In this section, we will give the construction of our GMsFEM for nonlinear parabolic equations. First, we present some basic notations and the coarse grid formulation in Sect. 2.1. Then, we present the construction of the multiscale snapshot functions and basis functions in Sect. 2.2. The online enrichment process is introduced in Sect. 2.3.

Here, we denote the exact solution of (1) by u, κ(x) is a high-contrast and heterogeneous permeability field, f = f (x, u) is the nonlinear source function depending on the u variable, g(x) is a given function and T > 0 is the final time. We denote the solution and the source term at t = t n by u(·, t n ) and f (u(·, t n )) respectively. The variational formulation for the problem (1) is: find u(·, t) ∈ H 1 0 (Ω) such that

where A(u, v) = Ω κ∇u · ∇v dx. In order to discretize (2) in time, we need to apply some time differencing methods. For simplicity, we first apply the implicit Euler scheme with time step Δt > 0 and in Sect. 3, we will consider the exponential time differencing method (ETD). We obtain the following discretization for each time t n = nΔt, n = 1, 2, · · · , N (T = NΔt),

Let T h be a partition of the domain Ω into fine finite elements. Here h > 0 is the fine grid mesh size. The coarse partition, T H of the domain Ω, is formed such that each element in T H is a connected union of fine-grid blocks. More precisely,

The quantity H > 0 is the coarse mesh size. We will consider the rectangular coarse elements and the methodology can be used with general coarse elements. An illustration of the mesh notations is shown in the Fig. 1 . We denote the interior nodes of T H by x i , i = 1, · · · , N in , where N in is the number of interior nodes. The coarse elements of T H are denoted by K j , j = 1, 2, · · · , N e , where N e is the number of coarse elements. We define the coarse neighborhood of the nodes x i by D i := ∪{K j ∈ T H : x i ∈ K j }.

In this paper, we will apply the GMsFEM to solve nonlinear parabolic equations. The method is motivated by the finite element framework. First, a variational formulation is defined. Then we construct some multiscale basis functions. Once the fine grid is given, we can compute the fine-grid solution. Let γ 1 , · · · , γ n be the standard finite element basis, and define V f = span{γ 1 , · · · , γ n } to be the fine space. We obtained the fine solution denoted by u n f at t = t n by solving

where g h is the V f based approximation of g. The construction of multiscale basis functions follows two general steps. First, we construct snapshot basis functions in order to build a set of possible modes of the solutions. In the second step, we construct multiscale basis functions with a suitable spectral problem defined in the snapshot space. We take the first few dominated eigenfunctions as basis functions. Using the multiscale basis functions, we obtain a reduced model. More specifically, once the coarse and fine grids are given, one may construct the multiscale basis functions to approximate the solution of (2). To obtain the multiscale basis functions, we first define the snapshot space. For each coarse neighborhood D i , define J h (D i ) as the set of the fine nodes of T h lying on ∂D i and denote the its cardinality by

The local snapshot space V

snap . In the second step, a dimension reduction is performed on V snap . For each i = 1, · · · , N in , we solve the following spectral problem:

is a set of partition of unity that solves the following system:

where p i is some polynomial functions and we can choose linear functions for simplicity. Assume that the eigenvalues obtained from (5) are arranged in ascending order and we may use the first 1 < l i ≤ L i (with l i ∈ N + ) eigenfunctions (related to the smallest l i eigenvalues) to form the local multiscale space V

off is the direct sum of the local mulitiscale spaces, namely

off . Once the multiscale space V off is constructed, we can find the GMsFEM solution u n off at t = t n by solving the following equation

We will present the constructions of online basis functions [1] in this section.

Online Adaptive Algorithm. In this subsection, we will introduce the method of online enrichment. After obtaining the multiscale space V off , one may add some online basis functions based on local residuals. Let u n off ∈ V off be the solution obtained in (6) at time t = t n . Given a coarse neighborhood D i , we define

We also define the local residual operator R n i :

The operator norm R n i , denoted by R n i V * i , gives a measure of the quantity of residual. The online basis functions are computed during the time-marching process for a given fixed time t = t n , contrary to the offline basis functions that are pre-computed.

Suppose one needs to add one new online basis φ into the space V i . The analysis in [1] suggests that the required online basis φ ∈ V i is the solution to the following equation

We refer to τ ∈ N as the level of the enrichment and denote the solution of (6) by u n,τ off . Remark that V n,0 off := V off for time level n ∈ N. Let I ⊂ {1, 2, . . . , N in } be the index set over some non-lapping coarse neighborhoods. For each i ∈ I, we obtain a online basis φ i ∈ V i by solving (8) 

Two Online Adaptive Methods. In this section, we compare two ways to obtain online basis functions which are denoted by online adaptive method 1 and online adaptive method 2 respectively. Online adaptive method 1 is adding online basis using online adaptive method from offline space in each time step, which means basis functions obtained in last time step are not used in current time step. Online adaptive method 2 is keeping online basis functions in each time step. Using this accumulation strategy, we can skip online enrichment after a certain time period when the residual defined in (7) is under given tolerance. We also presents the results of these two methods in Fig. 3 and Fig. 4 respectively.

Numerical Results. In this section, we present some numerical examples to demonstrate the efficiency of our proposed method. The computational domain is Ω = (0, 1) 2 ⊂ R 2 and T = 1. The medium κ 1 and κ 2 are shown in Fig. 2 , where the contrasts are 10 4 and 10 5 for κ 1 and κ 2 respectively. Without special descriptions, we use κ 1 .

For each function to be approximated, we define the following quantities e n a and e n 2 at t = t n to measure energy error and L 2 error respectively.

where u n f is the fine-grid solution (reference solution) and u n off is the approximation obtained by the GMsFEM method. We define the energy norm and L 2 norm of u by

Example 2.1. In this example, we compare the error using adaptive online method 1 and uniform enrichment under different numbers of initial basis functions. We set the mesh size to be H = 1/16 and h = 1/256. The time step is Δt = 10 −3 and the final time is T = 1. The initial condition is u(x, y, t)| t=0 = 4(0.5 − x)(0.5 − y). We set the permeability to be κ 1 . We set the source term f = 1 2 (u 3 − u), where = 0.01. We present the numerical results for the GMsFEM at time t = 0.1 in Table 1 , 2, and 3. For comparison, we present the results where online enrichment is not applied in Table 4 . We observe that the adaptive online enrichment converges faster. Furthermore, as we compare Table 4 and Table 1 , we note that the online enrichment does not improve the error if we only have one offline basis function per neighborhood. Because the first eigenvalue is small, the error decreases in the online iteration is small. In particular, for each iteration, the error decrease slightly. As we increase the number of initial offline basis, the convergence is very fast and one online iteration is sufficient to reduce the error significantly.

We compare online Method 1 and 2 under different tolerance. We keep H, h and the initial condition the same as in Example 2.1. We choose intial number of basis to be 450, which means we choose two initial basis per neighborhood. We keep the source term as f = 1 2 (u 3 − u). When = 0.01, we choose the time step Δt to be 10 −4 . We plot the error and DOF from online Method 1 in Fig. 3 and compare with results from online Method 2 in Fig. 4 . From Fig. 3 and 4 , we can see the error and DOF reached stability at t = 0.01. In Fig. 4 , we can see the DOF keeps increasing before turning steady. The error remains at a relatively low level without adding online basis after some time. As a cost, online method 2 suffers bigger errors than method 1 with same tolerance. We also apply our online adaptive method 2 under permeability κ 2 in Fig. 5 . The errors are relatively low for two kinds of permeability. 

In this section, we apply our proposed method to the Allen Cahn equation. We use the Exponential Time Differencing (ETD) for time dsicretization. To deal with the nonlinear term, DEIM is applied. We will present the two methods in the following subsections.

Let τ be the time step. Using ETD, u n off is the solution to (9)

Next, we will derive this equation. We have

Multiplying the equation by integrating factor e p(u) , we have

We require the above to become

By solving

Using Backward Euler method in (10), we have u n − τ div(κ∇u n ) = e −p(u)n u n−1 (11) where p(u) n = p(u(t n )−u(t n−1 )). To solve (11), we approximate (11) as follows:

Using above approximation, we have

When we evaluate the nonlinear term, the complexity is O(α(n) + c · n), where α is some function and c is a constant. To reduce the complexity, we approximate local and global nonlinear functions with the Discrete Empirical Interpolation Method (DEIM) [2] . DEIM is based on approximating a nonlinear function by means of an interpolatory projection of a few selected snapshots of the function. The idea is to represent a function over the domain while using empirical snapshots and information at some locations (or components). The key to complexity reduction is to replace the orthogonal projection of POD with the interpolation projection of DEIM in the same POD basis. We briefly review the DEIM. Let f (τ ) be the nonlinear function. We are desired to find an approximation of f (τ ) at a reduced cost. To obtain a reduced order approximation of f (τ ), we first define a reduced dimentional space for it. We would like to find m basis vectors (where m is much smaller than n), φ 1 , · · · , φ m , such that we can write

where Φ = (φ 1 , · · · , φ m ). We employ POD to obtain Φ and use DEIM (refer Table 5 ) to compute d(τ ) as follows. In particular, we solve d(τ ) by using m rows of Φ. This can be formalized using the matrix P P = [e ℘1 , . . . , e ℘m ] ∈ R n×m , where e ℘i = [0, · · · , 1, 0, · · · , 0] ∈ R n is the ℘ th i column of the identity matrix I n ∈ R n×n for i = 1, · · · , m. Using P T f (τ ) = P T Φd(τ ), we can get the approximation for f (τ ) as follows: Fig. 7 .

In this section, we consider using the snapshot from different initial conditions, we record the results in Fig. 9 . We first choose the initial condition to be compared Fig. 9 and Fig. 6 , we can see that different initial conditions can have less impact on the final solution since the solution is close to the one where the snapshot is obtained in the same equation.

Different Permeability Field. In this section, we consider using the snapshot from different permeability, we record the results in Fig. 10 . For reference, the first two figures plots the fine solution and multiscale solution without using DEIM. And we construct snapshot from another permeability κ 1 and we apply it to compute the solution in κ 2 . The last figure shows the of using DEIM is relatively small.

In this section, we construct the snapshot by using nonlinear function obtained in previous time step for example when t < 0.05. Then we apply it to DEIM to solve the equation in 0.05 < t < 0.06. We use these way to solve the equation with permeability κ 1 and κ 2 respectively. We plot the results in Fig. 11 and 12. From these figures, we can see that DEIM have different effects applied to different permeability. With κ 1 , the error increases significantly when DEIM are applied. But with κ 2 , the error decreased to a lower level when we use DEIM. 

Residual-driven online generalized multiscale finite element methods

Nonlinear model reduction via discrete empirical interpolation

Adaptive multiscale model reduction with generalized multiscale finite element methods

Online adaptive local-global model reduction for flows in heterogeneous porous media

Proper orthogonal decomposition surrogate models for nonlinear dynamical systems: error estimates and suboptimal control

Control of the Burgers equation by a reduced-order approach using proper orthogonal decomposition

Optimal control of vortex shedding using loworder models. Part I-Open-loop model development

A reduced-order approach for optimal control of fluids using proper orthogonal decomposition

Reliable real-time solution of parametrized partial differential equations: reduced-basis output bound methods

Output bounds for reduced-basis approximations of symmetric positive definite eigenvalue problems

A priori convergence theory for reducedbasis approximations of single-parameter elliptic partial differential equations

A posterior error estimation for reducedbasis approximation of parametrized elliptic coercive partial differential equations: "convex inverse" bound conditioners

Reduced basis approximation dand a posteriori error estimationd for the time-dependent viscous Burgers' equation

Generalized Multiscale Finite Element Methods