Sixth Mississippi State Conference on Differential Equations and Computational Simulations, Electronic Journal of Differential Equations, Conference 15 (2007), pp. 193–210. ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu ftp ejde.math.txstate.edu (login: ftp)

AN AUGMENTED IIM-LEVEL SET METHOD FOR STOKES EQUATIONS WITH DISCONTINUOUS VISCOSITY

ZHILIN LI, SHARON R. LUBKIN, XIAOHAI WAN

Abstract. A finite difference method is proposed for incompressible Stokes equations with discontinuous viscosity. The method combines the augmented immersed interface method with a level set representation of the interface on a uniform Cartesian grid. In the proposed method, augmented interface variables are introduced along the interface and be solved by the GMRES iterative method. The augmented approach allows fast Poisson solvers to be used and therefore is very efficient. Numerical examples including two moving interface problems are presented.

1. Introduction

In this paper, we present a numerical method for solving the stationary incompressible Stokes equations for two-phase Newtonian flows with an arbitrary interface. The governing equations have the following form

∇p = ∇ · μ (∇u + (∇u)^{T} ) + F(x) + g(x),  (1.1)

with the incompressibility condition

∇ · u = 0,  (1.2)

where u = (u, v)^{T} is the fluid velocity, p is the fluid pressure, μ is the fluid viscosity, x = (x, y) is the Cartesian coordinate variable, g = (g_{1}, g_{2})^{T} is a body force such as gravity, and F is a source which can have a Dirac delta function singularity,

F(x) = ∫_{Γ} f(s)δ(x − X(s))ds  (1.3)

where Γ is a smooth interface in the solution domain with the arc-length parameter s, f = (f_{1}, f_{2})^{T} is the source density, and δ(·) is the Dirac delta function defined in the distribution sense. The body force term g may also have a finite jump across the interface Γ as well.

The interface Γ divides the solution domain Ω into two parts Ω^{+} and Ω^{−} with Ω = Ω^{+} ∪ Ω^{−}. If the interface is closed, we use Ω^{+} to express the exterior domain of the interface.

2000 Mathematics Subject Classification. 65M06, 65M12, 76T05.

Key words and phrases. Incompressible Stokes equations; discontinuous viscosity;

interface problem; immersed interface method; level set method; fast Poisson solver, GMRES.

\begin{matrix}c \\ ◯ \end{matrix}2007 Texas State University - San Marcos.

Published February 28, 2007.

We assume that the viscosity coefficient μ is piecewise constant across the interface:

μ(x) = \begin{cases}μ^{+} & if x ∈ Ω^{+}, \\ μ^{−} & if x ∈ Ω^{−}, \end{cases}  (1.4)

where μ^{+} and μ^{−} are two positive constants.

In this paper, we propose a finite difference method coupled with a level set function representation of the interface on a uniform Cartesian grid to solve the problem. Finite element and boundary integral methods for this problem can be found in the literature. These methods may be more efficient if only the solution on the interface is solved. In our method, we solve for the velocity in the entire domain.

There are at least two difficulties in solving (1.1)-(1.4) numerically using finite difference methods. The first one is to deal with the singular force term. A simple way is to use Peskin’s discrete delta function approach [24] to distribute the singular force to nearby grid points. Such a discretization is typically first order accurate and will smooth out the solution. The second difficulty is how to deal with the discontinuous viscosity. A simple smoothing method may introduce large errors; see [12] for a one-dimensional example.

In the case of a continuous viscosity with a Dirac delta function source distribution along an interface, various methods have been developed. We refer the readers to [2, 5, 10, 19, 32] for various methods and the references therein. The difficulty with a discontinuous viscosity is that the jump conditions for the pressure and velocity are coupled together (section 3), which makes it difficult to discretize the system accurately. Approximations of the jump conditions have been used to decouple the system [16] and have been productively used to simulate problems in biological fluid dynamics [18].

The augmented immersed interface method for incompressible 2D Stokes flows with discontinuous viscosity has been developed [15] with the interface represented by a cubic spline interpolation, a variation of the particle approach. It is easy with splines to obtain the surface derivatives of jumps of the material variables (pressure and velocity) since they can be expressed as the functions of the arclength. However, the spline approach is difficult to use for multi-connected domains, moving interface problems with topological changes such as merging and splitting, and for three dimensional (3D) problems. In addition, the level set method usually has better stability. For a spline approach, re-parameterization, filtering, and regriding may be needed at every or every other time steps. All these reasons favor a level set approach over a spline approach. Nevertheless, it is not trivial to compute surface derivatives of an interface quantity from the level set method since the interface is explicitly defined only at grid points.

2. The Stokes solver: Three Poisson equations approach

Instead of writing the singular force as a source term for the Stokes equations (1.1), we can solve the Stokes equations in the form

∇p = ∇ · μ^{+} (∇u + (∇u)^{T} ) + g(x), x ∈ Ω^{+}  (2.1)

and

∇p = ∇ · μ^{−} (∇u + (∇u)^{T} ) + g(x), x ∈ Ω^{−}.  (2.2)

We define viscosity ratio λ = μ^{−}/μ^{+}. If Γ is closed and λ > 1, then the fluid phase inside the interface is more viscous and is called a drop; if Γ is closed and λ < 1, then the fluid phase inside the interface is less viscous than the ambient fluid and is called a bubble (see for example [26]); if λ = 1 the fluids inside and outside have equal viscosity.

The solutions to (2.1)-(2.2) are coupled by the jump conditions which will be stated in Section 3. If we apply the divergence operator to both sides of the momentum equation (2.1, 2.2) and make use of the incompressibility condition(1.2) in each fluid, we get

Δp = ∇ · g,  (2.3)

where Δ is the Laplacian. This is a Poisson equation for the pressure p. Once p is solved from the equation above, we can rewrite the Stokes equation (2.1)-(2.2) in the form [1]

Δũ = \frac{∂p}{∂x} − g_{1},  (2.4)
Δṽ = \frac{∂p}{∂y} − g_{2},  (2.5)

where

