CutFEM: Discretizing geometry and partial differential equations

2.1 A Poisson model problem

Let Ω be a bounded domain in two or three space dimensions, with an interface Γ dividing Ω into two non-overlapping subdomains Ω₁ and Ω₂, so that Ω:=Ω₁∪Ω₂∪Γ, with the interface defined by . For simplicity, we assume that the subdomains are polyhedral (or polygonal in R²) and that Γ is polygonal (or a broken line).

For any sufficiently regular function u in Ω₁∪Ω₂, we define the jump of u on Γ by 〚u〛:=u₁|_Γ−u₂|_Γ, where is the restriction of u to Ω_i. Conversely, for u_i defined in Ω_i, we identify the pair (u₁,u₂) with the function u, which equals u_i on Ω_i. For definiteness, we define n as the outward pointing unit normal to Ω₁ on Γ. We shall consider a problem with piecewise constant data α so that , and a reaction coefficient that may be discontinuous across Γ. Our first model problem is the following variant of Poisson's equation:

(1)

where we used the flux vectors q_i:=−α_i∇u_i.

In a standard finite element method, the jump in the normal derivative resulting from the continuity of the flux q:=−α∇u, when α₁≠α₂, can be taken into account by letting Γ coincide with mesh lines. In 5, 7, another approach was taken in that 1 was solved approximately using piecewise polynomial finite elements on a family of conforming shape regular triangulations of Ω that were independent of the location of the interface Γ. The approximation was then allowed to be discontinuous inside elements, which intersected the interface.

To recall this method, we will use the following notation for mesh related quantities. For any element K, let K_i=K∩Ω_i denote the part of K in Ω_i. By , we here denote the set of elements that are intersected by the interface. For an element , let Γ_K:=Γ∩K be the part of Γ in K.

We shall seek a discrete solution U = (U₁,U₂) in the space , where

As Γ may intersect two edges of a triangle arbitrarily, the size of the parts K_i is not fully characterized by the meshsize parameters. Thus, to guarantee stability of this method using elements with internal discontinuities, further conditions on the combinations of numerical fluxes (co-normal derivatives) must be imposed by choosing appropriate mesh and geometry dependent weights κ. The approach suggested in 5, 7 was to choose the numerical fluxes by introducing weights

(2)

where meas(K) denotes the size (area or volume) of K, and to use a weighted mean

(3)

where ∂_n:=n·∇, as the flux on Γ (note that κ₁+κ₂=1). Thus, for an intersected element, a mean numerical flux that takes the different meshsizes into account was computed. However, for problems in which there is a very large difference between the parameters α_i, this approach is not robust. To improve robustness, the weighted average must also take into account the parameters: in 3, we must change the definitions of the κ_i to

(4)

cf. 21, 22.

The method is defined by the variational problem of finding U∈V^h such that

(5)

where

with and

For stability, one must take γ sufficiently large. Two choices of γ have been proposed in the literature for these weights. In 21, it was suggested to take

(6)

and in 22, the choice

(7)

was advocated. Above is a mesh and parameter independent constant and

With these definitions, the discrete problem 5 is consistent in the sense that, for u solving 1,

(8)

In Section 3, we will discuss the consequences of the different choices of the penalty parameter and an alternative route to robustness inspired by fictitious domain methods.

A FE basis for V^h is easily obtained from a standard FE basis on the mesh by the introduction of new basis functions for the elements that intersect Γ. Thus, we replace each standard basis function living on an element that intersects the interface by two new basis functions, namely its restrictions to Ω₁ and Ω₂, respectively. The collection of basis functions with support in Ω_i is then clearly a basis for , and hence, we obtain a basis for V^h by the identification . If the interface coincides exactly with an element edge, no new basis functions are introduced on these elements, but the approximating functions may still be discontinuous over such an edge. As a consequence, there are six non-zero basis functions on each element that properly intersects Γ. Perhaps this process is most easily seen as creating two new separate meshes with doubling of the elements crossed by the interface (Figure 1).

