Finite-difference ghost-point multigrid methods on Cartesian grids for elliptic problems in arbitrary domains

Abstract

In this paper we present a numerical method for solving elliptic equations in an arbitrary domain (described by a level-set function) with general boundary conditions (Dirichlet, Neumann, Robin, etc.) on Cartesian grids, using finite difference discretization and non-eliminated ghost values. A system of $N_i+N_g$ equations in $N_i+N_g$ unknowns is obtained by finite difference discretization on the $N_i$ internal grid points, and second order interpolation to define the conditions for the $N_g$ ghost values. The resulting large sparse linear system is then solved by a multigrid technique. The novelty of the papers can be summarized as follows: general strategy to discretize the boundary condition to second order both in the solution and its gradient; a relaxation of inner equations and boundary conditions by a fictitious time method, inspired by the stability conditions related to the associated time dependent problem (with a convergence proof for the first order scheme); an effective geometric multigrid, which maintains the structure of the discrete system at all grid levels. It is shown that by increasing the relaxation step of the equations associated to the boundary conditions, a convergence factor close to the optimal one is obtained. Several numerical tests, including variable coefficients, anisotropic elliptic equations, and domains with kinks, show the robustness, efficiency and accuracy of the approach.

Introduction

Elliptic equation in arbitrary domain (possibly with moving boundary) is central to many applications, such as diffusion phenomena, fluid dynamics, charge transport in semiconductors, crystal growth, electromagnetism and many others. The wide range of applications may require different kinds of boundary conditions. Let us look for instance at the temperature distribution in a medium of arbitrary shape satisfying stationary heat equation: we may have Dirichlet (the temperature is fixed at the boundary), Neumann (heat flux is prescribed), or mixed boundary conditions (namely different boundary conditions on different parts of the boundary). More general Robin boundary conditions may also be prescribed, as in Stefan-type problem, in which a combination of temperature and heat flux is prescribed at the boundary (e.g. see [27], [9]). An application we have in mind is to fluid dynamics: the aim is to model the motion of an incompressible fluid contained in a tank of arbitrary shape. The problem is modeled by incompressible Euler equations, which are solved by projection method of Chorin [15], [16]. This leads to an elliptic equation for the pressure, obtained enforcing the incompressibility condition. This pressure equation requires Dirichlet condition on the free surface of the fluid (because we prescribe the atmospheric pressure for instance) and Neumann condition on the rigid walls. The pressure equation is the bottleneck of the whole method and therefore requires an efficient solver. Since the correction step is made by the gradient of the pressure, the method must be accurate also in the gradient.

Several techniques have been developed to solve elliptic equation on an arbitrary domain. Finite Element Methods use a mesh triangulation to capture the boundary [50], [51], [45], [57]. However, in presence of moving boundary, a grid re-meshing is needed at each time step, which makes the method expensive. Furthermore, for a complex geometry, generation of a good mesh is a non trivial task that may require a considerable amount of work [38]. For this reason a Cartesian grid method is preferred together with a level-set approach to keep track of the boundary at each time step. Level-set methods have been introduced to implicitly define a domain and its boundary, in order to handle complex topological changes due to the motion of the boundary such as merging and breaking up. Several papers and books exist in the literature about level-set methods: [61], [47], [55], [23], [58] are just some examples.

Since the boundary may be not aligned with the grid, a special treatment is needed. The simplest method makes use of the Shortley–Weller discretization [60], that discretizes the Laplacian operator with usual central difference away from the boundary and makes use of a non-symmetric stencil in the interior points of the domain close to the boundary. While this discretization provides a simple second order method for Dirichlet conditions, it cannot be immediately applied in presence of Neumann conditions. In fact, Shortley–Weller discretization [60] for Neumann conditions requires that the value of the numerical solution is suitably reconstructed at the intersection between the grid and the boundary by applying the boundary conditions. This approach is adopted, for example, by Hackbusch in [31] to first order accuracy, and by other authors (see [7] and the references therein) to second order accuracy. However, the method proposed by Bramble in [7] for second order accuracy is quite involved and not recommendable for practical purposes.

