Abstract
Projection based methods lead to reduced order models (ROMs) with dramatically reduced numbers of equations and unknowns. However, for nonlinear or parametrically varying problems the cost of evaluating these ROMs still depends on the size of the full order model and therefore is still expensive. The Discrete Empirical Interpolation Method (DEIM) further approximates the nonlinearity in the projection based ROM. The resulting DEIM ROM nonlinearity depends only on a few components of the original nonlinearity. If each component of the original nonlinearity depends only on a few components of the argument, the resulting DEIM ROM can be evaluated efficiently at a cost that is independent of the size of the original problem. For systems obtained from finite difference approximations, the ith component of the original nonlinearity often depends only on the ith component of the argument. This is different for systems obtained using finite element methods, where the dependence is determined by the mesh and by the polynomial degree of the finite element subspaces. This paper describes two approaches of applying DEIM in the finite element context, one applied to the assembled and the other to the unassembled form of the nonlinearity. We carefully examine how the DEIM is applied in each case, and the substantial efficiency gains obtained by the DEIM. In addition, we demonstrate how to apply DEIM to obtain ROMs for a class of parameterized system that arises, e.g., in shape optimization. The evaluations of the DEIM ROMs are substantially faster than those of the standard projection based ROMs. Additional gains are obtained with the DEIM ROMs when one has to compute derivatives of the model with respect to the parameter.
Access provided by Autonomous University of Puebla. Download chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
4.1 4.1 Introduction
Projection based reduced order models systematically extract the features of very large-scale systems to approximate these systems by substantially smaller ones. However, if the original system is parameter dependent or is semilinear, then, although the new small system involves substantially fewer equations and unknowns than the original one, the computational cost of its numerical solution can be essentially the same as that of the original large-scale system. The discrete empirical interpolation method (DEIM) of [7] further approximates projection based reduced order models to obtain small systems that capture the solution of the original large-scale system and that can also be solved at a computational cost that depends only on the size of the small system, provided each component of the original semilinear function depends only on a few components of its argument. So far, the DEIM has been primarily applied to finite difference discretizations of semilinear PDEs where the ith component of the nonlinearity depends only on the ith component of the argument. This is different in finite element discretizations, where the dependence of the nonlinear function is determined by the mesh as well as by the polynomial degree used to construct the finite element spaces. Therefore results from DEIM applied to finite difference approximations of PDEs do not necessarily carry over to DEIM applied to finite element approximations of PDEs. One purpose of this paper is demonstrate two approaches to apply DEIM to finite element discretizations of semilinear PDEs and numerically study their computational cost. The two approaches apply DEIM at different stages of the finite element assembly process. The size of the nonlinear function as well as its dependence on the argument are different at each stage of the assembly process, which impacts the computational efficiency of the resulting DEIM reduced models. The second purpose of this paper is to demonstrate how to apply DEIM to a class of parameter dependent systems that arise, e.g., in shape optimization.
Discretizations of parameterized semilinear elliptic partial differential equations (PDEs) lead to large scale nonlinear algebraic systems of the form
where the parameters θ ∈ Θ ⊂ ℝp and for each parameter θ the matrix A(θ) ∈ ℝN×N and the vectors F(y; θ) and b(θ) ∈ ℝN. Projection based model reduction techniques [1, 19, 24, 29] generate matrices V ℓ and V r ∈ ℝN×n with n ≪ N and replace (4.1) with the reduced system
While the reduced order system (4.2) is much smaller than the original one, the cost of computation of θ ↦ V Tℓ A(θ)V r , θ ↦ V Tℓ b(θ), and (ŷ, θ) ↦ V Tℓ F(ȳ + V r ŷ;θ) still depends on N. Therefore, additional approximations are needed to obtain reduced order models that capture the original system as well as evaluate with a computational complexity that depends only on the reduced order system size n but is independent of the full order model size N ≫ n.
The empirical interpolation method (EIM) of [2] and the DEIM of [7] generate reduced order models from (4.2) that approximate the full order model within desired error bounds and that can be numerically solved at a cost that essentially depends only on the reduced order system size. While the EIM is applied to the variational formulation that leads to the nonlinear algebraic system (4.1), its derivative, the DEIM is applied directly to discrete systems. Applications of EIM and DEIM to nonlinear finite element computations are also discussed, e.g., in [9, 15, 17, 22]. We will focus on discrete systems (4.1) and therefore consider the DEIM. Especially, we carefully expose the dependency of the computational complexity of the DEIM on the polynomial degree of the finite element method.
One purpose of this paper is the study of DEIM to nonlinear systems Ay + F(y) = b obtained from finite element discretizations. The DEIM reduced order model is of the form \(V_\ell ^TA(\bar y\, + \,{V_r}\hat y) + \hat F(\hat y) = V_\ell ^Tb,\,where\,\hat F\) depends only on m components of the original nonlinearity F. As we have mentioned before, the efficiency with which the DEIM reduced order model can be applied depends on how many components of the argument are needed to evaluate m components of the original nonlinearity F. For systems obtained from finite element discretizations the dependence of F on its argument is determined by the mesh, as well as by the polynomial degree used to construct the finite element spaces. One can apply DEIM at different stages of the finite element assembly process. This effects the structure of the nonlinearity. We demonstrate how to apply DEIM to finite element discretizations of nonlinear PDEs in the assembled and in the unassembled form, and we numerically study the computational cost of the resulting reduced order models. Either version of the DEIM is preferable over the naive application of projection based model reduction as in (4.2). For large systems, the application of the DEIM to the so-called unassembled form of the nonlinearity leads to additional gains in the on-line cost of the reduced order models.
A second focus of this paper is the application of DEIM to generate reduced order models for parametrically dependent PDEs A(θ)y = b(θ), where A(θ) = ∑ M i=1 (θ)A i and b(θ) = ∑ M i=1 l i (θ)b i . For large M the complexity of evaluating the reduced order matrix V Tℓ A(θ)V r = ∑ M i=1 g i (θ) V Tℓ A i V r is still high. The DEIM can be used to obtain an approximation that allows more pre-computation of matrices and that can be evaluated more efficiently in the on-line phase. Additional benefits arise when derivatives of the matrix with respect to the parameter θ have to be computed, and we illustrate these gains in the context of shape optimization.
The next section describes two model problems, a semilinear elliptic advection reaction diffusion equation and the Stokes equations on a parameterized domain, and their finite element discretizations. These problems will be used to demonstrate the application of the DEIM, and to numerically evaluate the computational costs required to solve the full and the reduced order models. Section 4.3 reviews approaches to construct the reduced order subspaces spanned by the columns of the matrices V ℓ and V r ∈ ℝNxn, and it reviews the DEIM. The main contributions of this paper are presented in Sects. 4.4 and 4.5.
In Sect. 4.4 we discuss the application of the DEIM to finite element discretizations of semilinear PDEs. We illustrate how ith component of the nonlinearity depends on the components of its arguments for piecewise linear and piecewise quadratic elements, and we demonstrate how this dependence impacts the efficiency of the DEIM. In addition, we discuss the application of DEIM to the fully assembled system, as well as the unassembled form of the nonlinearity. The latter was originally suggested by [9, 33]. The nonlinear vectors are larger, but each component depends on fewer components of the argument. We describe both version of the DEIM and computationally compare them on the semilinear elliptic advection reaction diffusion model equation of Sect. 4.2.1. As we have mentioned before, either version of the DEIM is preferable over the naive application of projection based model reduction as in (4.2). For large systems, the application of the DEIM to the unassembled form of the nonlinearity is more expensive in the off-line cost, but leads to additional gains in the on-line cost of the reduced order models.
The application of the DEIM to obtain efficient reduced order models for systems with parameterized matrices A(θ) = ∑ M i=1 g i (θ)A i and vectors b(θ) = ∑ M i=1 l i(θ)b i is demonstrated in Sect. 4.5. We numerically illustrate the efficiency gains achieved by the DEIM reduced order model using the Stokes equation on parameterized domains introduced in Sect. 4.2.2. The DEIM not only leads to reduced order models that can be evaluated efficiently, but in addition it also leads to reduced order models where derivatives with respect to the parameter θ can be computed efficiently. Both efficiency gains are crucial, e.g., for shape optimization.
4.2 4.2 Model Problems
4.2.1 4.2.1 Semilinear Advection-Diffusion-Reaction PDE
Our first model problem is a semilinear advection diffusion reaction equation. Let Ω ⊂ ℝd, d ∈ {2,3} be an open, bounded Lipschitz domainwith boundary ∂Ω = Γ N ∩ Γ N , where Γ D and Γ N corresponds to Dirichlet and Neumann parts. Given a diffusion coefficient v > 0, an advection vector β ∈ ℝ d , a nonlinear function f : ℝ × ℝp → ℝ, and Dirichlet data h, the semilinear advection diffusion reaction equation is given by
We consider the specific nonlinearity
used e.g., in [11]. Here C, D are known constants and θ = (ln(A),E) are system parameters that can vary within the parameter domain Θ = [5.00,7.25] × [0.05,0.15] ℝ2.
The weak form of (4.3) is given as follows. Find y ∈ H 1 (Ω) with y = h on Γ D such that
for all v ∈ H 1 (Ω) with v = 0 on Γ D . Existence results for linear and nonlinear advection diffusion equations can be found, e.g., in [26, 32] and [23], [27, Sec. 6.3]
We discretize the equations using an SUPG (streamline upwind/Petrov-Galerkin) stabilized FEM [5, 10, 25]. The Dirichlet boundary conditions are implemented via interpolation. Let \(\{ {\Omega _e}\} _{e = 1}^{{n_e}}\) be a conforming triangulation of the domain Ω. Furthermore, let {φ j } N j=1 be the piecewise polynomial nodal basis functions. To simplify the presentation, we assume that nodes with indices 1,…,N F are in \(\bar \Omega \backslash {\Gamma _D}\) and that the nodes with indices N F + 1,…,N F + N D are in Γ D . We define
If we let h e denote the length of largest side of each element Ω e and P e = h e ∥β∥ /(2v) the mesh Péclet number, then the SUPG stabilization parameter is defined as
The solution y of (4.5) is approximated by
where y h satisfies
To state the nonlinear algebraic system corresponding to (4.8), we define
and partition the matrices and vectors into submatrices and subvectors corresponding to the free variables y F and those determined by the Dirichlet boundary conditions, (4.8) leads to a system of algebraic equations of the type
Of course, this is equivalent to A FF y F + F F (y F , h; θ) + A FD h = 0. If we set b = —A FD h, N = N F , if we drop the subscript F, and if we drop the constant h from the arguments of the nonlinearity F, then we arrive at the N × N system
which is a special case of (4.2). In this model problem, the matrix A and the vector b do not depend on the parameter θ. For later reference, we note that the matrix A, the function F, and the vector b are given by
4.2.2 4.2.2 The Stokes Equations on Parameterized Domains
As our second model problem we consider the Stokes equations posed on a family of parameterized domains Ω(θ) ⊂ ℝ2, where θ ∈ Θ ⊂ ℝp. Since our numerical examples are 2D problems we describe the approach for parameterized domains in ℝ2. However, everything can be easily generalized to the Stokes equations on parameterized domains in ℝ3. The boundary ∂ Ω = Γ D ⋃ Γ out is decomposed into an outflow boundary Γ out and Γ D = ∂Ω \ Γ out. We assume that the parameterized domains Ω(θ) can be mapped onto a reference domain \(\tilde \Omega \subset {\mathbb{R}^2}\). That is we assume that for each θ ∈ there exists a diffeomorphism Φ(·θ) with
The Stokes equations for the velocity u and the pressure p are
where f ∈ (L 2(Ω(θ)))2. The weak form of (4.13) is given as follows: Find u ∈ (H 1(Ω(θ)))2 with u = h on Γ D (θ) and p ∈ L 2(Ω(θ)) such that
for all v ∈ {φ ∈ (H 1 (Ω(θ)))2 : φ = on Γ D (θ)} and q ∈ L 2(Ω(θ)). Existence results for the Stokes equations can be found, e.g., in [12, 13].
We approximate (4.14) using Taylor-Hood P2-P1 finite elements [10]. We triangulate the reference domain \(\tilde \Omega \) and use (4.12). Let N v be the number of velocity nodes in \(\tilde \Omega \cup {\tilde \Gamma _{out}}\) and let N p be the number of pressure nodes in \(\bar \tilde \Omega \). If the piecewise quadratic basis functions for the velocities on the reference domain are \([{\tilde \phi _j},j = 1, \ldots ,{N_v}\), and the piecewise linear basis functions for the pressure on the reference domain are \({\tilde \Psi _j},j = 1, \ldots ,{N_p}\), then the basis functions for velocities and pressure on the domain Ω(θ) are
The Taylor-Hood P2-P1 finite element discretization of (4.14) leads to
where
with
and
1 ≤ j ≤ N v , 1 ≤ i ≤ N p .
We use the integral transformation as well as the structure (4.12) of the basis functions to compute
for 1 ≤ i, j ≤ N v , and
for 1 ≤ j ≤ N v 1 ≤ i ≤ N p .
Finally, we approximate the integrals by a quadrature rule with nodes \({\tilde x_i}\) and weights ω i , i = 1,…,M. To keep the presentation simple, we assume that the same quadrature rule is used for all integrals. If we define functions g k : Θ → ℝM, k = 1,…, 7, component-wise as follows
then, if the integrals are replaced by quadrature, the matrices in the Stokes system can be written as
If we insert this representation into (4.17), then
Similarly, if we replace the integrals in the right hand side vectors
by quadrature rules, then
where \({({g_{7 + k}}(\theta ))_\ell } = {\omega _\ell }{f_k}(\Phi ({\tilde x_\ell };\theta ))|\det (D\Phi ({\tilde x_\ell };\theta ))|,\,k = 1,2.\)
4.3 4.3 Projection Based Reduced Order Models
4.3.1 4.3.1 Generating the Reduced Order Model Subspaces
The computation of the matrices V ℓ, V r ∈ ℝN × n is crucial for the accuracy of the resulting reduced order model and involves some sort of sampling of the solutions to the full order model. Commonly used methods to generate these matrices include the greedy algorithm (see, e.g., [4, 6, 24, 29]), proper orthogonal decomposition (POD) (see, e.g., [19]), and, for time dependent linear problems, balanced POD (see, e.g., [1, 21, 28]). Since emphasis of this paper is the efficient evaluation of the reduced order model (4.2) using DEIM, it does not matter how V ℓ, V r ∈ ℝN × n have been generated. We assume these matrices have been generated by a suitable method. In our numerical examples, we generate V = V ℓ = V r ∈ ℝN × n using a simple sampling strategy and proper orthogonal decomposition. This often results in good reduced order models, although more sophisticated sampling strategies might have provided equally good reduced order models using fewer samples.
Since we will refer to the proper orthogonal decomposition (POD) later, we provide a few details on this method. First by POD we mean the construction of a k dimensional subspace that best approximates given samples s 1,…,s K . Thus, selection of these samples is not part of POD. We assume s 1,…,s K ∈ ℝN, but in general these samples could be vectors in a Hilbert space. See, e.g., [19]. Given the samples s 1,…,s K the POD successively computes vectors v 1,…,v K as the solution of
where δ ij is the Kronecker delta, or in matrix notation
where I k ∈ ℝk × k is the identity. Is is well known that the solution can be computed via the singular value decomposition (SVD) of S, S = V∑W T. In fact, since W is orthogonal, ∥S — V k V T k S∥ 2 F = ∥V∑ — V k V T k V∑∥ 2 F . If V k ∈ ℝN×K is submatrix consisting of the first k columns of V ∈, ℝN×N, and if ∑ k ∈ ℝN×N is obtained by replacing the singular values σ k+1, σ k+2 in ∑ ∈ ℝN×K by zero, then
(POD)
Given the bound (4.21), the index k is often chosen to be the smallest index such that ∑ min{K,N} j=k+1 σ 2 j < τ. This requires computation of all singular values, which can be expensive. Therefore, we use the smallest index k such that σ k+1 < τσ1. This alternative provides a bound on the relative error in the two-norm: ∥S — V k V T k S∥2 ≤ τ ∥S∥2. In our examples, the matrix of samples S ∈ ℝN×K satisfies K ≪ N and we compute the so-called economy-sized SVD. In the large scale setting, we can use an iterative method (e.g. ARPACK) to compute just the largest k singular values without computing all of them.
We note that often the snapshots do not have to be approximated in the Euclidean norm sense as in (4.19), but instead using a weighted dot product v T i Ms j and corresponding norm ∥s∥ 2 M = s T Ms, respectively, where M ∈ ℝN×N is a symmetric positive definite matrix. This is for example the case when the snapshots s j (x) = ∑ N i=1 s ij φ i (x) belong to the Hilbert space H 10 (Ω). In this case, M is the stiffness matrix. See, e.g., [19]. This can be accomplished by modifying the SVD.
4.3.2 4.3.2 The DEIM
In this section we review the DEIM to approximate a function G : ℝk → ℝN. We require a subspace with basis {u 1,…,u m} such that G(z) is approximately contained in span{u 1,…,u m} for the arguments z of interest. Typically, one samples G and then applies the POD to the samples to obtain an orthonormal basis {u 1,…,u m}. To obtain a computationally efficient DEIM approximation of G one needs that m ≪ N.
The DEIM [7] can be viewed as variant of the empirical interpolation method of [2] (see also [14]) applied to large scale finite dimensional systems.
The DEIM computes indices p 1,…,p m in {1,…,N… and an approximation Ĝ : ℝk → ℝN of the function G which satisfies
moreover, for each z the computation of Ĝ(z) only requires the m components \({G_{{p_1}}}(z), \ldots ,{G_{{p_m}}}(z)\) of the original function G. More specifically, if e i is the ith unit vector in \({\mathbb{R}^N},P = [{e_{{p_1}}}, \ldots ,{e_{{p_m}}}] \in {\mathbb{R}^{N \times m}}\) is the submatrix of the identity obtained by extracting the columns p 1,…,p m , and U = [u 1,…,u m ], then the DEIM approximation of G is
Clearly, P TĜ = P T G, which verifies the interpolation property (4.22), and \({P^T}G = {({G_{{p_1}}}, \ldots ,{G_{{p_m}}})^T}\), which means that only the components p 1,…,p m of G are needed to compute the approximation Ĝ. This is the source of the complexity reduction provided by the DEIM.
Before we review how DEIM computes the indices p 1,…, p m and the DEIM error bounds, we discuss when the DEIM approximation is useful. For example, in model reduction we have to evaluate the nonlinearity (ŷθ) ↦ V Tℓ F (ȳ + V r ŷ;θ), where F : ℝN × ℝp → ℝN and V ℓ and V r ∈ ℝN × n with n ≪ N. As we have mentioned, this requires the computation of ȳ + V r ŷ, the evaluation of the nonlinearity F(Fȳ + V r ŷ;θ) and the projection V Tℓ F(ȳ + V r ŷ;θ). All of these operations depend on the size N of the full system and, therefore, the evaluation of the reduced order model is almost expensive as that of the full order model. The complexity of the reduced order model can be made independent of the full order problem size N using the DEIM approximation. If we compute a DEIM approximation
then we can approximate the nonlinearity V Tℓ F(ȳ + V r ŷ;θ) by
Typically in problems arising from spatial discretization of a PDE, the ith component of F depends only on a few components of y. Hence, the evaluation of the m components P T F(ȳ+V r ŷ;θ) of the nonlinearity requires only a few, say O(m) components of ȳ+V rŷ. Hence we do not need to compute ȳ+V rŷ at a cost of 2Nn+N flops (we count multiplication and addition as a flop), but only some components of this vector at a cost of O(mn). Furthermore, the matrix V Tℓ U(P T U)-1 ∈ ℝn×m can be precomputed so that afterwards the evaluation of \((\hat y;\theta ) \mapsto V_\ell ^T\hat F(\bar y + {V_r}\hat y;\theta )\) defined in (4.23) requires only O(mn) operations. In finite difference approximations, the ith component of the nonlinearity F typically depends only on the ith component of the argument y. Finite difference approximations are used, e.g., in the examples in [7,8]. If finite element methods are used, the ith component of the nonlinearity F depends on more than the ith component of the argument. The dependency of the ith component of F on the components of the argument depends on the polynomial order used in the finite element method, on the mesh, and also in what stage of the finite element assembly process the DEIM is applied. We will explore this in Sec. 4.4.
(DEIM)
We next state an error estimate from [7] for the DEIM approximation
to G. If U ∈ ℝN×m has ortho-normal columns, then
This result indicates that very little accuracy is lost when the orthogonal projection of POD is replaced by the DEIM interpolatory projection so long as ‖(P T U)-1‖2 is of modest size. In practice, we simply compute this quantity and use it as an aposteriori estimate. The greedy DEIM index selection actually limits the growth of ‖(P T U)-1‖2 and typically it has remained on the order of 100 or less in all of the examples we have considered. Finally, we must emphasize that the DEIM does not improve the accuracy of the POD reduced model. The sole benefit of the DEIM is to greatly reduce the complexity of evaluating the reduced model.
4.4 4.4 Evaluation of Nonlinear Functions Arising in Finite Element Methods Using DEIM
We study the application of the DEIM for the evaluation of nonlinear terms in finite element models. As noted in Sect. 4.3.2, the main issue here is the computational complexity of the DEIM reduced model. It depends on how may components of the argument influence a component of the nonlinearity, and it is determined by the finite elements used. We present two ways of applying the DEIM. One approach applies DEIM to the assembled form of the nonlinear term, the other approach, originally suggested by Dedden et al. [9, 33], to the unassembled form.
We use the semilinear advection diffusion reaction equation from Sect. 4.2.1 and continuous finite element approximations. However, the approaches can easily be extended to other equations and discontinuous Galerkin methods.
4.4.1 4.4.1 The Reduced Order Model
We consider the finite element discretization of the semilinear advection diffusion reaction equation discussed in Sect. 4.2.1. To simplify our notation, we assume that the boundary data h(x) = 0 in (4.3). The finite element discretization of (4.3) leads to the N × N system of nonlinear equations
where A ∈ ℝN×N and F : ℝN × ℝp → ℝN are given by (4.11). Note that since h(x) = 0, the vector b = 0 ℝN.
Assume we have generated V ℓ and V r ∈ ℝN×n with n ≪ N. Then the reduced order model of (4.25) is
As we have mentioned before, V Tℓ AV r , V Tℓ Aŷ and V Tℓ b can be precomputed, but since the nonlinearity depends on ŷ and θ the term V Tℓ F(ȳ + V r ŷ;θ)needs to be evaluated whenever ŷ or θ changes, and the cost of evaluating this nonlinearity still depends on the size N of the full order model.
To reduce the complexity of the nonlinear term, we apply the DEIM. The DEIM reduced order model is given by
The n × m matrix V Tℓ U(P T U)-1 can be precomputed once. We still need to study the complexity of the evaluation of the nonlinearity
in the DEIM reduced model (4.27). The ith component F i of the nonlinearity depends on all components y j for which the intersection of the support of basis functions φ i and φ j does not have measure zero. See (4.11b).
Left plot: Piecewise linear finite elements on triangles. If the DEIM index p i corresponds to the vertex indicated by the large dot, then the p i th component of the nonlinear function depends on the seven adjacent vertices indicated by dots. Right plot: Piecewise quadratic finite elements on triangles. If the DEIM index p i corresponds to the vertex indicated by the large dot, then the p i th component of the nonlinear function depends on nineteen adjacent nodes indicated by dots. If the DEIM index p i corresponds to the midpoint indicated by the large dot, then the p i th component of the nonlinear function depends on nine adjacent nodes indicated by dots
This is illustrated in Fig. 4.1 for piecewise linear (left plot) and piecewise quadratic (right plot) basis functions φ i on triangles. In the case of piecewise linear basis functions, there are N = 36 degrees of freedom, which correspond to the vertices. If the DEIM index p i corresponds to the vertex indicated by the large dot, then the p i th component of F depends on seven components of y, which corresponds to the vertices indicated by dots. If piecewise quadratic basis functions are used, then there are N = 121 degrees of freedom, which correspond to the vertices and edge midpoints. If the DEIM index p i corresponds to the vertex indicated by the large dot, then the p i th component of F depends on nineteen components of y, which corresponds to the vertices and edge midpoints indicated by dots in the bottom right part of the right plot in Fig. 4.1. On the other hand, if the DEIM index p i corresponds to a midpoint, then this midpoint is shared by only two triangles, and the p i th component of F depends on nine components of y, which corresponds to the vertices and edge midpoints indicated by dots in the top left part of the right plot in Fig. 4.1.
An alternative DEIM reduced order model is obtained when we consider the unassembled nonlinearity. As we have mentioned earlier, this was first suggested and explored by [9, 33]. Since \({\smallint _\Omega } = \sum _{e = 1}^{{n_e}}{\smallint _{{\Omega _e}}}\), we can write (4.11b) as
When the intersection of the supports of the basis functions φ i and φ j and of the element Ω e has measure zero, the integral \(\sum _{j = 1}^N{y_j}{\phi _j};\theta \) is zero. Therefore for nodal basis functions, this integral can only be nonzero when the indices i and j correspond to nodes in \({\bar \Omega _e}\). For each of the n e elements Ω e we can compute n p integrals
where n p is the number of degrees of freedom per element and the indices i corresponds to nodes in the element \({\bar \Omega _e}\). This gives a function \({F^e}(y;\theta ):{\mathbb{R}^{{n_e}{n_p}}} \times {\mathbb{R}^p} \to {\mathbb{R}^{{n_e}{n_p}}}\). Then we can assemble the element information into the global vector of unknowns F. This can be expressed as
where \(Q \in {\mathbb{R}^{N \times ({n_e}{n_p})}}\). The size of the unassembled nonlinearity F e is larger than that of the assembled one F. If the ith component of the unassembled nonlinearity belongs to element Ω e , then F e i only depends on the unknowns y j with indices j corresponding to nodes in the element Ω e , see Fig. 4.2. Consequently, a component of unassembled nonlinearity depends on fewer components than a component of assembled nonlinearity does.
If DEIM is applied to unassembled piecewise linear elements, then the p i -th component of the unassembled nonlinearity only depends on values at nodes in the element that contains the node p i . Left plot: For piecewise linear elements on triangles, the p i -th component of the unassembled nonlinearity only depends on the values at the three vertices, indicated by dots, of one triangle. Right plot: For piecewise quadratic elements on triangles, the p i -th component of the unassembled nonlinearity only depends on the values at the vertices and edge midpoints, indicated by dots, of one triangle
The reduced order model (4.26) can now be written as
We can apply DEIM to the unassembled nonlinearity. Let the columns of \({U^e} = [u_1^e, \ldots u_{{m^e}}^e]\) be a basis of a subspace that approximately contains F e(y;–) for the arguments y and θ of interest. The DEIM approximation of the unassembled nonlinearity is given by
Here P e is the sub matrix of the identity generated using the indices \(p_1^e, \ldots p_{{m^e}}^e\) generated by the DEIM applied to \(u_1^e, \ldots u_{{m^e}}^e\).
If we insert this into (4.29) we arrive at the DEIM reduced order model
The n × m e matrix V Tℓ QU e((P e)T(U e))-1 can be precomputed.
The advantage of the DEIM reduced order model (4.30) over (4.27) is that each component of the unassembled nonlinearity in (4.30) depends on fewer components of the argument than the nonlinearity in (4.27) does. Hence, if the dimension of the subspace ℛ(U) containing the image of F is roughly equal to dimension of the subspace ℛ(U e) containing the image of F e, i.e., if m ≈ m e, then the evaluation of (4.30) is computationally less expensive than that of (4.27). This is illustrated in Fig. 4.2. If a DEM point p i corresponds to a node in a triangle, the the p i th nonlinearity depends on all components of the argument that correspond to nodes in the triangle. The left plot in Fig. 4.2 illustrates this for one point when piecewise linear elements are used, whereas the right plot in Fig. 4.2 illustrates this when piecewise quadratic elements are used. Note, that if the unassembled form of the nonlinearity is used, the connectivity is the same no matter whether the DEIM point corresponds to an vertex or an edge midpoint.
The disadvantage of the DEIM reduced order model (4.30) compared to (4.27) is that the size of the unassembled nonlinearity F e(y;;) is significantly larger than the size N of the nonlinearity F(y;θ). The size n e n p of the unassembled nonlinearity F e(y;;) now depends on the number n e of elements and the number n p of degrees of freedom n p per element. For example, if we use piecewise linear basis functions on the mesh in the left plot in Fig. 4.1, there are N = 36 vertices, where as n e n p = 150. If we use piecewise quadratic basis functions on the mesh in the right plot in Fig. 4.1, then there are N = 121 degrees of freedom, whereas n e n p = 300. Since the vectors u 1,…,u m and
are typically computed from a POD of samples of the nonlinearities F and F e, respectively, the computation of the vectors
is more expensive than the computation of u 1,…,u m . However, this computation is done in the off-line phase.
4.4.2 4.4.2 Numerical Examples
We apply DEIM reduced order models to approximate the semilinear advection diffusion reaction equation (4.3) with nonlinearity (4.4). The full order model is obtained using the SUPG stabilized finite elements reviewed in Sect. 4.2.1. The diffusivity is v = 5.10-6, and the parameters C = 0.2 and D = 0.4 in (4.4) are fixed and θ = (ln(A),E) vary within Θ ≡ [5.00,7.25] × [0.05,0.15] ⊂ ℝ2.
To construct the reduced basis matrices V = V ℓ = V r , we sample the finite element solution of (4.4) at 25 parameters. We denote these solutions by y(θ),…,y(θ25).We compute the mean \(\bar y = \tfrac{1}{{25}}\sum _{i = 1}^{25}y({\theta _i})\), and generate the reduced basis matrices V = V ℓ = V r by applying the POD, Algorithm 4.1 to the samples y(θ 1) — ŷ,…,y(θ 25) — ŷ with tolerance τ = 10-4. To construct U = [u 1,…,u m ] and \({U^e} = [u_1^e, \ldots ,u_{{m^e}}^e]\) for the DEIM approximation, we sample the nonlinearities F(y(θ);θ) and F e (y(θ);θ), respectively, at the same parameters used to construct V, and then we apply the POD with tolerance τ = 10-4 to obtain U and U e , respectively.
All computations in this subsections were done using Matlab on MacBook Air with 8GB of memory and 1.8 GHz Intel Core i5 processor. The nonlinear full order or reduced order models are solved using Newton’s method. The linear systems in Newton’s method are solved using the Matlab backslash command.
4.4.2.1 4.4.2.1 2D Example
We consider the domain Ω ⊂ ℝ2 shown in Fig. 4.3, taken from [3]. The Dirichlet boundary segments are Γ D = {(0,x 2) : x 2 ∈ (0,2) ⋃ (2.75, 4.25) ⋃ (5,7)} and the Dirichlet data h is specified in Fig, 4.3.
2D Example: The domain Ω with Dirichlet boundary segments Γ D = {(0,x 2) : x 2 ∈ (0,2) ⋃ (2.75, 4.25) ⋃ (5,7)} and Dirichlet data h
To study the computational cost of applying DEIM reduced order models we use three meshes, referred to as Mesh 1 to Mesh 3, of different sizes, and we use piecewise linear and quadratic elements. We compute an approximate solution of (4.3) at the parameter (ln(A),E) = (6.4,0.11) not contained in the parameter sample. Figure 4.4 shows the triangulation corresponding to Mesh 2, of medium size, as well as the full order model solution of (4.3). (The reduced order model solutions are indistinguishable from the full order model solution.)
2D Example:A triangulation of the domain Ω (top plot) and solution of the advection diffusion reaction equation (4.3) with parameter (ln(A),E) = (6.4,0.11) (bottom plot)
As we have described in the previous section, the complexity of evaluating DEIM reduced order models depends on the connectivity of the nodes in the finite element mesh. We illustrate this in Fig. 4.5 using Mesh 2. For four different configurations, we plot the triangles that are involved in the evaluation of the DEIM nonlinear term. More precisely, the degrees of freedom corresponding to all nodes in the red solid triangles are needed to evaluate the DEIM nonlinear term. The top two plots correspond to piecewise linear finite elements using the assembled (top plot) and unassembled (second from top plot) form of the nonlinearity. The top two plots in Fig. 4.5 correspond to the schematic plots on the left in Figs. 4.1 and 4.2, respectively.
2D Example: The triangles that contain DEIM points are shown in solid red. The different plots correspond to different polynomial degree used in the FEM and application of the DEIM to the assembled or unassembled form of the nonlinearity
The bottom two plots in Fig. 4.5 correspond to quadratic finite elements. If we look at the third plot from the top, which colors the triangles involved in the evaluation of the DEIM nonlinear functions (assembled form), then at most two triangles are connected. This means that all DEIM points in this case correspond to edge midpoints (see the right plot in Fig. 4.2). We observed the same for the computations on Mesh 1 and Mesh 3. The bottom plot in Fig. 4.5 corresponds to the unassembled form of the DEIM using quadratic finite elements. In this plot a few adjacent triangles are colored red, which simply means that the DEIM selected points that happen to correspond to nodes in adjacent triangles.
Table 4.1 summarizes the problem size for the different models for the three meshes and piecewise linear and quadratic finite elements. In Tables 4.1 to 4.3, DEIM refers to the DEIM reduced order model (4.27) obtained using the assembled form of the nonlinearity, whereas DEIM-u refers to the DEIM reduced order model (4.30) obtained using the unassembled form of the nonlinearity.
The computing times to evaluate the full and the various reduced order models are shown in Table 4.2. The nonlinear systems are solved using Newton’s method and the computing times listed are for the Newton solve (and not for one Newton iteration). The number of Newton iterations required are shown in parenthesis. The computing times do not include the time needed to compute the matrices V, U, or U e via POD.
In this application, the solution of the POD-DEIM-u reduced order model required more Newton iterations in several cases, offsetting the gain in computational complexity of the POD-DEIM-u reduced order model nonlinearity. Another issue that makes computing time comparisons difficult using Matlab is that the computing time is often not determined by how many floating point operations are executed, but instead by how well the code is vectorized. We have made a great effort to vectorize the code for all models as much as possible, this is more effective for the full order and the POD reduced order models because by design the POD-DEIM and POD-DEIM-u reduced order models work with shorter vectors. Therefore the Matlab timings for the smaller problems likely do not accurately reflect what would be observed with, say, C code. However, from the Table 4.2 we can infer that POD reduced order models are only slightly more computationally efficient than the full order model. Applying DEIM for the assembled or unassembled form of the nonlinearity results in significant computational savings compared to both the full and the POD reduced order models when applied to larger problems. For larger problems the POD-DEIM-u reduced order model nonlinearities can be evaluated more efficiently than the POD-DEIM reduced order model nonlinearities. Different reduced order models may require different numbers of Newton iterations. In this example, the number of Newton iterations needed to solve the POD-DEIM-u reduced order model was at least as large as the number of Newton iterations needed to solve the POD-DEIM reduced order model. If the Newton iterations needed to solve the PODDEIM- u reduced order model is larger, then the gains in efficiency of evaluating the nonlinearity is offset by the larger number of Newton iterations.
The errors between the full order model solution and the reduced order model solutions shown in Table 4.3 are of the order of the tolerance τ = 10-4 used to construct the bases with the POD.
4.4.2.2 4.4.2.2 3D Example
The domain is the cube Ω = (0,18) × (0,9) × (0,9) (in [mm]). The left face ∂Ω D = {0} × [0,9] × [0,9] is the Dirichlet boundary, all other faces corresponds to Neumann boundaries ∂Ω N . On the part {0} × [3,6] × × [3,6] of the Dirichlet boundary we impose the Dirichlet conditions y = 0.2 and on the remainder of ∂Ω D impose y = 0. This is the problem setup used in [11].
For the numerical solution, we use SUPG stabilized piecewise linear FEM on tetrahedra. To discretize the domain, Ω is divided into cubes of size h × h × h and then each cube is divided into six tetrahedra.We use three meshes, Mesh 1 to Mesh 3, with h = 1.125, h = 0.5625, and h = 0.375, respectively. Mesh 2 is shown in the left plot in Fig. 4.6. The full order model solution of (4.3) parameter (ln(A),E) = (6.4,0.11) is shown in the right plot in Fig. 4.6. (The reduced order model solutions are indistinguishable from the full order model solution.) For reasons explained below, we only apply piecewise quadratic finite elements on Meshes 1 and 2, but not on Mesh 3.
3D Example: Partitioning of the domain Ω into tetrahedra (left plot) and solution of the advection diffusion reaction equation (4.3) with parameter (ln(A),E) = (6.4,0.11) (right plot)
Figure 4.7 shows the tetrahedra in Mesh 2 that contain a node corresponding to a DEIM point. The plots in the left column correspond to the DEIM applied to the assembled form of the nonlinearity. In case of quadratic elements, the nodes are either vertices or are edge midpoints. If we use Mesh 1, only one of the 21 DEIM points corresponds to a vertex. If we use Mesh 2, then none of the 21 DEIM points corresponds to a vertex. Since vertices are shared by more tetrahedra than edge midpoints, this means that DEIM points corresponding to edge midpoints lead to DEIM reduced order nonlinearities that can be evaluated more efficiently.
3D Example: Partitioning of the domain Ω into tetrahedra (left plot) and solution of the advection diffusion reaction equation (4.3) with parameter (ln(A),E) = (6.4,0.11) (right plot)
Table 4.4 summarizes the problem size for the different models for the three meshes and piecewise linear and quadratic finite elements. As before, in Tables 4.4 to 4.6, DEIM refers to the DEIM reduced order model (4.27) obtained using the assembled form of the nonlinearity, whereas DEIM-u refers to the DEIM reduced order model (4.30) obtained using the unassembled form of the nonlinearity.
The computing times to evaluate the full and the various reduced order models are shown in Table 4.5. Again, the computing times listed are for the entire Newton solve (and not for one Newton iteration). The number of Newton iterations required are shown in (in parenthesis). The computing times do not include the time needed to compute the matrices V, U, or U e via POD.
Table 4.4 shows that in the 3D case the DEIM applied to the unassembled form leads to nonlinear terms in the reduced order models which depend on significantly fewer components of the arguments than the nonlinear terms resulting from the DEIM applied to the assembled form. Table 4.5 shows that the POD-DEIM-u reduced order models are computationally more efficient than the POD-DEIM reduced order models, even if their solution required one more Newton iteration. The POD reduced order model leads to greater computational savings over the full order model in the 3D case compared to the 2D case (see Table 4.2). This is due to the computing time needed to solve the sparse linear systems in Newton’s method. As before, significant reductions in computing times can only be achieved after DEIM is applied (either to the assembled or the unassembled form of the nonlinearity).
For 3D problems, the cost of solving the large sparse linear systems arising in Newton’s method using the sparse LU decomposition is significant, especially for finer meshes and for piecewise quadratic elements. For the larger problems, it is likely beneficial to replace the direct solvers by iterative solvers. For this reason we have not included results for quadratic elements on the fine Mesh 3. The solution of the full order model using the sparse LU decomposition would have made the full order model solution artificially costly. Switching to iterative solvers for some discretizations would have raised the question what the ‘best’ iterative solver is. Therefore, we have limited our computational tests, to cases where the use of direct solvers still seems to be justifiable.
As in the 2D case, the errors between the full order model solution and the reduced order model solutions shown in Table 4.6 are of the order of the tolerance τ = 10-4 used to construct the bases with POD.
4.5 4.5 Evaluation of Parameterized Matrices and Vectors in Reduced Order Models Using DEIM
In this section we describe the use of the DEIM for the generation of efficient reduced order models that involve parameterized matrices. We first describe the approach applied to a generic matrix A(θ) and afterwards we apply it to the solution of Stokes equation in parameterized domains.
4.5.1 4.5.1 The Reduced Order Matrix
We consider a parametrically dependent matrix A(θ) that has the representation
with functions g = (g 1,…,g M )T : → ℝM and matrices A i ∈ ℝN×N, i = 1,…,M. As we have seen in Sect. 4.2.2 this is, e.g., the case when A(θ) is the stiffness matrix of a parametrically varying linear PDE. In this subsection A(θ) is a generic matrix. In the next subsection we will apply the reduction technique to the parametrically dependent Stokes system (4.16).
If we have computed the matrices V Tℓ A i V r then the system matrix for the reduced order model is given by
If M is small, we can precompute the matrices V Tℓ A i V r and for each θ we can use (4.32) to compute V Tℓ A(θ)V r in n 2 M operations. However, if M is large, which is the case, e.g., in the example in Sect. 4.2.2 an additional approximation is needed to allow for a fast computation of an approximation of V Tℓ A(θ)V r. We can apply the DEIM.
The DEIM computes a matrix U ∈ ℝM×m of rank m and a function
such that
We assume m ≪ M
If we insert (4.33b) into (4.32), we obtain
The matrices ∑ M i=1 U ij V Tℓ A i V r ∈ ℝn×n, j = 1,…,m can be precomputed. Afterwards, for each θ the reduced order matrix
can be computed at a cost of n 2 m ≪ n 2 m operations. Under the assumption that b(θ) has a decomposition similar to (4.31), we can easily extend the ideas from reduction to M(θ) in (4.35) to b(θ). We have omitted those details to avoid repetition.
We note that the approximation presented previously can be generalized if A(θ) is of the form
by applying the previous techniques to each of the functions g j = (g 1j ,…,g Mj )T, j = 1,…,K.
In many applications we also need to compute the derivative of the matrix A(θ) with respect to θ. If the function g is differentiable, then the derivative of A(θ) is given by
and requires the evaluation of the derivative of all M functions g 1,…,g M . The same is true for the derivative of (4.32). The derivative of the DEIM reduced matrix,
only requires the evaluation of the m ≪ M functions \({\tilde g_1}, \ldots ,{\tilde g_m}\). From (4.33) we have that
since P T just extracts the m rows from D θ g that corresponding to the DEIM indices p 1,…,p m . Thus evaluating the derivative D θ Â(θ) of the DEIM reduced matrix, requires the derivative of only m ≪ M functions \({g_{{p_1}}}, \ldots ,{g_{{p_m}}}\).
4.5.2 4.5.2 Numerical Example
We illustrate the DEIM approximation of parametrized matrices and vectors on the example of evaluating the objective function and its derivative in shape optimization of Stokes equation.
Suppose we want to minimize the functional
where the velocities u(θ) and pressure p(θ) are the solution of the Stokes equation (4.13). The function l will be specified later.
We assume that the domains Ω(θ) are obtained by mapping a reference domain as shown in (4.12). Furthermore, we discretize the Stokes equation using P2-P1 finite elements as described in Sect. 4.2.2. The discretized Stokes system is given by
where S(θ) has the form (4.18). In our examples, the forcing function f in (4.13) is zero. Therefore, the right hand side b is determined by the S(θ) and the in homogenous Dirichlet data on the velocity in (4.13). The Stokes matrix S(θ) in (4.18) has the same structure as the generic matrix S in (4.36). Since the forcing function f in (4.13) is zero, no additional parameterization of the right hand side b(θ) is needed.
Applying the domain mapping, the P2-P1 finite element discretization, and the quadrature formula from Sect. 4.2.2 to the objective (4.39) gives the discrete objective functional
where u h is the piecewise quadratic FEM approximation of the velocity and p h is the piecewise linear FEM approximation of the pressure. The objective (4.41) depends on θ via the function g 8 : Θ → ℝM defined by
Since the discretized velocity and pressure u h and p h are determined by their coefficients u and p, we can write the discrete objective functional (4.41) as
Note that its parameter dependence has the same structure as that of the generic matrix and therefore DEIM can be applied to reduce the computational cost. As in Sect. 4.2.2 we set
To summarize, we want to minimize
where y(θ) solves (4.40). In many minimization problems there will be additional constraints on the parameter or on the velocities or pressures. Since we focus on the evaluation of reduced order models, we focus on the evaluation of J h (θ) and on its gradient.
The evaluation of the objective function requires the following steps. \({J_1}\): Assemble S(θ) and b(θ) and solve the state equation S(θ)y = b(θ) for y(θ). \({J_2}\): Compute J h (θ) = l(y(θ))T g 8(θ).
We briefly summarize the computation of the gradient of J h (θ) via the adjoint approach, see, e.g., [18, Sec. 1.6]. We define the Lagrangian functional
We assume that the objective has already been computed, i.e., that S(θ) and b(θ) have been assembled and that y(θ) has been computed. Then the computation of the gradient requires the following steps. \({G_1}\) \({G_1}\): Solve the adjoint equation S(θ)Tλ = — D y l(y(θ))T g 8(θ) for λ(θ). \({G_2}\) Compute ∇J h (θ) = l(y(θ))T D θ g 8(θ) + λ(θ)T (D θ S(θ)y(θ) — D θ b(θ)).
To construct the reduced basis for the state equations (4.40), we sample the solution of the discrete Stokes (4.40) at r samples in the parameter domain Θ. We then apply the POD Algorithm 4.1 with tolerance τ individually to the snapshots for the x 1 - and x 2-components of the velocity and the snapshots for the pressures. If N v are the degrees of freedom for the x 1 - and x 2-components of the velocity and N p are the degrees of freedom for the pressure, the POD generates matrices \({V_{{v_1}}} \in {\mathbb{R}^{{N_v} \times {n_{{v_1}}}}},\,{V_{{v_2}}} \in {\mathbb{R}^{{N_v} \times {n_{{v_2}}}}}\), and \({V_p} \in {\mathbb{R}^{{N_p} \times {n_p}}}\). The reduced order Stokes matrix and right hand side are
and
The preliminary version of the reduced order Stokes system is
Since the b 3 component of the right hand side (4.16) of the discrete Stokes equation is nonzero, the velocity snapshots are not divergence free (in the discrete sense). Therefore, as already noted in [30], there is no guarantee that the reduced Stokes matrix (4.43) satisfies an inf-sup condition. In [30] a procedure is proposed that enriches the velocity subspaces to guarantee the inf-sup condition. Instead we monitor the infsup constant corresponding to (4.43) by computing the singular values of the small matrix \(\hat B(\theta ) = {(V_p^T{B^{(1)}}(\theta ){V_{{v_1}}},\quad V_p^T{B^{(2)}}{V_{{v_2}}})^T}\) and found that no enrichment of the velocity space was needed in our example.
The matrix S(θ) has the structure (4.18). Since in our examples the forcing function f in (4.13) is zero, no additional parameterization of the right hand side b(θ) is needed. We apply the DEIM as described in the previous Sect. 4.5.1 to obtain a DEIM reduced order matrix Ŝ(θ) and right hand side vector \(\hat b(\theta )\). Specifically, the reduced bases, the matrices U for the nonlinear terms g 1,…,g 8 are constructed by sampling these nonlinearities at the same parameters used to construct the reduced basis \({V_{{v_1}}},{V_{{v_2}}}\) and V p and then applying POD with tolerance τ to get matrices U for the DEIM. We apply DEIM to each of the eight functions g 1,…,g 8 separately, i.e., for each of the eight functions we generate a matrix U. Applying the DEIM approximation of Sect. 4.5.1 we obtain the DEIM reduced order system
Furthermore, applying DEIM to the function g8 in the objective, i.e., approximating
where
leads to the reduced order objective
where ŷ(θ) is the solution of (4.45). In our applications, l is affine linear or quadratic in y, so that fast computation of \(\hat y \mapsto l{(V\hat y)^T}{U_8}{\tilde g_8}(\theta )\) is possible.
All computations were done using Matlab on a MacBook Pro with 8GB of memory and a 2.53 GHz Intel Core 2 Duo processor. The nonlinear full order or reduced order models are solved using Newton’s method. The linear systems are solved using the Matlab backslash command. The θ derivatives are computed using INTLAB Version 5.5 [31].
4.5.2.1 4.5.2.1 Evaluation of Drag Generated by Parameterized Airfoil
The drag on the boundary portion is Γdrag(θ) ⊂ ∂Ω(θ) is defined by
where u ∞ = U ∞û∞ is the velocity of the incoming flow, û∞ is the unit vector directed as the incoming flow, U ∞ is constant, and L is the characteristic length of the body. See, e.g., [16,20]. As usual, we use the Stokes equations (4.13) to find an equivalent formula for the drag that avoids integration over the boundary. We use a function v ∞ ∈ (H 1(Ω(θ)))2 with v ∞ = û∞ on Γdrag(θ) and v ∞ = 0 on ∂Ω(θ) \ Γdrag(θ) as a test function in (4.13) to obtain
Hence,
We use C D as our objective functional for this example, i.e., in this example J in (4.39) is given by (4.48).
The domain Ω(θ) (for θ = 0.5) is sketched in Fig. 4.8 and has the boundary ∂Ω(θ), where Γin = {−6} } (−3,5), Γ D = ((−6,6) × {−3}) ∪ ((−6,6) × {5}, Γ out = {6} × (−3,5) and Γ drag(θ) is the boundary of airfoil. We specify an inflow velocity h = 1, on Γ in and a constant viscosity v = 0.1. The forcing function f in (4.13) is taken to be zero. We assume that the airfoil is of unit length, and the boundary has the following parameterization,
where for θ ∈ [0, 2]
The reference domain \(\tilde \Omega \) for the NACA airfoil 4-digit family. The DEIM points (quadrature points) are contained in the triangles marked in solid red
The diffeomorphism Φ that is used to map the reference domain , is given by
for \({\tilde x_1} \in [0,1]\) and \(\Phi (({\tilde x_1},{\tilde x_2});\theta ) = ({\tilde x_1},{\tilde x_2})\) else. The reference domain is \(\tilde \Omega = \Phi (( - 6,6) \times ( - 3,5);0.5)( = \Omega (0.5))\) and is shown in Fig. 4.8
The problem is discretized using P2-P1 Taylor Hood elements as described in Sect. 4.2.2. We compute 25 snapshots each for both the solution to the state equations and the nonlinear terms. The reduced basis are generated using the POD with a tolerance τ = 10−6.
We evaluate C D (see (4.47)) and its derivative with respect to θ at an arbitrary point \(\theta = \sqrt 2 \in \Theta \), which is not in the snapshot set. Table 4.7 summarizes the size of the full and the reduced order systems for three finite element grids using the full order model, the POD reduced order model and the POD-DEIM reduced order model. The mesh in Fig. 4.8is the coarse Mesh 1. The DEIM points (quadrature points) chosen are contained in the triangles marked in red.
The computing times to evaluate the objective function (\(step\,{J_1} + {J_2}\)) and its gradient (\(step\,{G_1} + {G_2}\)) for the full order model and the reduced order models are shown in Table 4.8. For the reduced order models the times do not include off-line cost. Most of the computational cost in computing objective functional occurs in . Computing the gradient requires solving the adjoint equations (\(Step\,{G_1}\)) and the sensitivities of system matrices and the objective functional (\(Step\,{G_2}\)) with respect to the shape parameter θ. Since this example only involves a scalar parameter, for the full order model \(Step\,{G_1}\) is the most expensive step in the evaluation of the gradient of objective functional. The cost of sensitivities increases with the number of parameters, see Sect. 4.5.2.2
The errors between the full order model (objective functional C D ) and the reduced order model solutions shown in Table 4.9 are of the order of the tolerance τ = 10−6 used to construct the bases with the POD. The error in gradient computation is slightly higher, due to the fact that adjoint solutions have not been taken into account to generate the reduced bases. This accuracy can be easily improved by enriching the snapshot set.
4.5.2.2 4.5.2.2 Channel with Parameterized Top and Bottom Wall
In our second example we consider a channel in which the bottom and top boundaries are parameterized using Bézier curves. The reference domain is \(\tilde \Omega = {( - 1,1)^2}\)\. The bottom and top wall of the channel are parameterized by Bezier curves with p T control points for the top boundary and p B control points for the bottom boundary. Thus the physical domain Ω(θ) is parameterized by θ ∈ Θ ⊂ ℝp, = p T + p B .
The boundary ∂Ω(θ) is decomposed into the inflow and outflow boundaries Γ in (θ) = {−1} × (−1,1), and Γ out (θ) = {1} × (−1,1), both of which are independent of the parameterization and the top and bottom boundaries Γ t (θ) and Γ b (θ). The viscosity is v = 1.0. On the inflow boundary Γ t we specify an parabolic inflow velocity h = 8(1 + x2)(1.x2). The velocity h = 0 on Γ t (θ) and Γ b (θ). The forcing function f in (4.13) is taken to be zero.
We use p T = p B = 2 Bézier control points to specify the top and the bottom boundary of the variable domain Ω(θ). The parameters are in Γ = (0.5, 3.0) × (0.5, 3.0) × (−3.0, −0.5) × (−3.0, −0.5)
For this example the objective functional is
where u are the velocities computed as the solution of the Stokes equations (4.13) on Ω(θ). The functions u d are the desired velocities computed by solving the stokes equation on Ω(θ d) with fixed parameter θ d = (1.0,0.5,−0.5−1.0)T.
The problem is discretized using P2-P1 Taylor Hood elements as described in Sect. 4.2.2. To construct the reduced basis, we compute 54 snapshots in the parameter domain Θi.e., we take 5 sample points in each direction. Then we apply Algorithm 4.1 with tolerance τ = 10−4 to construct the reduced basis, as before.
We evaluate J and its derivative with respect to θ at an arbitrary point \(\theta = {(\sqrt 2 ,\sqrt 2 , - \sqrt 2 , - \sqrt 2 ,)^T} \in \Theta \), which is not in the snapshot set. Table 4.10 summarizes the size of the full and the reduced order systems for three finite element grids using the full order model, the POD reduced order model and the POD-DEIM reduced order model.
The mesh in Fig. 4.9 is the coarse Mesh 1. The DEIM points (quadrature points) chosen are contained in the triangles marked in red. The computing times to evaluate the full and the various reduced order objective (\(Step\,{J_1} + {J_2}\)) and its gradient (\(Step\,{G_1} + {G_2}\)) are shown in Table 4.8. For the reduced order models the times do not include off-line cost. As in the previous example, most of the computing cost for the computation of the objective function occurs in step \({J_1}\), the assembly and solution of the state equation. Computing the gradient requires solving the adjoint equations (\(Step\,{G_1}\)) and the sensitivities of system matrices and the objective functional (\(Step\,{G_2}\)) with respect to the shape parameter θ. We observe that in this example and for the full order model, Step \({G_2}\) is the most expensive step in the evaluation of the gradient of the objective functional. This is due to the fact that we have four parameters.
The reference domain \(\tilde \Omega \) for the channel example. The top Γ T and bottom Γ B boundaries are parameterized by p T = 2 and p B = 2 Bézier control points respectively. The DEIM points (quadrature points) lies in the interior of the triangles marked in solid red
The errors between the full order model (objective functional C D and its gradient) and the reduced order model solutions shown in Table 4.12 are of the order of the tolerance τ = 10−4 used to construct the bases with the POD.
4.6 4.6 Conclusions
We have demonstrated the application of the DEIM to compute reduced order models for finite element discretizations of seminar elliptic PDEs and for parameterized linear systems that arise, e.g., in shape optimization, and we have studied the computational efficiency of the resulting reduced order models.
The efficiency with which DEIM reduced order models of discretized semilinar elliptic PDEs can be evaluated is determined by how many components of the argument each component of the nonlinearity depends on. For finite element discretizations this dependence is determined by the mesh, the polynomial degree used in the finite element approximation, but also by whether the nonlinearity is defined in its assembled or unassembled form. For nodal based finite element methods, each component of the unassembled form of the nonlinearity depends only on the components associated with the degrees of freedom corresponding to one element. This is different for the assembled form of the nonlinearity. Here a component of the nonlinearity can depend on the degrees of freedom in several adjacent elements. More precisely, if the component of the nonlinearity corresponds to a node on the boundary of an element, then this component of the nonlinearity depends on all degrees of freedom in the elements that share this node. Because of the dependence of the components of the nonlinearity on the components of its argument, the unassembled form is attractive for DEIM. Since DEIM applied to the different forms of the nonlinearity generates different reduced order models, which require different numbers of Newton iterations to solve, the dependency of the nonlinearity on its argument alone cannot be used to decide which form of the DEIM is favorable. Our numerical examples have shown that either version of the DEIM is preferable over the naive application of projection based model reduction. For large systems, the application of the DEIM to the unassembled form of the nonlinearity led to additional gains in the on-line cost of the reduced order models. The off-line cost of DEIM applied to the unassembled form of the nonlinearity is always higher (and can be significantly higher) since the unassembled form results in a nonlinear vector valued function that has significantly more components than the nonlinear vector valued function arising in the assembled form.
A second focus of this paper was to demonstrate the application of the DEIM to compute reduced order models for an important class of parameterized linear systems. The DEIM not only leads to reduced order models that can be evaluated efficiently, but in addition the derivatives of the reduced order models with respect to the parameter can be computed efficiently. Both efficiency gains are crucial, e.g., for shape optimization. We have demonstrated this numerically using the Stokes equations on parameterized domains.
References
Antoulas, A.C.: Approximation of large-scale dynamical systems, Advances in Design and Control, vol. 6. Society for Industrial and Applied Mathematics, Philadelphia, PA (2005)
Barrault, M., Maday, Y., Nguyen, N.D., Patera, A.T.:An ‘empirical interpolation’ method: application to efficient reduced-basis discretization of partial differential equations. C. R. Math. Acad. Sci. Paris 339(9), 667–672 (2004)
Becker, R., Braack, M., Vexler, B.: Numerical parameter estimation for chemical models in multidimensional reactive flows. Combust. Theory Modelling 8, 6 (2004)
Binev, P., Cohen, A., Dahmen, W., DeVore, R., Petrova, G., Wojtaszczyk, P.: Convergence rates for greedy algorithms in reduced basis methods. SIAM J. Math. Anal. 43(3), 1457–1472 (2011)
Brooks, A.N., Hughes, T.J.R.: Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations. Comp. Meth. Appl. Mech. Engng. 32, 199–259 (1982)
Buffa, A., Maday, Y., Patera, A.T., Prud’homme, C., Turinici, G.: A priori convergence of the greedy algorithm for the parametrized reduced basis method. ESAIM Math. Model. Numer. Anal. 46(3), 595–603 (2012)
Chaturantabut, S., Sorensen, D.C.: Nonlinear model reduction via discrete empirical interpolation. SIAM Journal on Scientific Computing 32(5), 2737–2764 (2010)
Chaturantabut, S., Sorensen, D.C.: Application of POD and DEIM on dimension reduction of non-linear miscible viscous fingering in porous media. Math. Comput. Model. Dyn. Syst. 17(4), 337–353 (2011)
Dedden, R.J.: Model order reduction using the discrete empirical interpolation method. Master’s thesis, Technical University Delft, Netherlands, 2012. Available from http://repository.tudelft.nl (accessed Dec. 31, 2012)
Elman, H.C., Silvester, D.J., Wathen, A.J.: Finite Elements and Fast Iterative Solvers with Applications in Incompressible Fluid Dynamics. Oxford University Press, Oxford (2005)
Galbally, D., Fidkowski, K., Willcox, K., Ghattas, O.: Nonlinear model reduction for uncertainty quantification in large-scale inverse problems. Internat. J. Numer. Methods Engrg. 81(12), 1581–1603 (2010)
Galdi, G.P., Simader, C.G., Sohr, H.: On the Stokes problem in Lipschitz domains. Ann. Mat. Pura Appl. (4) 167, 147–163 (1994)
Girault, V., Raviart, P.-A.: Finite element methods for Navier-Stokes equations. Theory and algorithms, volume 5 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin Heidelberg (1986)
Grepl, M.A., Maday, Y., Nguyen, N.C., Patera, A.T.: Efficient reduced-basis treatment of nonaffine and nonlinear partial differential equations. M2AN Math. Model. Numer. Anal. 41(3), 575–605 (2007)
Grepl, M.A., Patera, A.T.: A posteriori error bounds for reduced-basis approximations of parametrized parabolic partial differential equations. M2AN Math. Model. Numer. Anal. 39(1), 157–181 (2005)
He, J.-W., Glowinski, R., Metcalfe, R., Nordlander, A., Periaux, J.: Active control and drag optimization for flow past a circular cylinder. I. oscillatory cylinder rotation. Journal of Computational Physics 163, 83–117 (2000)
Hinze, M., Kunkel, M.: Discrete empirical interpolation in pod model order reduction of drift-diffusion equations in electrical networks. In: Michielsen, B., Poirier, J.-R. (eds.) Scientific Computing in Electrical Engineering SCEE 2010, Mathematics in Industry, pp. 423–431. Springer-Verlag, Berlin Heidelberg (2012)
Hinze, M., Pinnau, R., Ulbrich, M., Ulbrich, S.: Optimization with Partial Differential Equations. of Mathematical Modelling, Theory and Applications, vol. 23. Springer-Verlag, Berlin Heidelberg New York (2009)
Hinze, M., Volkwein, S.: Proper orthogonal decomposition surrogate models for nonlinear dynamical systems: Error estimates and suboptimal control. In: Benner, P., Mehrmann, V., Sorensen, D. C. (eds.) Dimension Reduction of Large-Scale Systems, Lecture Notes in Computational Science and Engineering, vol. 45, pp. 261–306. Springer-Verlag, Berlin Heidelberg (2005)
John, V.: Reference values for drag and lift of a two-dimensional time-dependent flow around a cylinder. International Journal for Numerical Methods in Fluids 44(7), 777–788 (2004)
Lall, S., Marsden, J.E., Glavaški, S.: A subspace approach to balanced truncation for model reduction of nonlinear control systems. Internat. J. Robust Nonlinear Control 12(6), 519–535 (2002)
Lass, O., Volkwein, S.: POD Galerkin schemes for nonlinear elliptic-parabolic systems. Konstanzer Schriften in Mathematik No. 301, FB Mathematik & Statistik, Universität Konstanz, D-78457 Konstanz, Germany, 2012. To appear in SIAM J. Scientific Computing
Lions, P.-L.: On the existence of positive solutions of semilinear elliptic equations. SIAM Rev. 24(4), 441–467 (1982)
Patera, A.T., Rozza, G.: Reduced Basis Approximation and A Posteriori Error Estimation for Parametrized Partial Differential Equations. MIT Pappalardo Graduate Monographs in Mechanical Engineering. Cambridge, MA (2007). Available from http://augustine.mit.edu/methodology/methodology_book.htm
Quarteroni, A., Valli, A.: Numerical Approximation of Partial Differential Equations. Springer-Verlag, Berlin Heidelberg New York (1994)
Roos, H.G., Stynes, M., Tobiska, L.: Robust Numerical Methods for Singularly Perturbed Differential Equations. Computational Mathematics, Vol. 24, 2nd ed. Springer-Verlag, Berlin Heidelberg (2008)
Roubíček, T.: Nonlinear partial differential equations with applications, volume 153 of International Series of Numerical Mathematics. Birkhäuser, Basel (2005)
Rowley, C.W.: Model reduction for fluids, using balanced proper orthogonal decomposition. Int. J. on Bifurcation and Chaos 15(3), 997–1013 (2005)
Rozza, G., Huynh, D.B.P., Patera, A.T.: Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations: application to transport and continuum mechanics. Arch. Comput. Methods Eng. 15(3), 229–275 (2008)
Rozza, G., Veroy, K.: On the stability of the reduced basis method for Stokes equations in parametrized domains. Comput. Methods Appl. Mech. Engrg. 196(7), 1244–1260 (2007)
Rump, S.M.: INTLAB — INTerval LABoratory. In: Csendes, T. (ed.) Developments in Reliable Computing, pp. 77–104. Kluwer Academic Publishers, Dordrecht (1999). http://www.ti3.tu-harburg.de/rump/
Stynes, M.: Steady-state convection-diffusion problems. In: Iserles, A. (ed.) Acta Numerica 2005, pp. 445–508. Cambridge University Press, Cambridge, London, New York (2005)
Tiso, P., Dedden, R.J., Rixen, D.J.: DEIM for nonlinear structural dynamics model order reduction, 2012. Talk presented at the 10th World Congress on Computational Mechanics, Sao Paulo, Brazil (8–13 July 2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Antil, H., Heinkenschloss, M., Sorensen, D.C. (2014). Application of the Discrete Empirical Interpolation Method to Reduced Order Modeling of Nonlinear and Parametric Systems. In: Quarteroni, A., Rozza, G. (eds) Reduced Order Methods for Modeling and Computational Reduction. MS&A - Modeling, Simulation and Applications, vol 9. Springer, Cham. https://doi.org/10.1007/978-3-319-02090-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-02090-7_4
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02089-1
Online ISBN: 978-3-319-02090-7
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)