We now want to show that the approximation property of V^h is optimal in the following mesh dependent norm:

We thus wish to show that functions in V^h approximate functions to the order h in the norm . For this purpose, we construct an interpolant of v by nodal interpolants of H²-extensions of v₁ and v₂ as follows. Choose extension operators E_i:H²(Ω_i)→H²(Ω) such that and

(9)

Let I_h be the standard nodal interpolation operator and define

(10)

We then have the following result. Let be an interpolation operator defined as in 10. Then

(11)

In the proof of this result, we need to estimate the interpolation error at the interface. To that end, the following trace inequality is necessary: under reasonable mesh assumptions 5-7, there exists a constant C_T, depending on Γ but independent of the mesh, such that

(12)

The crucial fact is that the constant in this inequality is independent of the location of the interface relative to the mesh. Optimal interpolation estimates follow, as does optimal convergence of the method irrespective of the location of the interface relative to the mesh. The key elements of the analysis are the robust coercivity of a_h(·,·) with respect to the norm , the consistency property 8, and the approximability 11. For details, see 5.

2.2 The case of Dirichlet boundaries

We now consider the boundary value problem

(13)

where Γ=Γ_D∪Γ_N denotes the boundary of the domain Ω, discretized on a mesh that contains Ω but is not fitted to the domain boundary. Denoting the mesh domain , we consider the following finite element space:

By , we denote the set of elements that are intersected by the interface. For an element , let Γ_K:=Γ∩K be the part of Γ in K. We also introduce the set of element faces associated with , defined as follows: for each face , there exist two simplices K and K^′ such that F = K ∩ K^′ and at least one of the two is a member of . This means in particular that the boundary faces of the mesh are excluded from . On a face F such that F = K ∩ K^′, define the jump of the gradient of v∈W^h by , where n_F denotes the unit normal to F, the orientation is chosen arbitrarily. The problem that arises when applying Nitsche's method in this framework is that the inverse inequality corresponding to 12 cannot be robust when the right hand side must be controlled by norms over the physical domain alone, as the cut elements can be arbitrarily small. We thus need to further stabilize the problem. The finite element discretization takes the form: find U∈W^h, such that

(14)

where

and

with

(15)

and

(16)

Here, γ_D,γ_N, and γ₁ are positive penalty parameters; cf. 12. The rationale for the stabilization term 16 is that it extends the coercivity from the physical domain Ω to the mesh domain . Details are given in Section 3.

2.3 Other interface conditions of interest

3.1 Example: perfect conductor, the limit of infinite diffusion

As an example of how the improved robustness works, we will consider the problem 1, with Ω₂ completely enclosed by Ω₁ such that ∂Ω⊂∂Ω₁ and Γ:=∂Ω₂(Figure 2). It is well known that in the limit α₂→∞, the solution u₂ becomes constant in Ω₂ and can therefore be exactly represented by one degree of freedom. We will give two formulations of this problem, one similar to 5, and the other using the reduced model in a framework similar to the fictitious domain approach 14 using only one degree of freedom to represent u₂. In both formulations, we will use the ghost penalty method so that the weights may be depending only on the diffusivities. This allows us to show that the solution of the domain decomposition approach converges to that of the fictitious domain approach in the limit as α₂→∞. We will then compare this to what is obtained if the weights are chosen as in equation 4, with the penalty defined in equation 6 or 7.

First, consider the formulation 35, and U∈V^h such that

(28)

with a_h(U,v) and L(v) as defined in 5, but for simplicity with f₂≡0 and using the weights

(29)

and the penalty parameter

(30)

This choice of weights was first considered in the context of discontinuous Galerkin methods in 36 and then for Nitsche's method in 37. The ghost penalty terms are designed similarly to the formulation 14. However, here, j_i(U_i,v_i) is acting in the boundary zone of the mesh domain . It is straightforward to prove coercivity of this formulation using the arguments of the previous section, indeed,