Another method which achieves second order accuracy by modifying standard difference formulas was proposed by Mayo in [40] for solving Poisson or biharmonic equation on irregular domains. Such method embeds the irregular domain in a regular region with a Cartesian grid and discretizes the equation on the whole region, by suitable extension of the solution outside.

One of the most challenging problems in numerical methods for elliptic equations is the case of discontinuous coefficient. The pioneer work of Peskin [49] introduced the Immersed Boundary Method, and was later developed by other authors [36], [65] (Immersed Interface Method). Several methods have been recently developed: for sharp-edge interface, such as the Matched Interface and Boundary (MIB) method [66]; the finite volume method [46]; the non-symmetric positive definite finite element method [32], where the more general case of variable matrix coefficient is treated; the virtual node method [4]. In [17], the authors add additional unknowns on the interface, allowing to express straightforwardly the interface transmission conditions. The case of discontinuous coefficients is currently under investigation by the authors and some preliminary results in one dimension can be found in [18].

Several methods have been also proposed to model the interaction between multiphase flows and solid obstacles, such as Arbitrary Lagrangian Eulerian (ALE) [25], [22], Distribute Lagrangian Multiplier (DLM) [28], penalization methods [56], [1]. In [13] a combination of penalization and level-set methods is presented to solve inverse or shape optimization problems on uniform Cartesian meshes.

In this paper we propose a simple discretization technique for the solution of elliptic problems in arbitrary domains embedded in a regular square grid, solved by a multigrid approach. The discretization is based on a finite-difference ghost-cell technique, that adds extra grid points (ghost points) outside the domain. In ghost points the boundary conditions are enforced in order to close the linear system.

The ghost-cell method was first developed by Fedkiw in [24], where a two-phase contact discontinuity was discretized (Ghost Fluid Method). A second-order accurate method for Dirichlet conditions on regular Cartesian grid is proposed by Gibou et al. in [26]. The value at the ghost nodes is assigned by linear extrapolation, and the whole discretization leads to a symmetric linear system, solved by a preconditioned conjugate gradient method. A fourth order accurate method is also proposed in [27]. Other methods use a non-regular Cartesian grid, such as in [14], where Gibou et al. present finite difference schemes for solving the variable coefficient Poisson equation and heat equation on irregular domains with Dirichlet boundary conditions, using adaptive Cartesian grids. One efficient discretization based on cut-cell method to solve more general Robin conditions is proposed by Gibou et al. in [48], which provides second order accuracy for the Poisson and heat equation and first order accuracy for Stefan-type problems, and in [44] where suitable Neumann boundary conditions are discretized in a fluid–solid coupling method based on Hodge projection step.

Most of the techniques listed above cannot be straightforwardly applied in the special case of mixed boundary conditions. Simple efficient methods based on symmetric image of ghost points to solve mixed boundary condition problems provided with a multigrid algorithm have been recently developed in [11] and by Ma et al. [39], while a geometric multigrid method for embedded boundaries, applicable for mixed boundary conditions, and based on a cut-cell (finite volume) approach has been recently presented in [19].

Our method consists in the discretization of the elliptic operator using central difference, namely using a symmetric five-point stencil in two space dimension, centered in each of the $N_i$ internal grid points. The symmetry of the five-point stencil near the boundary suggests the introduction of $N_g$ ghost points, i.e. grid points outside the domain and belonging to a five-point stencil centered at an interior point. In order to close the linear discrete system, we write an equation for each ghost point, enforcing the boundary condition in the closest point of the boundary, by suitable interpolation. The choice of defining a single value of the unknown at ghost points has the advantage that it provides a natural extension of the solution out of the domain, in a neighborhood of the boundary. Other approaches, such as the one adopted by Gibou and Fedkiw in [26], defines more values at the same ghost point, and is restricted to Dirichlet conditions, but achieves better accuracy, as shown in the comparison in Section (5.5). A procedure based on biquadratic interpolation of the solution on the point of the boundary closest to the ghost point is adopted, providing second order accuracy in the solution and its gradient, as is confirmed by several numerical tests. Although the approach could be used to construct higher order schemes (using high order polynomials), we restrict ourselves to second order accuracy. The full set of equations (for the interior and for the ghost points) is solved by a suitable multigrid strategy.