ũ(x) = \begin{cases}μ^{+}u(x) x ∈ Ω^{+} \\ μ^{−}u(x) x ∈ Ω^{−}, \end{cases}  ṽ(x) = \begin{cases}μ^{+}v(x) x ∈ Ω^{+} \\ μ^{−}v(x) x ∈ Ω^{−}. \end{cases}  (2.6)

We obtain u = (u, v) by solving ũ = (ũ, ṽ) from the Poisson equations above. The three decoupled Poisson equations (2.3)-(2.5) each can be solved efficiently using a fast Poisson solver if the solutions are smooth across the interface.

3. Jump conditions

It is well known that if there are singular interface forces, then the pressure p is discontinuous, and the velocity u is non-smooth across the interface. If the viscosity is discontinuous, that is λ ≠ 1, then ũ is also discontinuous. Due to these discontinuities, the direct application of three Poisson solvers without modifications will not give the correct solution. It is critical to incorporate the jump conditions in the finite difference schemes so that the solutions in different phases can be coupled together correctly across the interface. The jump condition on the pressure p at point x^{∗} on the interface Γ is defined as

[p](x^{∗}) = ( lim_{x→(x^{∗})^{+}} p(x)) − ( lim_{x→(x^{∗})^{−}} p(x)).  (3.1)

Other jump conditions are defined similarly. Jump conditions on each variable can be derived either from the physics of the problem itself or from the partial differential equations. The derivations of the jump conditions for the Stokes equation are described elsewhere [15]. Here we just list the results. Define

q = (q_{1}, q_{2})^{T} = (\left[{ \atop ũ}\right] , \left[{ \atop ṽ}\right])^{T} .  (3.2)

Then the solutions of the Stokes flow are the following three Poisson equations:

\{ \begin{matrix}Δp = ∇ · g, \\ [p] = f̂_{1} − 2\frac{∂}{∂τ} (q · τ (x^{∗})) , \\ [\frac{∂p}{∂n}] = \frac{∂f̂_{2}}{∂τ} + 2\frac{∂^{2}}{∂τ^{2}} (q · n (x^{∗})) − 4κ\frac{∂}{∂τ} (q · τ (x^{∗})) + [g · n], \end{matrix}  (3.3)

\{ \begin{matrix}Δũ = p_{x} − g_{1}, \\ [ũ] = q_{1}, \\ [\frac{∂ũ}{∂n}] = (f̂_{2} + \frac{∂}{∂τ} (q · n (x^{∗})) ) sin θ − (\frac{∂}{∂τ} (q · τ (x^{∗})) ) cos θ, \end{matrix}  (3.4)

\{ \begin{matrix}Δṽ = p_{y} − g_{2}, \\ [ṽ] = q_{2}, \\ [\frac{∂ṽ}{∂n}] = −(f̂_{2} + \frac{∂}{∂τ} (q · n (x^{∗})) ) cos θ − (\frac{∂}{∂τ} (q · τ (x^{∗})) ) sin θ, \end{matrix}  (3.5)

[\frac{ũ}{μ}] = 0, [\frac{ṽ}{μ}] = 0.  (3.6)

In the jump conditions above, n = (cos θ, sin θ)^{T} and τ = (− sin θ, cos θ)^{T} are unit outward normal and tangential directions respectively, θ is the angle between the x-axis and the normal directions, f̂_{1} = f ·n and f̂_{2} = f ·τ are the force components in the normal and tangential directions. κ is interface curvature. Unit circle is defined to have constant curvature −1. The vector q is called the augmented variable which is unknown unless we know the solution (u, v)^{T}. However, if we know q, then the jump conditions for the pressure and the velocity are decoupled in terms of q and its surface derivatives. In this paper, we assume that we have a periodic boundary for all the variables.

The main idea of the augmented approach is to solve q such that (ũ, ṽ)^{T} and p satisfy the Stokes equations, the jump conditions above, and the kinematic condition

[u] = [v] = 0.  (3.7)

Then (u, v)^{T} and p must be the solution to the original problem.

The jump conditions above enable us to use the immersed interface method (IIM) to solve the three Poisson equations (2.3)-(2.5) if a guess q is given. The generalized minimum residual (GMRES) method [28] is used to solve for q so that the kinematic condition can be satisfied.

4. The numerical algorithm

4.1. Level set representation of interfaces and related quantities. We use the zero level set of a two dimensional function φ(x, y) to represent the interface. That is, φ(x, y) is such a function that

Γ = {(x, y) : φ(x, y) = 0} .  (4.1)

Generally φ(x, y) is chosen as the signed distance function from the interface. We denote Ω^{+} = {(x, y), | φ(x, y) ≥ 0} and Ω^{−} = {(x, y), | φ(x, y) < 0}. For simplicity, we assume that the domain Ω is a rectangle [a, b] × [c, d]. The solution domain is discretized using a uniform Cartesian grid

\begin{matrix}x_{i} = a + ih_{x}, i = 0, 1, …, m, h_{x} = \frac{b − a}{m}; \\ y_{j} = c + jh_{y}, j = 0, 1, …, n, h_{y} = \frac{d − c}{n}. \end{matrix}  (4.2)

In the rest of the paper, we take h_{x} = h_{y} = h to simplify the notation. The level set function φ_{i,j} = φ(x_{i}, y_{j}) is defined at grid points. A grid point (x_{i}, y_{j}) is an irregular inner grid point if

φ_{i,j} < 0  (4.3)

and any of the following four inequalities is true:

\begin{matrix}φ_{i,j} · φ_{i−1,j} ≤ 0, φ_{i,j} · φ_{i+1,j} ≤ 0, \\ φ_{i,j} · φ_{i,j−1} ≤ 0, φ_{i,j} · φ_{i,j+1} ≤ 0. \end{matrix}  (4.4)

Similarly, a grid point (x_{i}, y_{j}) is an irregular outer grid point if

φ_{i,j} ≥ 0  (4.5)

and any of the following four inequalities is true:

\begin{matrix}φ_{i,j} · φ_{i−1,j} < 0, φ_{i,j} · φ_{i+1,j} < 0, \\ φ_{i,j} · φ_{i,j−1} < 0, φ_{i,j} · φ_{i,j+1} < 0. \end{matrix}  (4.6)

For a given irregular grid point x = (x_{i}, y_{j}) near a sufficiently flat section of interface, there is a corresponding orthogonal projection point x^{∗} = (x^{∗}, y^{∗}) on the interface satisfying

x^{∗} = x + an(x)  (4.7)

where a is a real unknown variable and n = ∇φ/|∇φ| is the unit outward normal direction at x. See Fig. 1 for an illustration.

Since φ(x^{∗}) = 0, we have

0 = φ(x + an) ≈ φ(x) + |∇φ|a + \frac{1}{2}(n^{T}H(φ)n)a^{2}  (4.8)

where the Hessian matrix H is defined as

H(φ) = (\begin{matrix}\frac{∂^{2}φ}{∂x^{2}} & \frac{∂^{2}φ}{∂x∂y} \\ \frac{∂^{2}φ}{∂y∂x} & \frac{∂^{2}φ}{∂y^{2}} \end{matrix} ) .  (4.9)

The derivatives are approximated using the central finite difference schemes:

\frac{∂φ}{∂x} ≈ \frac{φ_{i+1,j} − φ_{i−1,j}}{2h} ,  (4.10)
\frac{∂φ}{∂y} ≈ \frac{φ_{i,j+1} − φ_{i,j−1}}{2h} ,  (4.11)
\frac{∂^{2}φ}{∂x^{2}} ≈ \frac{φ_{i+1,j} − 2φ_{i,j} + φ_{i−1,j}}{h^{2}} ,  (4.12)
\frac{∂^{2}φ}{∂y^{2}} ≈ \frac{φ_{i,j+1} − 2φ_{i,j} + φ_{i,j−1}}{h^{2}} ,  (4.13)
\frac{∂^{2}φ}{∂x∂y} = \frac{∂^{2}φ}{∂y∂x} ≈ \frac{φ_{i+1,j+1} + φ_{i−1,j−1} − φ_{i+1,j−1} − φ_{i−1,j+1}}{4h^{2}} .  (4.14)

Figure 1. An irregular grid point x = (x_{i}, y_{j}) and its normal projection point x^{∗} = (x^{∗}, y^{∗}) on the interface Γ. (ξ, η) is the local coordinate system at x^{∗}.

At each orthogonal projection x^{∗}, the geometrical information needed includes the curvature κ and the angle θ between the normal direction and the x-axis at x^{∗}. The curvature is defined as usual

κ = − \frac{\frac{∂^{2}φ}{∂x^{2}}(\frac{∂φ}{∂y})^{2} − 2\frac{∂^{2}φ}{∂x∂y} \frac{∂φ}{∂x} \frac{∂φ}{∂y} + \frac{∂^{2}φ}{∂y^{2}}(\frac{∂φ}{∂x})^{2}}{((\frac{∂φ}{∂x})^{2} + (\frac{∂φ}{∂y})^{2})^{\frac{3}{2}}} .  (4.15)

The unit normal direction is determined by

cos θ = \frac{\frac{∂φ}{∂x}}{\sqrt{(\frac{∂φ}{∂x})^{2} + (\frac{∂φ}{∂y})^{2}}} , sin θ = \frac{\frac{∂φ}{∂y}}{\sqrt{(\frac{∂φ}{∂x})^{2} + (\frac{∂φ}{∂y})^{2}}} .  (4.16)

The derivatives at x^{∗} can be approximated using the bilinear interpolation formula from the derivatives already calculated at grid points using (4.10)-(4.14) as following. Given an interface point x^{∗} and a grid function f(·), we label the four grid points surrounding x^{∗} as

(x_{i}, y_{j}), (x_{i+1}, y_{j}), (x_{i}, y_{j+1}), (x_{i+1}, y_{j+1}).  (4.17)

See Fig. 1 for an example. If we define

a = \frac{2(x^{∗} − x_{i})}{h} − 1, b = \frac{2(y^{∗} − y_{j})}{h} − 1,  (4.18)

then we can use the bilinear interpolation scheme

\begin{matrix}\{(1 − a)(1 − b)f_{i,j} + (1 + a)(1 − b)f_{i+1,j} \\ + (1 − a)(1 + b)f_{i,j+1} + (1 + a)(1 + b)f_{i+1,j+1}\}/4 \end{matrix}  (4.19)

to approximate f(x^{∗}). We can calculate κ, cos θ and sin θ at the orthogonal projection point x^{∗} if we set f = κ(x), f = cos θ, and f = sin θ respectively using the interpolated formula above. Note that these quantities are poorly conditioned if |∇φ| ∼ 0. However our choice of φ as the signed distance function avoids this difficulty.

4.2. The immersed interface method for elliptic interface problems. Given an intermediate approximation of q, the solution to the Stokes equations can be obtained by solving the three Poisson equations (2.3)-(2.5) with known jump conditions in the solution and the flux:

\begin{matrix}(Ψ_{x})_{x} + (Ψ_{y})_{y} = R(x, y) \\ [Ψ] = w_{1}, [Ψ_{n}] = w_{2}. \end{matrix}  (4.20)

using the immersed interface method [9, 13, 14]. The finite difference scheme using the immersed interface method can be simply written as

\frac{Ψ_{i−1,j} + Ψ_{i+1,j} + Ψ_{i,j−1} + Ψ_{i,j+1} − 4Ψ_{ij}}{h^{2}} = R_{ij} + C_{ij}  (4.21)

where C_{ij} = 0 at regular grid points. At an irregular grid point, C_{ij} depends on the interface curvature, first and second order surface derivatives of w_{1} and w_{2} (see [11] for its formulation and derivation). The immersed interface method not only gives a second order accurate solution, but also enables us to use widely available fast Poisson solvers to solve the discrete systems of equations. The fast Poisson solver, for example the one from Fishpack [23], only requires O(N log(N)) operations, where N is the total number of grid points. Therefore the Stokes equations with given q can be solved in O(3N log(N)) operations, which corresponds to the cost of one GMRES iteration.

4.3. Computing an interface quantity and its tangential derivatives using the least squares interpolation scheme. To determine the correction term C_{ij} we need to know the jumps [Ψ] = w_{1}(s), [\frac{∂Ψ}{∂n}] = w_{2}(s) and the tangential derivatives w′_{1}, w′′_{1} and w′_{2}, where s is the arc-length parameterization of the interface [11]. The problem may be formulated thus: given the values of an interface function ϕ(s) at a set of interface points s = s_{1}, …, s = s_{n}, find the values of ϕ(s^{∗}), ϕ′(s^{∗}) and ϕ′′(s^{∗}). It is critical to choose an interpolation scheme for the immersed interface-level set method to work well.

We assume that the values of the interface function ϕ(s) are known at all the projection points from the inner irregular grid points and we want to interpolate ϕ(s) at the projection points from the outer irregular grid points, and ϕ′(s) and ϕ′′(s) at the projection points from both inner and outer irregular grid points. See Fig. 2 for an illustration.

The least squares interpolation scheme for approximating ϕ(s^{∗}) (or ϕ′(s^{∗}) and ϕ′′(s^{∗})) can be written as

∑_{i} γ_{i}ϕ(s_{i}),  (4.22)

where γ_{i}’s are the coefficients that need to be determined from the Taylor expansion at the interpolation point s^{∗}

ϕ(s_{i}) = ϕ(s^{∗}) + ϕ′(s^{∗})(s_{i} − s^{∗}) + \frac{1}{2}ϕ′′(s^{∗})(s_{i} − s^{∗})^{2} + ….  (4.23)

Figure 2. On the interface Γ, the values of the interface function ϕ(s) at the projection points from the inner irregular grid points (dark circles) can be used to interpolate both the values of ϕ(s) at the projection points from the outer irregular grid points (white circles) and the values of ϕ′(s) and ϕ′′(s) at all the projection points.

We define

a_{1} = ∑_{i} γ_{i}, a_{2} = ∑_{i}(s_{i} − s^{∗})γ_{i} a_{3} = ∑_{i} \frac{1}{2}(s_{i} − s^{∗})^{2}γ_{i},  (4.24)

where (s_{i} − s^{∗}) is the signed arc length from the interface point at s = s_{i} to the point at s = s^{∗}(see [17] for its formula using the Hermite cubic spline approximation method). Substituting (4.23) into (4.22), we obtain the coefficients γ_{i} from setting

a_{1} = 1, a_{2} = 0, a_{3} = 0.  (4.25)

If we choose more than three interface points for the interpolation, then the linear system of equations (4.25) is under-determined, that is, there are an infinite number of solutions. We use the singular value decomposition (SVD) method to solve the system of equations (4.25) to get the unique solution that has the least 2-norm among all feasible solutions.

For a given s = s^{∗}, the interpolation points are chosen as a few orthogonal projections of inner grid points (φ_{i,j} < 0) that are the first few closest to the point (X(s^{∗}), Y (s^{∗})). The criterion is the arc length distance such that |s − s^{∗}| ≤ α, where α is a parameter. We choose α = 6.5h.

4.4. Augmented immersed interface method for the Stokes equations. The augmented unknown q needs to be solved only at orthogonal projection points from the inner irregular grid points because we can use interface interpolation to get the values at outer projection points.

Given a discrete approximation of (q_{1}, q_{2}) at {X_{k}}, we can solve the first three equations (3.3)-(3.5) to get an approximate solution: the pressure P(Q), the scaled velocity Ũ(Q) and Ṽ(Q). Generally the computed velocity (Ũ(Q), Ṽ(Q)) does not satisfy the two augmented equations in (3.6), that is, (U, V) = (Ũ/μ, Ṽ/μ) may not be continuous across the interface.

Let us concatenate the discrete solutions {P_{ij}}, {U_{ij}}, and {V_{ij}} as a vector Ũ whose dimension is O(3MN), where M and N are the number of grid lines in the x and y direction respectively. We denote also the vector of the discrete values of (q_{1}, q_{2}) at the control points {X_{k}} (consisted of projection points only from the inner irregular grid points) by Q whose dimension is O(2N_{b}). Then the discrete solution of (3.3)-(3.5) given Q can be written as

A Ũ + BQ = F_{1}  (4.26)

for some vector F_{1} and sparse matrices A and B. It requires solving three Poisson equations with different source terms and jump conditions to get Ũ.

Once we know the solution Ũ given Q, we can use (Ũ, Ṽ) and the jump conditions [Ũ_{n}] and [Ṽ_{n}] which also depend on Q, to get [U(Q)] = [Ũ(Q)/μ] and [V(Q)] = [Ṽ(Q)/μ] at those control points {X_{k}}, 1 ≤ k ≤ N_{b}. If both ∥ [U(Q)] ∥ and ∥ [V(Q)] ∥ are smaller than a given tolerance, then the method has already converged and the set of Q, Ũ/μ, Ṽ/μ is an approximate solution. The interpolation scheme to get [Ũ(Q)/μ] and [Ṽ(Q)/μ], which will be explained in the next sub-section, depends on Ũ, Q linearly. Therefore we can write

([Ũ/μ], [Ṽ/μ])^{T} = S Ũ + EQ − F_{2},  (4.27)

where S and E are two sparse matrices, and F_{2} is a vector. The matrices depend on the interpolation scheme but do not need to be actually constructed in the algorithm. We need to choose such a vector Q that the continuity condition for the velocity is satisfied along the interface Γ. If we put the two matrix-vector equations (4.26) and (4.27) together we get

[\begin{matrix}A & B \\ S & E \end{matrix}] [Ũ ; Q] = [\begin{matrix}F_{1} \\ F_{2} \end{matrix}] .  (4.28)

Note that Q is defined only on a set of points {X_{k}} on the interface while Ũ is defined at all grid points. The Schur complement for Q is

(E − SA^{−1}B)Q = F_{2} − SA^{−1}F_{1} = F̄.  (4.29)

If we can solve the system above to get Q, then we can get Ũ easily. Because the dimension of Q is much smaller than that of Ũ, we expect to get a reasonably fast algorithm for the two-phase Stokes equations if we can solve (4.29) efficiently.

In implementation, the GMRES iterative method [28] is used to solve (4.29). The GMRES method only requires matrix-vector multiplication. We explain below how to evaluate the right hand side F̄ of the Schur complement, and how to evaluate the matrix-vector multiplication needed by the GMRES iteration. We can see why we do not need to form the coefficient matrix E − SA^{−1}B explicitly.

4.4.1. Evaluation of the right hand side of the Schur complement. First we set Q = 0 and solve the de-coupled system (3.3)-(3.5), or (4.26) in the discrete form, to get Ũ(0) which is A^{−1}F_{1} from (4.26). From the interpolation (4.27), we also have

([U(0)], [V(0)])^{T} = S Ũ(0) + E 0 − F_{2} = S Ũ(0) − F_{2}.

Note that the residual of the Schur complement for Q = 0 is

\begin{aligned}R(0) & = (E − SA^{−1}B) 0 − F̄ = −F̄ \\ & = − (F_{2} − SA^{−1}F_{1}) = −F_{2} + S Ũ(0) \\ & = ([U(0)] , [V(0)])^{T} , \end{aligned}  (4.30)

which gives the right hand side of the Schur complement system with an opposite sign.

4.4.2. Evaluation of the matrix-vector multiplication. The matrix-vector multiplication of the Schur complement system given Q is obtained from the following two steps:

Step 1: Solve the coupled system (3.3)-(3.5), or (4.26) in the discrete form,

to get Ũ(Q). Step 2: Interpolate Ũ(Q) using (4.27) to get ([U(0)] , [V(0)])^{T}. Then the

matrix vector multiplication is

(E − SA^{−1}B) Q = ([U(Q)] , [V(Q)])^{T} − ([U(0)] , [V(0)])^{T} .  (4.31)

This is because

(E − SA^{−1}B) Q = EQ − SA^{−1}BQ
= EQ − S (A^{−1}F_{1} − Ũ(Q)) (from (4.26)) ,
= EQ + S Ũ(Q) − F_{2} + F_{2} − SA^{−1}F_{1}
= ([U(Q)], [V(Q)])^{T} + F̄ (from (4.27)),

= ([U(Q)], [V(Q)])^{T} − ([U(0)], [V(0)])^{T} , (from (4.30)).

Now we can see that a matrix-vector multiplication is equivalent to solving the coupled system (3.3)-(3.5), or (4.26) in the discrete form, to get Ũ, and using an interpolation scheme (4.27) to get ([U], [V])^{T} at the control points.

Since we know the right hand side of the linear system of equations and the matrix-vector multiplication of the coefficient matrix, it is straightforward to use GMRES or other iterative methods.

In summary, the system of equations for Q can be written as

GQ = b,  (4.32)

where b = − (\begin{matrix}[U(0)] \\ [V(0)] \end{matrix}). The coefficient matrix G does not need to be formed

explicitly. Given a guess of Q^{k}, the matrix vector multiplication that is needed for the GMRES iterative method is simply

GQ^{k} = (\begin{matrix}[U(Q^{k})] \\ [V(Q^{k})] \end{matrix}) − (\begin{matrix}[U(0)] \\ [V(0)] \end{matrix}) .  (4.33)

4.5. Computing the residual vector using the least squares interpolation. The matrix-vector multiplication (4.33) only involves the velocity jumps at the inner projection points. However, the velocity solved from the Poisson equations (2.3, 2.4, 2.5) is defined only at grid points. We use a least squares interpolation scheme again to get the velocity at the interface points. The interpolation scheme is critical for the accuracy and convergence speed of the GMRES method and thus is very important for the new method.

For an inner projection point x^{∗} = (x^{∗}, y^{∗}) and its neighboring grid points {x = (x_{m}, y_{n})|m, n ∈ ℕ}, we can find

(ũ(x^{∗}))^{+} = lim_{x→(x^{∗})^{+}} ũ(x)  (4.34)

using the following interpolation

∑_{m,n} β_{m,n}ũ(x_{m}, y_{n}) + C  (4.35)

where the coefficients β_{m,n} and the correction term C are to be determined. It is more convenient to use the local coordinate system in the tangential and normal directions (Fig. 1) defined as

ξ_{m} = (x_{m} − x^{∗}) cos θ + (y_{n} − y^{∗}) sin θ,

η_{n} = −(x_{m} − x^{∗}) sin θ + (y_{n} − y^{∗}) cos θ. (4.36)

The Taylor expansion of ũ(x_{m}, y_{n}) at (ξ, η) = (0, 0) is

\begin{matrix}ũ(ξ_{m}, η_{n}) \\ = ũ^{±} + \frac{∂ũ^{±}}{∂ξ} ξ_{m} + \frac{∂ũ^{±}}{∂η} η_{n} + \frac{1}{2} \frac{∂^{2}ũ^{±}}{∂ξ^{2}} ξ_{m}^{2} + \frac{1}{2} \frac{∂^{2}ũ^{±}}{∂η^{2}} η_{n}^{2} + \frac{∂^{2}ũ^{±}}{∂ξ∂η} ξ_{m}η_{n} + …. \end{matrix}

(4.37)

The ± sign is determined according to whether x ∈ Ω^{±}. Let us define

a_{1}^{+} = ∑_{(x_{m},y_{n})∈Ω^{+}} β_{m,n}, a_{1}^{−} = ∑_{(x_{m},y_{n})∈Ω^{−}} β_{m,n},

a_{2}^{+} = ∑_{(x_{m},y_{n})∈Ω^{+}} β_{m,n}ξ_{m}, a_{2}^{−} = ∑_{(x_{m},y_{n})∈Ω^{−}} β_{m,n}ξ_{m},

a_{3}^{+} = ∑_{(x_{m},y_{n})∈Ω^{+}} β_{m,n}η_{n}, a_{3}^{−} = ∑_{(x_{m},y_{n})∈Ω^{−}} β_{m,n}η_{n},

a_{4}^{+} = ∑_{(x_{m},y_{n})∈Ω^{+}} β_{m,n} \frac{1}{2}ξ_{m}^{2}, a_{4}^{−} = ∑_{(x_{m},y_{n})∈Ω^{−}} β_{m,n} \frac{1}{2}ξ_{m}^{2},

a_{5}^{+} = ∑_{(x_{m},y_{n})∈Ω^{+}} β_{m,n} \frac{1}{2}η_{n}^{2}, a_{5}^{−} = ∑_{(x_{m},y_{n})∈Ω^{−}} β_{m,n} \frac{1}{2}η_{n}^{2},

a_{6}^{+} = ∑_{(x_{m},y_{n})∈Ω^{+}} β_{m,n}ξ_{m}η_{n}, a_{6}^{−} = ∑_{(x_{m},y_{n})∈Ω^{−}} β_{m,n}ξ_{m}η_{n}.

(4.38)

Substituting (4.37) into (4.35), the coefficients β_{m,n} of the interpolation scheme for ũ^{+} are seen to be the solution of the following linear system of equations

\begin{matrix}a_{1}^{+} + a_{1}^{−} = 1, a_{2}^{+} + a_{2}^{−} = 0, a_{3}^{+} + a_{3}^{−} = 0, \\ a_{4}^{+} + a_{4}^{−} = 0, a_{5}^{+} + a_{5}^{−} = 0, a_{6}^{+} + a_{6}^{−} = 0. \end{matrix}  (4.39)

The correction term is

C = a_{1}^{−}[ũ] + a_{2}^{−}[\frac{∂ũ}{∂ξ}] + a_{3}^{−}[\frac{∂ũ}{∂η}] + a_{4}^{−}[\frac{∂^{2}ũ}{∂ξ^{2}}] + a_{5}^{−}[\frac{∂^{2}ũ}{∂η^{2}}] + a_{6}^{−}[\frac{∂^{2}ũ}{∂ξ∂η} ]. (4.40)

Again, we choose more than six grid points for the interpolation to get an underdetermined system of equations. The linear system of equations is solved by the SVD method. The jump conditions in the correction term can be represented by the jump in the solution and the flux (see [15]).

Similarly, we can get an interpolation scheme for ũ^{−}. Once we have ũ^{±} at all orthogonal projections of inner irregular grid points, it is also straightforward to

get (\begin{matrix}[U] \\ [V] \end{matrix}) which is needed in the matrix-vector multiplication.

To get the interpolation grid points for a given inner projection point x^{∗} = (x^{∗}, y^{∗}), we choose at least 6 closest grid points to (x^{∗}, y^{∗}) as the interpolation stencil so that we can have a third order accurate interpolation scheme. To avoid excess points we use | (ξ_{m}, η_{n}) | ≤ 2.5h.

4.6. The level set method for moving interfaces. We use the level set method first introduced by Osher & Sethian [22] to solve the moving interface problems modeled by the incompressible Stokes equations. The level set function is evolved according to the level set function (a Hamilton-Jacobi equation)

\frac{∂φ}{∂t} + V_{n}|∇φ| = 0  (4.41)

where V_{n} = u · n is the component of the velocity in the level sets normal direction and φ = φ(x, t). The level set function φ is often chosen as the signed distance function which satisfies the Eikonal equation

|∇φ| = 1  (4.42)

at least in a neighborhood of the interface. To ensure that the level set function φ remains the signed distance function, we solve the following re-initialization equation at each time step after interface advection until |∇φ| = 1 + O(h^{2}):

\begin{matrix}φ(x, t = 0) = φ_{0}, \\ \frac{∂φ}{∂t} = sign(φ_{0})(1 − |∇φ|). \end{matrix}  (4.43)

Numerical methods [21, 30] for Hamilton-Jacobi (HJ) equations can be used to solve the level set equations (4.41)-(4.43). In our implementation, we use the explicit forward Euler scheme for the time derivative and the third order WENO (Weighted Essentially Non-Oscillatory) scheme for the spatial derivatives.

The standard level set methods do not preserve volume well. Sussman et. al. [31] incorporated the volume conservation condition into the re-initialization equation (4.43) and a hybrid particle level set approach has also been proposed [3]. We use a simple approach described in [7] to preserve the area.

5. Numerical examples

In this section we present one example with fixed interface, one with a moving interface and one with four moving interfaces. All the computations are done on a P4 2.80GHz DELL desktop PC with 512MB memory. The computational domain is Ω = [−2, 2] × [−2, 2]. We choose to fix μ^{+} = 1.0, so λ = \frac{μ^{−}}{μ^{+}} = μ^{−}.

5.1. A general fixed interface test problem. We first present some results to a general fixed interface test problem. The interface is chosen to be a unit circle

φ(x, y) = \sqrt{x^{2} + y^{2}} − 1.0.  (5.1)

The initial guess of GMRES for the augmented variable Q takes zero values. The non-physical exact test solutions of (u, p) are constructed as [15]

u = \begin{cases}\frac{y}{4} & if x^{2} + y^{2} < 1, \\ \frac{y}{4} (x^{2} + y^{2}) & if x^{2} + y^{2} ≥ 1; \end{cases}

v = \begin{cases}−\frac{x}{4}(1 − x^{2}) & if x^{2} + y^{2} < 1, \\ −\frac{xy^{2}}{4} & if x^{2} + y^{2} ≥ 1; \end{cases}

p = \begin{cases}(−\frac{3}{4}x^{3} + \frac{3}{8}x)y & if x^{2} + y^{2} < 1, \\ 0 & if x^{2} + y^{2} ≥ 1. \end{cases}

(5.2)

The body force term g = (g_{1}, g_{2})^{T} is chosen to be

g_{1} = \begin{cases}(−\frac{9}{4}x^{2} + \frac{3}{8}) y & if x^{2} + y^{2} < 1, \\ −2μ^{+}y & if x^{2} + y^{2} ≥ 1; \end{cases}

g_{2} = \begin{cases}−\frac{3}{4}x^{3} + \frac{3}{8}x − \frac{3μ^{−}}{2} x & if x^{2} + y^{2} < 1, \\ \frac{μ^{+}}{2} x & if x^{2} + y^{2} ≥ 1. \end{cases}

(5.3)

And the singular interface force terms are

f̂_{1} = (\frac{3}{4} cos^{3} θ − \frac{3}{8} cos θ) sin θ − \frac{3}{2} cos^{3} θ sin θ[μ],

f̂_{2} = \frac{1}{2}μ^{+} + \frac{3}{4}[μ] cos^{2} θ(1 − 2 cos^{2} θ).

(5.4)

To accommodate the exact solutions, the jump condition for \frac{∂p}{∂n} is modified by adding a correction term, which does not change the difficulty of the problem. Note that this is a very general fixed interface problem with non-homogeneous jumps and tangential derivatives in all quantities.

We use linear regression analysis to find the convergence order of all quantities. For this purpose, we choose m = n = 32 + 16k(k = 0, …, 54) and run the convergence analysis for λ = 0.001, 0.1, 10 and 1000. Fig. 3 is the grid refinement analysis of the test problem. The error is the L^{∞} error at all grid points. The slope of the linear regression line is the order of the convergence. It is clear from these results that the algorithm is second order accurate in velocity u = (u, v)^{T}, as expected, and almost second order accurate in pressure p. For this problem, it also seems that with larger λ, the numerical solution for u (or v) tends to be more accurate than the solution for p.

Fig. 4 shows the algorithm efficiency analysis. The number of GMRES iterations seems to be independent of grid size for fixed λ, and increases slowly as λ increases. Most simulations finish within two minutes.

5.2. A moving interface test problem. We present a moving interface test problem where the surface tension is the only interface force, i.e. the normal force f̂_{1} = ακ where α > 0 and κ is the curvature as defined before; we set the tangential force f̂_{2} = 0.0. We choose α = 1.0 and m = n = 64 in our simulations. It is known that starting from an arbitrary interface shape without any body forces, i.e. g = 0, the interface will evolve to the equilibrium circle shape [10]. The initial interface is

(a)  (b) (c)  (d)

Figure 3. Convergence analysis in the L^{∞} norm for four cases in log-log scale. The slope of the linear regression line is the convergence rate which is close to number 2.0 for all cases. (a) μ^{−} = 0.001 and μ^{+} = 1.0. (b) μ^{−} = 0.1 and μ^{+} = 1.0. (c) μ^{−} = 10 and μ^{+} = 1.0. (d) μ^{−} = 1000 and μ^{+} = 1.0. Linear regressions R^{2} > 0.98 for all cases.

chosen to be an ellipse

φ(x, y) = \sqrt{\frac{(x + y)^{2}}{2a^{2}} + \frac{(−x + y)^{2}}{2b^{2}}} − 1.0  (5.5)

where a = 2.0 and b = 0.5. We use periodic boundary conditions for both u and p. See Fig. 5 for an example of the interface evolution. Also see Fig. 6 for a comparison of the evolving interfaces with different λ’s at a fixed time. It is clear from Fig. 6 that the more viscous fluid moves slower. For all the moving interface simulations, the area conservation algorithm [7] preserves the initial area at each time step exactly.

5.3. A moving multiple-interface problem. We present another moving interface test problem with a multiply-connected interface consisting initially of four ellipses. As in the other test problems, we use periodic boundary conditions on the edges of the simulation rectangle. The two fluids have equal viscosity, the surface tension is given as f̂_{1} = ακ where α = 0.1, and we set f̂_{2} = 0. The initial interfaces are easily constructed using the union of individual level set functions [21, 30]. As the four symmetrically placed ellipses relax to circles, we observe preservation of the symmetries in the flow. Equilibrium is reached when the pressure is uniformly distributed.

Figure 4. Algorithm efficiency analysis for 32 by 32 through 896 by 896 grids. Left axis represents number of GMRES iterations and right axis represents computational CPU cost with unit second using log scale. GMRES iterations (thick curves) remain relatively constant with grid size, and CPU time (thin curves) ∼ grid number^{2}.

Figure 5. A moving interface simulation with λ = 0.5, at time t = 0, 0.86, 1.90 and 6.75. Starting from the ellipse, the interface evolves to a circle. The inner reference circle (dash curve) helps to show the symmetry of the equilibrium interface. The final area inside the interface is 3.14 ≈ π so our algorithm preserves area well.

Figure 6. Comparison of viscosity effects on interface motion. Three curves (thin curves) at time t = 1.5, for λ = 0.5, 1.0, 2.0. λ = 0.5 approaches equilibrium (thick curve) fastest.

(a)  (b)

Figure 7. A moving interface simulation starting with four elliptic interfaces (white boundary). Streamlines are drawn and symmetry of streamlines are observed as expected. We choose λ = 1 here. (a) t = 5. (b) t = 50.

Discussion

In this paper we proposed a new numerical method for Stokes equations with interfaces, by combining the augmented interface method with the level set method. Our method handles moving interfaces and multiply connected interfaces more easily than a spline approach, and could more easily be extended to 3D. Our algorithm is shown to be 2nd order accurate in both velocity and pressure, and conserves volume well. Our method should prove useful for interface problems in fluid flow and biological models.

One of the remaining open questions is how to use a preconditioning technique for the Schur complement system since the coefficient matrix for the Schur complement system is not explicitly formed. Even the simplest diagonal preconditioning technique needs to use the fast Stokes solver N_{b} times which would cost more than that of the entire solution process for the testing examples in this paper. On the other hand, as discussed in [13], a good interpolation scheme for the residual that takes advantages of the interface/jump conditions can reduce the number of iteration significantly. Therefore, it is more practical to tune-in the interpolation scheme as a preconditioner than to use preconditioning techniques that require structures of the coefficient matrix. Fortunately, for all the test examples in this paper, the number of GMRES iterations is modest (fewer than 55).

Acknowledgments. This work was partially supported by grants: 0201094 from NSF/NIH, 43751-MA from ARO, and DMS-0412654 from NSF. The first author would like to thank Prof. John Bishir for helpful discussions and proofreading the paper.

References

[1] A. J. Chorin, Numerical solution of the Navier-Stokes equations, Math. Comput. 22:745-762, 1968.

[2] R. Cortez, The Method of Regularized Stokeslets, sisc, 23: 1204-1225, 2001.

[3] D. Enright, R. Fedkiw, J. Ferziger and I. Mitchell, A hybrid particle level set method for improved interface capturing, J. Comp. Phys., 183:83-116, 2002.

[4] L. J. Fauci and A. McDonald, Sperm motility in the presence of boundaries, B. Math. Biol., 57:679-699, 1994.

[5] A. L. Fogelson and C. S. Peskin; Numerical solution of the three dimensional Stokes equations in the presence of suspended particles, Proc. SIAM Conf. Multi-phase Flow, SIAM. June 1986.

[6] E. Givelberg and J. Bunn, A comprehensive three-dimensional model of the cochlea, J. Comput. Phys., 191:377-391, 2003.

[7] S. Groß, V. Reichelt and A. Reusken, A finite element based level set method for two-phase incompressible flows, IGPM-Report 243, RWTH Aachen, 2004.

[8] S. Jadhav, C. D. Eggleton and K. Konstantopoulos, A 3-D computational model predicts that cell deformation affects selectin-mediated leukocyte rolling, Biophys. J., 88:96-104, 2005.

[9] R. J. LeVeque and Z. Li, The immersed interface method for elliptic equations with discontinuous coefficients and singular sources, SIAM J. Numer. Anal., 31:1019, 1994.

[10] R. J. LeVeque and Z. Li, Immersed interface methods for Stokes flow with elastic boundaries or surface tension, SIAM J. Sci. Comput., 18:709-735, 1997.

[11] Z. Li, The immersed interface method - a numerical approach for partial differential equations with interfaces, PhD thesis, University of Washington, 1994.

[12] Z. Li, An overview of the immersed interface method and its applications, Taiwanese J. Mathematics, 7:1-49, 2003.

[13] Z. Li, A Fast Iterative Algorithm for Elliptic Interface Problems, SIAM J. Numer. Anal., 35:230-254, 1998.

[14] Z. Li and K. Ito, Maximum Principle Preserving Schemes for Interface Problems with Discontinuous Coefficients, SIAM J. Sci. Comput., 23:1225-1242, 2001.

[15] Z. Li and K. Ito and M-C. Lai; An augmented approach for Stokes equations with a discontinuous viscosity and singular forces, NCSU-CRSC Tech. Report: CRSC-TR04-23, North Carolina State University, 2004.

[16] Z. Li and S. R. Lubkin, Numerical Analysis of Interfacial 2D Stokes Flow with Discontinuous Viscosity and Variable Surface Tension, Numerical Methods in Fluids, 37:525-540, 2001.

[17] Z. Li, H. Zhao and H. Gao, A numerical study of electro-migration voiding by evolving level set functions on a fixed Cartesian grid, J. Comput. Phys., 152:281-304, 1999.

[18] S. R. Lubkin and Z. Li, Force and Deformation on Branching Rudiments: Cleaving Between Hypotheses, Biomechanics and Modeling in Mechanobiology, 1(1):5-16, 2002.

[19] A. Mayo and C. S. Peskin, An implicit numerical method for fluid dynamics problems with immersed elastic boundaries, Contemp. Math., 141:261-277. 1991.

[20] D. M. McQueen and C. S. Peskin, Heart simulation by an immersed boundary method with formal second-order accuracy and reduced numerical viscosity, In Mechanics for a New Millennium, Proceedings of the International Conference on Theoretical and Applied Mechanics (H. Aref and J. W. Phillips, eds.), Kluwer Academic Publishers, 2001.

[21] S. J. Osher and R. P. Fedkiw, Level set methods and dynamic implicit surfaces, Springer-Verlag, 2002.

[22] S. J. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys., 79:12-49, 1988.

[23] P. Swarztrauber and R. Sweet, Efficient FORTRAN subprograms for the solution of elliptic partial differential equations, NCAR Technical Note-TN/IA-109, 1975.

[24] C. S. Peskin, The immersed boundary method, Acta Numerica, 1-39, 2002.

[25] C. S. Peskin and D. M. McQueen, Fluid dynamics of the heart and its valves, In Case Studies in Methematical Modeling: Ecology, Physiology, and Cell Biology (H. G. Othmer, F. R. Adler, M. A. Lewis and J. C. Dallon, eds.), Prentice-Hall, Englewood Cliffs, NJ, 309-337, 1996.

[26] C. Pozrikidis eds., Modeling and simulation of capsules and biological cells, Chapman & Hall, London, 2003.

[27] Y. Saad and M. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7:856-869, 1986.

[28] Y. Saad, GMRES: A Generalized minimal residual algorithm for solving nonsymmetric linear systems, sissc, 7:856-869, 1986.

[29] J. A. Sethian and P. Smereka, Level set methods for fluid interfaces, Annu. Rev. Fluid Mech., 35:341-72, 2003.

[30] J. A. Sethian, Level Set Methods and Fast Marching methods, Cambridge University Press, nd edition, 1999.

[31] M. Sussman and E. Fatemi, An efficient, interface-preserving level set redistancing algorithm and its application to interfacial incompressible fluid flow, SIAM J. Sci. Comput., 20:1165-1191, 1999.

[32] C. Tu and C. S. Peskin, Stability and instability in the computation of flows with moving immersed boundaries: a comparison of three methods, sissc, 13:1361-1376, 1992.

[33] X. Wang and W. K. Liu, Extended immersed boundary method using FEM and RKPM, Comput. Methods Appl. Mech. Eng., 193:1305-1321, 2004.

[34] A. Wiegmann and K. P. Bube, The explicit-jump immersed interface method: finite difference methods for PDEs with piecewise smooth solutions, SIAM J. Numer. Anal., 37:827-862, 2000.

[35] L. Zhang, A. Gerstenberger, X. Wang and W. K. Liu, Immersed finite element method, Comput. Methods Appl. Mech. Engrg., 193:2051-2067, 2004.

Zhilin Li Center for Research in Scientific Computation & Department of Mathematics, North Carolina State University, Raleigh, NC 27695-8205, USA

   E-mail address: zhilin@math.ncsu.edu

Sharon R. Lubkin Center for Research in Scientific Computation & Department of Mathematics, North Carolina State University, Raleigh, NC 27695-8205, USA

   E-mail address: lubkin@math.ncsu.edu

Xiaohai Wan Biomathematics Graduate Program & Department of Mathematics, North Carolina State University, Raleigh, NC 27695-8203, USA

   E-mail address: xwan@unity.ncsu.edu