(31)

Here, we used the inequality

and the stability 25 in both subdomains.

If we formally let α₂→∞ and replace U₂ and v₂ by constant functions, we find the following formulation: find such that for all , there holds

(32)

where . It follows by inspection that this formulation is equivalent to 14, with the only difference that in this case the Dirichlet value set on Γ is an unknown constant value. The coercivity and hence the discrete wellposedness can be shown here exactly using the arguments of 27 together with a triangle inequality and a trace inequality to get control of . First note that by a triangular inequality, a trace inequality on the whole domain Ω₁, and a Poincaré inequality, we have

Therefore, by the same arguments as above, there exists a constant c > 0 such that

(33)

Consequently, both 28 and 32 are coercive, and with some additional effort, one may prove that the approximations indeed have optimal convergence in the H¹ and L²-norm provided the exact solution is sufficiently smooth when restricted to each subdomain.

Here, we will instead consider the robustness of the formulation 28. A natural question to ask, as 32 was obtained by taking the formal limit α₂→∞ in 28, is if the solutions of the two formulations also coincide in the limit. We will show now that this is the case. Let U = (U₁,U₂) denote the solution of 28 and denote the solution of 32. If we set and note that , we may use the coercivity proven in 31:

Using the formulation 28 and once again that , we see that

Now, we apply the formulation 32 on the form to write

(34)

By applying Cauchy–Schwarz inequalities and trace inequalities and using the definition of γ in the right hand side, we may then obtain

Using 33 and cα₁≤γ≤Cα₁ when α₁≤α₂, it follows that

and we conclude that as α₂→∞ meaning that the asymptotic limit of the solution of 28 coincides with that of 32.

Another important observation is that for the discretization using ghost penalty and weights depending only on the diffusion, preconditioning the system matrix using diagonal scaling with α₁,α₂ leads to a system whose condition number is independent of both the mesh/boundary intersection and the contrast in the diffusion (for details, see 35).

Note that the use of the weights 4 and the penalty parameters 6 or 7 do not allow a similar robust limit formulation. This can be seen in the following way. Consider the penalty parameter γ for the choice 6 proposed in 21. Then the limit satisfies

which is robust in the diffusion parameter but degenerates into the choice of weights for the fictitious domain method that depends on the element cuts. Hence, for the weights 6, preconditioning using diagonal scaling will make the system robust for large contrast, but unfortunate cuts will still result in a poorly conditioned system matrix. This disadvantage motivated the introduction of the ghost penalty operator in the previous section.

The choice 7 on the other hand results in the limit behavior,

This implies that 〚U〛 = 0 across the boundary, which may not always be compatible with optimal accuracy. Observe also that the penalty parameter is present in the system matrices corresponding to the bulk discretization in both subdomains. As γ becomes big, with increasing α₂, it will destroy the conditioning of the matrix corresponding to subdomain Ω₁.

3.2 A numerical illustration

Robustness issues may also appear in the limit of vanishing diffusion in a subdomain. We consider a configuration similar to that of Figure 2, with the square domain Ω:=[−1,1]². Let Ω₂ be a disc with radius 0.75 centered in the origin and Ω₁:=Ω∖Ω₂. In this configuration, we solve 1, with u|_∂Ω=0, α₁=1, f = 1, , and with α₂∈{10⁻⁴,10⁻⁶,10⁻⁹}. First, we apply the formulation 5 with weights given by 3. The elevations of the solutions are presented in Figure 3. We then solve the same problem using the method 28 with 29–30 and give the corresponding elevations in Figure 4. Observe the relatively strong, but local, spurious overshoots that are present close to the layer in Figure 3. The combination of the ghost penalty and the parameters 29–30 eliminates the oscillations by relaxing the continuity constraint in the limit. Indeed, the sharp layer is represented as a discontinuity when it is under resolved.