Multigrid technique is one of the most efficient strategy to solve a class of partial differential equations, using a hierarchy of discretizations. An introduction to multigrid can be found, for example, in [8], while more advanced textbook on the subject are, for example, [62], [30]. Related literature for elliptic equations for arbitrary domain can be found in the detailed survey [12] and in the reference therein. Other recent developments are [63], [64], [34].

In all these papers, the multigrid is identified by the smoother and the transfer operators. Classical smoothers are usually variants of Jacobi or Gauss–Seidel iterations. Since each condition on a ghost point may involve other ghost points, then the additional conditions are coupled, and it is not trivial to eliminate the ghost points. Furthermore, even if we eliminated the ghost points by solving for them in terms of the inner points, then we would obtain a non convergent Jacobi or Gauss–Seidel scheme. For this reason the whole $(N_i+N_g)\times (N_i+N_g)$ system with non-eliminated boundary conditions is considered. While it is clear how to iterate on the equations relative to inner points, it is not obvious how to treat boundary conditions.

In this paper we present an original procedure for relaxing the equations on the ghost points. The procedure is based on re-writing both the PDE and the boundary conditions as an evolutionary problem using a fictitious time, which in practice has the meaning of a relaxation step: the original problem is defined as the stationary condition for the time dependent counterpart. The choice of the appropriate fictitious time step is dictated by stability conditions (more precisely by positivity conditions) of the forward Euler scheme applied to the corresponding evolutionary equation. This approach, which may be viewed as an automatic way to construct a good preconditioning for the original algebraic system, leads to a convergent Jacobi iteration for the full problem, at least in the case of the first order accurate scheme, as is shown in Section (3).

A similar approach, in a different context, has been introduced in 1987 by Merkle and Athavale [42] and by Rau [53], and subsequently adopted in conjunction with multigrid by Jameson [33]. In the latter paper, Jameson used the approach to solve unsteady compressible flows. The method consists in solving the whole problem implicitly in the physical time, and then adding a fictitious time at each time step in order to find the steady-state solution of the intermediate problem. The multigrid strategy was adopted to accelerate the steady-state convergence of the fictitious-time problem. The multigrid applied to dual time stepping has been later improved in [54] and coupled with a time-derivative preconditioning in [20], [37], [3], [59].

In our approach, the restriction operator is suitably modified for grid points close to the boundary, so that it weights only grid points from the same side of the boundary, because we want to transfer separately the defect of the inner equations from the defect of the boundary conditions (since they refer to different operators which scale with different powers of the spatial step). We experienced that this special treatment is not necessary for the interpolation operator, since it acts on the error, which is supposed to be sufficiently smooth across the boundary. The motivation for this conjecture is that the error refers to the solution, which is smoothly extended on ghost points from the internal points, using the boundary conditions. Such smoothness property is not true for the residue.

The plan of the paper is the following: the next section presents the discretization of the problem and the extension to some particular cases: Robin boundary conditions, variable coefficients, anisotropic case and sharp-edge domain. In Section 3 we describe the relaxation scheme (for which we provide also a convergence proof for the first order accurate method), using the fictitious time technique. Section 4 is devoted to the description of the multigrid approach, with a particular attention to the transfer operators. The last section presents several numerical tests, showing the second order accuracy in the solution and its gradient, and the optimal convergence factor for the multigrid.