Now, we consider the case where , α₂=1 and choose α₁=10²⁰, to illustrate the effect in the limit α₁→∞. This corresponds to a situation similar to that explored in Example 3.1, but with the diffusivity going to infinity in the outer domain. In Figure 5, we compare the results of the method 5 with the weights 3 and of 28 with 29–30. We see that for this large contrast, the method using the weights 3 exhibits some spurious oscillations close to the boundary, probably owing to an incompatibility between the constraint 〚U〛 = 0 and the weakly imposed condition on the gradient. In other words, the finite element space defined on the cut mesh does not allow for a H¹-conforming interpolant that also can represent the jump in the gradient. This effect is reminiscent of locking but only present in the vicinity of the interface. The method 28 on the other hand converges to the fictitious domain solution of 14 in the limit for which optimal error estimates exist.

3.3 Ghost penalty for surface partial differential equations

Let us consider the Laplace–Beltrami problem: find u_Γ:Γ→R such that

(35)

where Δ_Γ=∇_Γ·∇_Γ is the Laplace–Beltrami operator. The finite element method takes the form: find such that

(36)

and we recall that is the space of continuous piecewise linears on , the union of elements intersecting Γ.

In this case, the ghost penalty term provides additional stability to the discrete problem, which may be arbitrary ill conditioned. The proof of the optimal scaling estimate of the condition number, that is,

(37)

basically relies on the Poincaré estimate

(38)

and the inverse estimate

(39)

Note that, in these inequalities, the ghost penalty term plays a crucial role. Using the Poincaré and inverse estimate together with the coercivity of the bilinear form and the standard scaled equivalence,

(40)

between the Euclidian norm on the nodal values of v∈W_h and the L²-norm on , we may prove 37; see 38 for details.

Furthermore, we note that the ghost penalty term scales in the same way as the bilinear form (∇_Γv,∇_Γw)_Γ and that we have the interpolation error estimate

(41)

Using the Galerkin orthogonality, we obtain an optimal error estimate in the energy norm and by duality an L²-error estimate,

(42)

In order to deal with the effect of approximating the boundary Γ, a more elaborate analysis is needed, and we refer to 38 for further details. For a numerical example of the solution of the Laplace–Beltrami equation on a non-trivial surface, see Section 6.3.

5.1 Interface approximation and sub-triangulation of cut elements

In the first step of the subtesselation algorithm, the values of the level-set function in the element nodes are used to distinguish between elements that are fully contained in Ω₁ (φ < 0 for all nodes) or Ω₂ (φ > 0 for all nodes) and the elements that are intersected by the interface Γ (φ > 0 and φ < 0 in some nodes) (Figures 8 and 9).

For elements that are intersected by the interface, we perform a subtriangulation of the element allowing us to apply standard quadrature rules to the subtriangles for the integration over the parts K₁, K₂, and Γ_K. Here, we only consider linear intersections of the zero level-set with the elements that are represented by one straight line segment per element in 2d or one plane in 3d. In more detail, the subtriangulation algorithm consists of the following steps.

5.2 Integration over subtriangulation

For the evaluation of integrals over the subtriangulation, we require two mappings . Here, the linear affine mapping, χ_p, between the reference element and the cell part, transforms a quadrature rule defined on the reference element in terms of quadrature points ξ_i and weights w_i into a quadrature rule on the subtriangle cell part (Figure 14). The mapping χ_w between the reference element and the whole ‘parent’ cell is used to map the quadrature points defined on the physical subtriangle to their location in the reference element of the whole parent cell.

More precisely, the quadrature rule over the cell part is given in terms of quadrature points in physical space and quadrature weights . Here, J_p is the Jacobian of the mapping χ_p. These points and weights can then be used to perform the numerical quadrature over the given cell part, for example, for a mass matrix, by

(47)

Here, A_T[j][k] denotes the matrix entry for the cell integral over the degrees of freedom j and k. Note here that we have to evaluate basis functions and/or their derivatives at arbitrary points on the reference element that result from the backward transformation of the quadrature rule over the cell part onto the reference element of the whole ‘parent’ element.

5.3 Software for CutFEM-type method

The technology required for the automated assembly of general cut finite element based variational forms over fictitious domains and embedded surfaces has been implemented as part of the software library libCutFEM. libCutFEM is open source and freely available from http://www.cutfem.org. This software library builds on the finite element library DOLFIN, which is part of the FEniCS project 42 for automated scientific computing. The main feature of FEniCS is the automated treatment of finite element variational problems, based on automated generation of highly efficient C++ code from abstract high-level descriptions of finite element variational problems expressed in near-mathematical notation 43.

libCutFEM makes use of this automatization technology in the following way. We specify the variational problem in near-mathematical notation in the domain specific Uniform Form Language 43 (for an example, see Figure 17). Then the code generation components of FEniCS (UFL+FFC+UFC 42) generate code containing information about the cell integrals of the given forms and information about the elements such as the degrees of freedom maps. In particular, libCutFEM uses an extension developed in earlier works of the components FFC 44, 45 and UFC 46. In these works, FFC and UFC were extended 33, 47, 48 to provide generated code for the cell integration over cut cell parts (see right box in Figure 14). These extensions provide the fundamental infrastructure for the evaluation of cut finite element based variational forms defined on fictitious domains and embedded surfaces. Consequently, given a high-level description of the variational formulation, low-level C++ code can be automatically generated for the evaluation of the cut element and surface integrals, in addition to the evaluation of integrals over the standard (non-cut) mesh entities. The generated code takes as input appropriate quadrature points and weights for each cut entity, which are provided by the libCutFEM library. The resulting cell integral matrix contributions are then assembled to the global matrix by routines provided in libCutFEM.

In addition to these quadrature and assembly routines, libCutFEM provides functionality for computing topological and geometric descriptions of the embedded surface and cut elements. Currently, libCutFEM mainly supports the level set based cutting algorithm as described in detail in the previous section. However, alternative geometrical algorithms can be integrated easily thanks to the modular structure of the library and FEniCS, which decouples the variational formulation, the quadrature and assembly routines, and the geometrical and mesh description.

In summary, in libCutFEM, one may specify variational forms defined over finite element spaces on fictitious domains in high-level UFL notation 43, define the background mesh , and give a description of the surface Γ, and then invoke the functionality provided by the libCutFEM library to automatically assemble the corresponding stiffness matrix. In particular, the numerical experiments presented in Sections 6.1–6.3, corresponding to the variational formulation defined by 50, 58 and 60, have been carried out using this technology. We also present the UFL scripts that were used to obtain the numerical results illustrating the simplicity by which the end user can access the CutFEM paradigm (Figures 17, 18, and 21). Other software projects including CutFEM style technology include GetFem++ 49, LifeV 50, and DUNE-UDG 51.

6.1 Stabilized Nitsche fictitious domain method for the Poisson problem

Consider the following Poisson problem on the domain Ω:

(48)

where Γ denotes the boundary of the domain Ω. Following 12, we consider the finite element space:

(49)

and seek U∈W^h for the stabilized Nitsche finite element formulation

(50)

where

(51)

and

(52)

with

(53)

and

(54)

Here, the outward unit normal n_Γ is determined by the level set through the formula

(55)

where φ is the level set function. In particular, we seek such that

(56)

We consider the solution of Equation 50 in two complex domains: the popcorn 45 and the olympic rings, which are constructed by taking the minimum over five tori specified in Equation 44. We set f = 1, γ = 10.0, and γ₁=0.1.

The solution u in the popcorn geometry is depicted in Figure 15. Figure 15a shows the fictitious domain mesh of the popcorn geometry colored by the value of U. Figure 15b displays the subtesselation of the popcorn surface, and Figure 15c shows a contour plot of U in a slice through the middle of the popcorn.

Solving the Poisson Equation 50 in the olympic ring geometry gives the result depicted in Figure 16, where Figure 16a shows the surface subtesselation, and Figure 16b shows the solution U in a slice through the middle of the olympic rings. The UFL input files to specify Equations (50 and 56 in the libCutFEM/FEniCS framework are displayed in Figures 17 and 18, respectively.

6.2 Stabilized Nitsche fictitious domain method for the Stokes' problem

Following 29, 30, we now employ the ghost penalty technique to solve Stokes' problem

using a Nitsche fictitious domain method. We let the discrete velocity space V^h be the space of continuous, piecewise linear, -vector fields and let the discrete pressure space Q^h consist of either piecewise constant or continuous piecewise linear elements, denoted by and , respectively. To formulate our CutFEM method for the Stokes problem, we introduce the forms

As explained in Section 3, we extend the coercivity of the bilinear form a_h(·,·) from the physical to fictitious domain using the ghost penalty

As the mixed spaces and are known to violate the Babuška–Brezzi conditions, we stabilize our scheme by the following symmetric pressure penalties:

(57)

where denotes all the interior faces in the mesh domain . Note that the integral contributions in 57 are always evaluated on the entire face F, even for faces that are intersected by the boundary Γ. Again, such a ghost penalty ensures the robustness and optimal convergence properties of the stabilized scheme irrespective of the location of the boundary; see 29, 30 for detailed proofs.

Combining these forms, the stabilized Nitsche fictitious domain method for Stokes' problem reads: find (U,P)∈V^h×Q^h such that for all (v,q)∈V^h×Q^h

(58)

where

and

We present two numerical examples. First, we compute the Stokes flow in the Swiss cheese domain while the domain is rotating along the z-axis at constant angle velocity. As volume force, we take f = (0,0,−1). Figure 19 shows both the pressure approximation and the computed velocity. In the second example, we consider the flow through a blood vessel bifurcation with an aneurysm developed at the bifurcation; see Figure 20. Here, the vessel boundary is given as a surface mesh generated from biomedical image data, demonstrating the great potential of CutFEM technologies also to applications where only non-smooth boundary descriptions can be obtained.

6.3 Laplace–Beltrami problem on a surface using a bulk-mesh

We consider the Laplace–Beltrami problem for a surface Γ: find solving

(59)

where Γ denotes the popcorn surface described by the level-set function 45. Then, the cut finite element method for the Laplace–Beltrami problem is to seek such that

(60)

where the bilinear form A(·,·) is defined by

(61)

with

(62)

The right-hand side f is set to f(x,y,z) = x + y + z, satisfying the compatibility condition (f,1)_Γ=0. For the bulk mesh, the mesh size is approximately h≈0.04. Figure 22 depicts the solution U on the popcorn surface 45. Figure 21 shows the UFL input file used in libCutFEM to specify the Laplace–Beltrami problem.

6.4 Porous media flow in a domain with cracks

In this section, we give some preliminary numerical results obtained when solving 19 using the stabilized bilinear form

The stabilization term j_Γ(·,·) is necessary in the case when α_Γ/α becomes large, as we are then basically solving a perturbed Laplace–Beltrami problem.

We consider the following model problem in : a domain (0,1) × (0,1) with Dirichlet boundary conditions u = 1 at x = 0 and u = 0 at x = 1, zero Neumann conditions elsewhere. Choosing α = 1 in Ω and an elliptically shaped crack shown in Figure 23 and setting γ_Γ=10, we obtain the following results when setting α_Γ=0 on the lower arc of the crack and α_Γ∈{1,2,4} in the upper arc. A close-up of the computed velocities α∇U close to the crack, using the computational mesh of Figure 24, is shown in Figure 25, together with a corresponding zoom of the mesh in Figure 26, and isoline plots of the pressures U are given in Figure 27. We note that even a small increase in permeability increases the velocity quite noticeably in the crack. Further developments for system of cracks are under way.