• 검색 결과가 없습니다.

HanChen, ChohongMin, andFr´ed´ericGibou ASupra-ConvergentFiniteDifferenceSchemeforthePoissonandHeatEquationsonIrregularDomainsandNon-GradedAdaptiveCartesianGrids

N/A
N/A
Protected

Academic year: 2022

Share "HanChen, ChohongMin, andFr´ed´ericGibou ASupra-ConvergentFiniteDifferenceSchemeforthePoissonandHeatEquationsonIrregularDomainsandNon-GradedAdaptiveCartesianGrids"

Copied!
42
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

DOI: 10.1007/s10915-006-9122-8

A Supra-Convergent Finite Difference Scheme for the Poisson and Heat Equations on Irregular Domains and Non-Graded Adaptive Cartesian Grids

Han Chen,1 Chohong Min,2 and Fr´ed´eric Gibou3

Received March 30, 2006; accepted (in revised form) November 28, 2006; Published online March 31, 2007

We present finite difference schemes for solving the variable coefficient Poisson and heat equations on irregular domains with Dirichlet boundary conditions.

The computational domain is discretized with non-graded Cartesian grids, i.e., grids for which the difference in size between two adjacent cells is not con- strained. Refinement criteria is based on proximity to the irregular interface such that cells with the finest resolution is placed on the interface. We sample the solution at the cell vertices (nodes) and use quadtree (in 2D) or octree (in 3D) data structures as efficient means to represent the grids. The boundary of the irregular domain is represented by the zero level set of a signed distance function. For cells cut by the interface, the location of the intersection point is found by a quadratic fitting of the signed distance function, and the Dirichlet boundary value is obtained by quadratic interpolation. Instead of using ghost nodes outside the interface, we use directly this intersection point in the discret- ization of the variable coefficient Laplacian. These methods can be applied in a dimension-by-dimension fashion, producing schemes that are straightforward to implement. Our method combines the ability of adaptivity on quadtrees/octrees with a quadratic treatment of the Dirichlet boundary condition on the inter- face. Numerical results in two and three spatial dimensions demonstrate sec- ond-order accuracy for both the solution and its gradients in the L1 and L norms.

KEY WORDS: Poisson equation; heat equation; irregular domains; supra- convergence; non-graded adaptive Cartesian grids; quadtrees; octrees.

1Computer Science Department, University of California, Santa Barbara, CA 93106, USA.

2Department of Mathematics, KyungHee University, 130–701, Seoul, Korea.

3Mechanical Engineering Department and Computer Science Department, University of California, Santa Barbara, CA 93106, USA. E-mail: fgibou@engineering.ucsb.edu

19

0885-7474/07/0500-0019/0 © 2007 Springer Science+Business Media, LLC

(2)

1. INTRODUCTION

The Poisson and the heat equations are two of the fundamental equations used in the modeling of diffusion dominated phenomena, rang- ing from electromagnetism to semi-conductor growth to fluid mechanics. A wide variety of approaches exist for solving the Poisson equation on irreg- ular domains. In [26] Peskin introduced the immersed boundary method, which uses a δ-function that smears out the solution on a thin finite band around the interface. Leveque and Li introduced the immersed interface method [16], which is a second-order accurate numerical method designed to preserve the jump condition at the interface. In [22, 24], Mayo et al.

proposed a fast method using boundary integral techniques. Based on the Ghost Fluid Method of Fedkiw et al. [8], Liu et al. [18] developed a first- order accurate symmetric discretization of the variable coefficient Poisson equation in the presence of an irregular interface across which the variable coefficient, the solution and its derivative may have jumps. Gibou et al.

[11] introduced a second-order accurate symmetric discretization of the variable coefficient Poisson equation in the case where Dirichlet boundary conditions are imposed on the irregular domain. In this case, ghost values across the interface are defined by linear extrapolation allowing standard central differencing formulas to be used when discretizing the Laplacian near the interface. Third and fourth-order accurate schemes were later pro- posed in Gibou et al. [9] by defining ghost values with higher-order extrap- olations. In this case the corresponding linear system is non-symmetric but the method produces accurate results for very coarse grids, making the method extremely efficient. Jomaa and Macaskill [14] showed that in the case where ghost values are defined by linear extrapolations, the error near the boundary is in general large compared to the error found for regu- lar domains. Defining ghost values by a quadratic extrapolation makes the linear system non-symmetric, but leads to errors comparable with those obtained for a regular domain.

Many physical problems have different scales and more often than not, only small portions of the computational domain require finer res- olution. In this case, uniform grids become inefficient in terms of mem- ory storage and CPU usage, and adaptive mesh strategies are usually adopted. Adaptive mesh strategies for elliptic partial differential equations, such as the Poisson equations, are often associated with the finite element method (see, e.g., [7, 13]). Young et al. [35] introduced a finite element method employing adaptive mesh refinements for second-order variable coefficient elliptic equations using a cut-cell representation of irregular domains. However, adaptive mesh refinement strategies for the finite ele- ment method can be complex in the case of irregular domains due to the

(3)

organization of the resulting data structure. In addition, special care must be taken for moving boundary problems in order to guarantee good mesh quality (see, e.g., [31]).

Cartesian grids have the advantage of easier grid generation over unstructured grids, especially in three spatial dimensions. In [12], Johan- sen and Colella presented a cell-centered finite volume discretization to solve the variable coefficient Poisson equation on irregular domains with Dirichlet boundary conditions. They used a multigrid approach and a block-grid algorithm related to the adaptive mesh refinement scheme of Berger and Oliger [5]. McCorquodale et al. [23] presented a node-cen- tered finite difference approach to solving the variable coefficient Poisson equation with Dirichlet boundary conditions on irregular domains using the block-structured adaptive mesh refinement and the multigrid solver of Almgren et al. [2–4]. Numerical evidence in [23] showed that while both linear and quadratic interpolations produce second-order accurate solu- tions, only quadratic interpolations (Shortley–Weller approximation [32]) yield second-order accurate gradients in the L norm. These methods, however, do not consider non-graded adaptive grids in which the differ- ence in size between two adjacent cells is not constrained.

Aftomis et al. [1] pointed out that quadtree/octree data structures (see, e.g., [29, 30] for an introduction on quadtree/octree data structures) could be used as an efficient means to represent Cartesian grids. Popinet [27]

proposed a second-order non-symmetric numerical method to study the incompressible Navier–Stokes equations using an octree data structure to represent the spatial discretization. In this method, a Poisson equation for the pressure is solved to account for the incompressibility condition using a standard projection method. Only graded trees, i.e., trees for which the ratio between two adjacent cell sizes cannot exceed two, were considered in [27]. Non-graded grids generate less nodes leading to efficient methods and allow for more flexible grid generations since the size between adja- cent cells is not constrained. In [20], Losasso et al. proposed a first-order accurate symmetric discretization of the Poisson equation on non-graded octrees in the context of free surface flows. This work was then extended to second-order accuracy in [19] using the work of Lipnikov et al. [17]. A common criticism of quadtree/octree data structures is the time it takes to traverse the tree from the root to a leaf. This issue can be alleviated by using a uniform grid at the coarsest level and a quadtree/octree in every cell of this uniform grid as demonstrated in [19].

Recently, Min et al. [25] introduced a supra-convergent finite differ- ence scheme for solving the variable coefficient Poisson equation on reg- ular domains using non-graded grids represented by quadtrees/octrees.

A hallmark of this method is that it produces second-order accurate

(4)

solutions with second-order accurate gradients (supra-convergence). In this paper, we extend this method to solve the variable coefficient Poisson and the heat equations on irregular domains. We describe the interface by the set of points where a level set function is zero. We automatically construct non-graded Cartesian grids based on the proximity to the interface, i.e., we impose the finest resolution at the interface. Such grid generations yield straightforward approximations of both the Poisson and the heat equa- tions on non-graded Cartesian meshes. We note, however, that one can in addition refine the mesh in other regions if needed, as shown in Sec. 5.

For interior nodes, the variable coefficient Laplacian is discretized as in [25], where the spurious error induced by interpolation at ghost nodes at T-junctions is cancelled out by a weighted combination of the discretiza- tions in other Cartesian directions. For nodes adjacent to the interface, the location of the interface point is found by a quadratic fitting of the signed distance level set function, and the Dirichlet boundary value is obtained either explicitly (if an analytic formula is known) or calculated using a quadratic interpolation using neighboring nodal values in the case where the Dirichlet boundary values are defined at the nodes. The Shortley–

Weller approximation [32], based on quadratic extrapolation, is then used to discretize the Laplacian. The resulting non-symmetric linear system is solved using the stabilized bi-conjugate gradient (Bi-CGSTAB) method with the incomplete LU preconditioner [28]. In the case of the heat equa- tion, the Crank–Nicolson scheme is used with a time step of ∆t= c∆x, where 0 < c < 1 and ∆x is the size of the smallest cell. Numerical examples demonstrate that our method produces second-order accuracy for the solu- tion as well as its gradients in the L1 and L norms. We emphasize that second-order accuracy for the gradient is particularly important in Stefan- type problems since the overall accuracy of the method is determined by the accuracy of the gradients at the interface. We find that our method on adaptive grids favorably compares to the symmetric solver of Gibou et al.

[11] on uniform grids.

2. EQUATIONS 2.1. Poisson Equation

Consider a Cartesian computational domain, Ω, with exterior bound- ary, ∂Ω, and a lower-dimensional irregular interface, Γ , which divides the computational domain into disjoint pieces, the interior region Ω and the exterior region Ω+ (see Fig. 1). The regions are represented by a level set function φ, taken to be the signed distance function to the interface Γ . That is, Ω is represented by the set of points where φ < 0 and Ω+ is

(5)

Fig. 1. Schematic of two distinct regions Ωand Ω+, separated by an interface Γ .

represented by the set of points where φ > 0, whereas Γ is represented by the set of points where φ= 0 The variable coefficient Poisson equation is written as

∇ · (ρ(x)∇u(x)) = f (x), x ∈ Ω, (1) where ∇ =(∂x ,∂y ,∂z ) is the gradient operator and where ρ(x) is assumed to be continuous on each of the disjoint subdomains, Ω and Ω+, but may be discontinuous across the interface Γ . Furthermore, ρ(x) is assumed to be bounded from below by a positive constant. On ∂Ω, either Dirichlet or Neumann boundary conditions are specified. On the interface Γ , a Dirichlet boundary condition of uΓ= g(x) is specified. Thus, Eq. (1) decouples into two distinct equations, one on Ω and one on Ω+, and the solutions can be obtained independently.

2.2. Heat Equation

Ignoring the effects of convection, the standard heat equation reads

ρcvTt= ∇ · (k∇T ), (2)

where T is the temperature, ρ the density, cv the specific heat at constant volume, and k is the thermal conductivity. Assuming that ρ and cv are

(6)

constant allows Eq. (2) to be written as

Tt= ∇ · (ˆk∇T ), (3)

where ˆk=ρckv.

3. SPATIAL DISCRETIZATION ON QUADTREES/OCTREES

The computational domain Ω is discretized into squares (in 2D) or cubes (in 3D), and quadtree (in 2D) or octree (in 3D) data structures are used to represent this discretization. As depicted in Fig. 6 for a 2D domain, the entire domain is originally associated with the root of the tree, which has a level of zero by definition. Then this discretization pro- ceeds recursively, i.e., each cell can be in turn split into four children which have one more level than their parent cell. A cell with no children is called a leaf. Two cells are called neighbors if they share a common face or part of a face. The interested reader is referred to [29, 30] for more details on quadtree and octree data structures (Fig. 2).

By definition, a quadtree is graded if the difference between two adja- cent cell levels is at most one. In this paper, we sample the solution at the nodes (vertices of cells) and we consider non-graded Cartesian grids, i.e., grids for which the level difference between two adjacent cells is not constrained. In our non-graded Cartesian grids, a node is regular if it is linked to another node by a cell edge in each of the directions. In two

Fig. 2. Discretization of a 2D domain (left) and its quadtree representation (right). The entire domain corresponds to the root of the tree (level 0), and each cell is subdivided into four children, in the order of lower-left, upper-left, lower-right, upper-right. In this example, the tree is not graded since the difference of levels between neighboring cells exceeds one.

(7)

Fig. 3. A general configuration in 2D illustrating the nodes involved in the discretization at a T-junction node v0. The broken line between v0 and the ghost node v4is imaginary.

Fig. 4. A general configuration in 3D illustrating of the nodes involved in the discretization at v0. There is a 2D T-junction in the−x-direction, and a 3D T-junction in the −y-direction.

The broken lines are imaginary.

spatial dimensions, a node is called a T-junction node if it does not have a direct neighboring node in one, and only one, of the −x, x, −y, and y-directions, as illustrated in Fig. 3. In three spatial dimensions, at most one 3D T-junction and one 2D T-junction can occur at a node, as depicted in Fig. 4.

(8)

Adaptive grids are usually generated in such a way as to produce a uniform error throughout the entire domain, see, e.g., [34] for adaptive mesh generations based on a posteriori error estimate. For many problems, e.g., Stefan-type problems [6, 10], the solution’s gradient at the interface drives the interface motion and therefore the accuracy of the method. It is therefore desirable to discretize the computational domain in such a way that the cell size is proportional to the distance to the interface. In this work, we split a cell c if the following test is satisfied:

minv∈V|φ(v)| <lip× diag

2 , (4)

where v is a vertex of the current cell c, V the set of all vertices of c, lip the Lipschitz constant associated with φ, and diag is the diagonal length of the current cell. As pointed out by Strain in [33], this is a splitting algo- rithm that automatically generates non-graded Cartesian grids and guaran- tees the finest resolution on the interface. In addition, enforcing uniform cells with the smallest size on the interface prevents the occurrence of T-junctions. This greatly simplifies our finite difference discretization in Sec. 4.2 and allows a straightforward extension of the method of Min et al. [25].

4. FINITE DIFFERENCE SCHEMES

4.1. Variable Coefficient Poisson Equation on Regular Domains

We first recall the finite difference discretization from Min et al. [25]

for the variable coefficient Poisson Eq. (1) on regular domains.

4.1.1. One Spatial Dimension

In one spatial dimension, the finite difference discretization on a non- uniform grid at a grid node xi is

ui+1− ui

si+1 2

·ρi+1+ ρi

2 +ui−1− ui

si−1 2

·ρi−1+ ρi

2



· 2

si+1 2+ si−1

2

= fi+si+1 2 − si−1

2

3 · uxxx+ O(h2), (5)

where si−1

2=xi−xi−1and h=maxisi+1

2. Even though this scheme appears to be second-order accurate only in the case where the grid is uniform, it is in fact second-order accurate (see, e.g., [15, 21]).

(9)

4.1.2. Two Spatial Dimensions

In two spatial dimensions, a node is either a regular node or a T-junction node, i.e., a node with a missing direct neighboring node. We emphasize that the T-junction can only occur at one of the −x, +x, −y, and +y-directions. Let us consider the finite difference discretization for a T-junction node without a direct right neighboring node as depicted in Fig. 3 noting that the discretization when the T-junction is in the other directions can be derived in a similar manner: denote by ui the solution value at node vi. The ghost value u4 is calculated by linear interpolation using u5 and u6:

u4=s5u6+ s6u5 s5+ s6

. (6)

The forward difference for ρux at node v0 is also linearly interpolated as (ρux)+v

0=s5D6+ s6D5 s5+ s6

, (7)

where

D5=u5− u0

s4 ·ρ5+ ρ0

2 , (8)

D6=u6− u0

s4 ·ρ6+ ρ0

2 . (9)

The discretizations for (ρux)x and (ρuy)y at the node v0, along with their Taylor series expansions, are given by

u1− u0

s1 ·ρ1+ ρ0

2 +s6D5+ s5D6 s5+ s6



· 2 s1+ s4

= (ρux)x+ s5s6 (s1+ s4)s4

ρuy

y+ O(h) (10)

and

u2− u0

s2 ·ρ2+ ρ0

2 +u3− u0

s3 ·ρ3+ ρ0

2



· 2 s2+ s3=

ρuy

y+ O(h), (11) respectively, where D5 and D6 are given by Eqs. (8) and (9). The spuri- ous term (ss5s6

1+s4)s4

ρuy

y is due to the T-junction, and can be canceled by

(10)

appropriately weighting Eqs. (10) and (11) as:

u1− u0

s1 ·ρ1+ ρ0

2 +s6D5+ s5D6 s5+ s6



· 2 s1+ s4

+

u2− u0

s2 ·ρ2+ ρ0

2 +u3− u0

s3 ·ρ3+ ρ0

2



· 2 s2+ s3

·



1− s5s6 (s1+ s4)s4



= f0+ O(h). (12)

Although this scheme appears to be first-order accurate, it is indeed sec- ond-order accurate as in the one spatial dimension. Not surprisingly, this weighted scheme (12) reduces to the usual five point scheme in the case of a regular node:

u1−u0

s1 ·ρ10

2 +u4−u0

s4 ·ρ40

2



· 2 s1+s4

+

u2−u0

s2 ·ρ20

2 +u3−u0

s3 ·ρ30

2



· 2

s2+s3=f0+O(h), (13) where v4 is the direct neighboring node of v0 to the right.

4.1.3. Three Spatial Dimensions

In three spatial dimensions, more complex configurations can occur due to the adaptive nature of the Cartesian grid. The most general case is depicted in Fig. 4, where one 2D T-junction in the −x-direction and one 3D T-junction in the −y-direction are present. We emphasize that this is the most general case and that no other T-junctions can occur at a single node. In this case two ghost values u4 and u5 are linearly interpolated as:

u4=u7s8+ u8s7 s8+ s7

(14)

and

u5=u11s11s12+ u12s11s9+ u9s10s12+ u10s10s9

(s11+ s10)(s9+ s12) . (15) The backward difference (ρux) and (ρuy) at node v0 are also linearly interpolated as

(ρux)=ρ7+ ρ0

2 ·u7− u0

s4 · s8

s8+ s7+ρ8+ ρ0

2 ·u8− u0

s4 · s7 s8+ s7

(16)

(11)

and

(ρuy)= ρ11+ ρ0

2 ·u11− u0

s5 · s11s12 (s11+ s10)(s9+ s12) +ρ12+ ρ0

2 ·u12− u0

s5 · s11s9 (s11+ s10)(s9+ s12) +ρ10+ ρ0

2 ·u10− u0

s5 · s10s9 (s11+ s10)(s9+ s12) +ρ9+ ρ0

2 ·u9− u0

s5 · s10s12

(s11+ s10)(s9+ s12), (17) respectively.

The discretizations for (ρux)x, (ρuy)y, and (ρuz)z at the node v0, along with their Taylor series expansions, are given by

ρ1+ ρ0

2 ·u1− u0

s1 − (ρux)

 2

s1+ s4= (ρux)x+ s7s8

s4(s1+ s4)(ρuz)z+ O(h),

ρ2+ ρ0 (18)

2 ·u2− u0

s2 − (ρuy)

 2

s2+ s5= ρuy

y+ s9s12

s5(s2+ s5)(ρux)x + s10s11

s5(s2+ s5)(ρuz)z+ O(h) (19) and

ρ3+ ρ0

2 ·u3− u0

s3 +ρ6+ ρ0

2 ·u6− u0

s6

 2

s3+ s6= (ρuz)z+ O(h), (20)

respectively, where (ρux) and (ρuy) are given by Eqs. (16) and (17).

As in two spatial dimensions, a linear combination of Eqs. (18)–(20) allows for the cancellation of the spurious errors terms s s7s8

4(s1+s4)(ρuz)z,

s9s12

s5(s2+s5)(ρux)x, and ss10s11

5(s2+s5)(ρuz)z, yielding the following scheme:

ρ1+ ρ0

2 ·u1− u0

s1 + (ρux)

 2

s1+ s4

· α +

ρ2+ ρ0

2 ·u2− u0

s2 + (ρuy)

 2

s2+ s5

+

ρ3+ ρ0

2 ·u3− u0

s3 +ρ6+ ρ0

2 ·u6− u0

s6

 2

s3+ s6· β = f0+ O(h) (21)

(12)

with

α = 1 − s10s11 s5(s2+ s5), β = 1 − s9s12

s5(s2+ s5) −α s7s8

s4(s1+ s4). (22) Although this scheme appears to be first-order accurate, it is in fact sec- ond-order accurate as it is in the 1D case. Not surprisingly, this weighted scheme (21) reduces to the usual seven point scheme in the case of a reg- ular node:

u1− u0

s1 ·ρ1+ ρ0

2 +u4− u0

s4 ·ρ4+ ρ0

2



· 2 s1+ s4

+

u2− u0

s2 ·ρ2+ ρ0

2 +u5− u0

s5 ·ρ5+ ρ0

2



· 2 s2+ s5

+

u6− u0

s6 ·ρ6+ ρ0

2 +u3− u0

s3 ·ρ3+ ρ0

2



· 2

s6+ s3= f0+ O(h), (23) where v4 and v5 are the direct neighbors of v0 in the −x and −y- directions.

4.2. Discretization Near the Interface

In the case where one or more of the neighboring nodes involved in the spatial discretization, e.g., v1–v3, v5, v6 in Fig. 3 or v1–v3, v6–v12 in Fig. 4, are outside the irregular domain (i.e., φ is positive), the interface intersects between the node v0 and the neighboring node(s). By enforcing a band of uniform cells along the interface, we guarantee that only uni- form cells are cut by the interface, and in this case v0 is a regular node.

Let’s consider the 1D case, as depicted in Fig. 5, in which the interface intersects between v0 and v4 at vI. Denote by sI the distance between vI and v0. sI is approximated by finding the zero crossing of the quadratic

Fig. 5. v0 is a regular node and the interface Γ intersects between v0 and v4at vI.

(13)

interpolant φ= φ0+ φxs +12φxxs2, where φ is the signed distance level set function. Since v1 and v0 are inside the irregular domain with negative values in φ and v4 is outside with a positive φ, the quadratic interpolant in φ is convex with a positive φxx, and sI is calculated as:

sI=









−φx+

φx2− 2φxxφ0

φxx , if φxx> ,

φ0

φx if xx|  ,

(24)

where is a small positive number to avoid division by zero. φx and φxx

are approximated at v0 using central difference schemes:

φx=s1φ4−φs 0

4 + s4φ0−φ1

s1

s1+ s4

(25) and

φxx=

φ4− φ0

s4φ0− φ1

s1

 2

s1+ s4

. (26)

These schemes (25) and (26) are second-order accurate because of the locally uniform grid spacing near the interface.

Once we know the location of the interface point, the Dirichlet boundary value uI and ρI are either calculated with an analytic expres- sion or by quadratic interpolation using neighboring nodal values. Then the standard central difference scheme is used to approximate (ρux)x:

(ρux)x=

uI− u0

sI ·ρI+ ρ0

2 −u0− u1

s1 ·ρ1+ ρ0

2



· 2 sI+ s1

. (27)

When the interface intersects between the node and its neighboring nodes in any of the other directions, the discretization can be performed inde- pendently in a similar manner, which makes the method straightforward to implement in a dimension-by-dimension framework. In addition, the qua- dratic interpolation near the interface prevents that the largest error be systematically located near the interface, as pointed out in [14, 23] and guarantees second-order accuracy for both the solution and its gradients.

The resulting non-symmetric linear systems are diagonally dominant.

4.3. Heat Equation

We consider only the constant coefficient heat equation:

Tt= k∆T , (28)

(14)

noting that extension to the variable coefficient heat equation is straight- forward. Explicit schemes impose a time step restriction of ∆t(θ∆x)2k 2 for stability, where ∆x is the size of the smallest cell and θ is the smallest cell fraction for cells cut by the interface. Since θ can be arbitrarily small, so is the time step restriction ∆t, which leads to unpractical schemes.

Implicit schemes avoid such time step restrictions. We use the Crank–

Nicolson scheme to discretize the heat Eq. (28):

 I −1

2∆tk∆

 Tn+1=

 I +1

2∆tk∆



Tn, (29)

where I is the identity matrix and Tn is the solution at the nth time step.

The spatial discretization of the Laplace operator in Secs. 4.1 and 4.2, is used to approximate ∆T . Since the Crank–Nicolson scheme (29) is uncon- ditionally stable and second-order accurate we choose a time step ∆t pro- portional to ∆x.

4.4. Computing Second-Order Accurate Gradients

To compute the gradients to second-order accuracy when T-junctions are present, the ghost values u4 in Fig. 3 and u4, u5 in Fig. 4 are linearly interpolated as in Eqs. (6), (14), and (15). The spurious error caused by the interpolation is successfully removed and the gradients are computed in 2D (following the notations in Fig. 3) as:

ux = u4− u0

s4 · s1

s1+ s4+u0− u1

s1 · s4

s1+ s4s5s6s1 2s4(s1+ s4)uyy,

(30) uy = u3− u0

s3 · s2

s2+ s3+u0− u2

s2 · s3 s2+ s3

, where

uyy=

u3− u0

s3 +u2− u0

s2



· 2 s2+ s3

.

Following the notations in Fig. 4, the gradients in 3D are calculated as:

ux =u1− u0

s1 · s4 s1+ s4

+u0− u4

s4 · s1 s1+ s4

+s7s8 2s4 · s1

s1+ s4

· uzz, uy =u2− u0

s2 · s5

s2+ s5+u0− u5

s5 · s2

s2+ s5+s9s12 2s5 · s2

s2+ s5· uxx

+ s10s11 2s5 · s2

s2+ s5· uzz, uz =u6− u0

s6 · s3

s3+ s6+u0− u3

s3 · s3 s3+ s6

, (31)

(15)

where uxx, uyy, and uzz are given by solving Eqs. (18)–(20) simultaneously.

In the case where v0 is a regular node, Eqs. (31) and (31) reduce to the usual weighted average forward and backward differences:

ux = u4− u0

s4 · s1

s1+ s4+u0− u1

s1 · s4 s1+ s4

, uy = u3− u0

s3 · s2

s2+ s3+u0− u2

s2 · s3 s2+ s3

(32)

in 2D, and

ux = u1− u0

s1 · s4

s1+ s4+u0− u4

s4 · s1 s1+ s4

, uy = u2− u0

s2 · s5

s2+ s5+u0− u5

s5 · s2 s2+ s5

, uz= u6− u0

s6 · s3

s3+ s6+u0− u3

s3 · s6 s3+ s6

(33) in 3D. For nodes next to the interface, interface nodes are used in Eqs.

(32) and (33) instead of those neighboring nodes that are outside the domain. We note that the calculation of the gradient involves the same cells as those used in the discretization of the Poisson or heat equation, hence preserving the locality and ease of implementation of the method.

5. EXAMPLES

In this section, we present numerical evidence that confirms the schemes described in this paper produce second-order accuracy in the L1 and L norms for both the solution and its gradients. We use meshes for which the difference of level between adjacent cells can be greater than one, illustrating the fact that the method is supra-convergent on non- graded adaptive grids. The linear systems of equations are solved using the stabilized bi-conjugate gradient (Bi-CGSTAB) method with an incomplete LU preconditioner (see, e.g., [28]). In these examples, we solve the pois- son or heat equation on Ω only, noting that the procedure to obtain the solution on Ω+ is similar. We denote by min resoln and max resoln the minimum and maximum grid resolution corresponding to the coars- est and finest cells in the grid, respectively. Specifically, if the cell size is denoted by ∆x, then ∆x= L/min resoln for the coarsest cell and ∆x = L/max resoln for the finest cell, where L is the length of the computa- tional domain. In the following examples, we start with an initial adaptive grid, e.g., with (min resoln, max resoln)=(16, 128), and then recursively split each cell into four (in 2D) or eight cells (in 3D), which effectively

(16)

increases min resoln and max resoln by one, to obtain the convergence test results for the solution and its gradients. Other starting values of (min resoln, max resoln) can also be used to obtain similar results. We also assume the variable coefficients and the Dirichlet boundary values are defined on grid nodes. Therefore, the variable coefficients and the Dirichlet boundary values on the interface points are calculated by quadratic inter- polation using neighboring nodal values.

5.1. Poisson Equation 5.1.1. Example 1

Consider ∇ · (ρ∇u) = f on Ω = [−1, 1] × [−1, 1] with an exact solu- tion of u=e10(x2+y2 −0.752), where ρ=1. The interface is a circle on which φ =

x2+ y2−0.75=0. In this example, large solution gradients exist near the circular interface where we impose the finest grid resolution, while the solution near the center is smoother, where we can impose coarser grid resolution. We generate the adaptive grids by proximity to the interface, as described by the criterion in (4). Figure 6 depicts the adaptive Carte- sian grid with (min resoln, max resoln) = (16, 64), as well as the inter- face. The numerical solution on this grid is plotted in Fig. 7. Numerical

Fig. 6. Domain Ω= [−1, 1] × [−1, 1] and the spatial discretization in example 5.1.1 with (min resoln, max resoln)= (16, 64).

(17)

–1 –0.5

0 0.5

1

–1 –0.5 0 0.5 1 0.2 0.4 0.6 0.8

y x

u

Fig. 7. Graph of the solution in example 5.1.1, where (min resoln, max resoln)= (16, 64).

The dots represent the approximate solution and the mesh represents the exact solution.

Table I. Accuracy Results for the Solution u in Example 5.1.1

(min resoln, max resoln) Lerror Order L1 error Order

(32, 128) 6.042× 10−2 1.948× 10−2

(64, 256) 1.673× 10−2 1.852 5.136× 10−3 1.924

(128, 512) 4.279× 10−3 1.968 1.292× 10−3 1.991

(256, 1024) 1.075× 10−3 1.993 3.226× 10−4 2.001

accuracy test results for the solution and its gradients are given in Tables I and II, respectively.

In many applications (e.g., Stefan type of problems), high-order accuracy of the solution’s gradients at the interface is desired. In this example, numerical accuracy test is also performed for the gradient at

Table II. Accuracy Results for the Solution’s Gradients∇u in Example 5.1.1

(min resoln, max resoln) Lerror Order L1 error Order

(16, 128) 6.676× 10−1 3.897× 10−1

(32, 256) 2.014× 10−1 1.729 1.065× 10−1 1.872

(64, 512) 5.713× 10−2 1.818 2.739× 10−2 1.959

(128, 1024) 1.581× 10−2 1.853 6.914× 10−3 1.986

(18)

Table III. Accuracy Results for the Solution’s Gradients∇u on the Interface in Example 5.1.1

(min resoln, max resoln) Lerror Order L1 error Order

(16, 64) 2.749 1.260

(32, 128) 9.751× 10−1 1.495 3.977× 10−1 1.663

(64, 256) 2.949× 10−1 1.725 9.719× 10−2 2.033

(128, 512) 8.145× 10−2 1.857 2.568× 10−2 1.920

the interface, which is obtained by second-order extrapolation of the gradient from Ω to Ω+ followed by quadratic interpolation on the interface. Table III demonstrates that second-order accuracy of the solu- tion’s gradients can be obtained at the interface in both the L1 and L norms.

The resulting linear system is non-symmetric but diagonally domi- nant, which we solve with the stabilized bi-conjugate gradient (Bi-CGSTAB) method with an incomplete LU preconditioner. In [11], Gibou et al. pro- posed a symmetric solver for the Poisson and heat equation on irregular domains and uniform grids. The advantage of this method is the symmetry of the linear system, which can be inverted with a number of fast meth- ods, such as the conjugate gradient method with an incomplete Cholesky preconditioner [28]. However, the solutions gradients are only first-order accurate. We present a brief comparison between the method in Gibou et al. [11] with that of the present paper. We find that the present method compares favorably.

We plot the maximum solution and gradient errors as a function of the number of nodes inside the irregular domain in Figs. 8 and 9, respec- tively. It can be seen that while both methods yield second-order accu- rate solutions, the number of nodes in our method is about one order of magnitude less than that in [11], if the same error is to be obtained. Our method is also advantageous in that the maximum gradient error, which occurs near the interface in this example, decays quadratically, while it decays linearly in [11]. This is consistent with the argument in [14] about the method in [11]. Since different solvers of the linear system are used in these two methods, we also plot the maximum solution and gradient errors as a function of the computational time in Figs. 10 and 11, respectively.

Our method is obviously more efficient, especially when high accuracy of the gradient is desired. In these plots, the adaptive grid resolutions are (min resoln, max resoln) = (16, 64), (32, 128), (64, 256), (128, 512), and the uniform grid resolutions are 64× 64, 128 × 128, 256 × 256, 512 × 512.

(19)

102 103 104 105 106 10–4

10–3 10–2 10–1

number of nodes in the irregular domain

error

maximum solution error on adaptive grids maximum solution error on uniform grids

Fig. 8. Log–log plot of the solution error as a function of the number of nodes in the irreg- ular domain for example 5.1.1. Our method on adaptive grids is compared with that on uni- form grids in [11].

We also note that in term of speed, one should invest on the implementa- tion of the fast linear solver using for example multigrid methods, which are significantly more efficient than Bi-CGSTAB.

5.1.2. Example 2

Consider∇ ·(ρ∇u)=f on Ω =[−1, 1]×[−1, 1] with an exact solution of u= sin(x) sin(y) + e−100(x2+y2), where ρ= 1. The interface is a circle on which φ=

x2+ y2− 0.75 = 0. Large solution gradients are expected near the center of the circle where we put finer resolution in our adaptive grids, while solutions near the interface is smoother and we put coarser reso- lution there. An adaptive Cartesian grid with (min resoln, max resoln) = (16, 128), as well as the interface, are illustrated in Fig. 12. The numer- ical solution on this grid is plotted in Fig. 13. Numerical accuracy test results for the solution and its gradients are given in Tables IV and V, respectively.

(20)

102 103 104 105 106 10–3

10–2 10–1 100 101

number of nodes in the irregular domain

error

maximum gradient error on adaptive grids maximum gradient error on uniform grids

Fig. 9. Log–log plot of the gradient error as a function of the number of nodes in the irreg- ular domain for example 5.1.1. Our method on adaptive grids is compared with that on uni- form grids in [11].

Table IV. Accuracy results for the solution u in example 5.1.2

(min resoln, max resoln) Lerror Order L1 error Order

(16, 128) 2.120× 10−2 7.116× 10−3

(32, 256) 4.271× 10−3 2.311 1.747× 10−3 2.026

(64, 512) 9.358× 10−4 2.190 4.396× 10−4 1.990

(128, 1024) 2.332× 10−4 2.005 1.111× 10−4 1.985

Table V. Accuracy Results for the Solution’s Gradients∇u in Example 5.1.2

(min resoln, max resoln) Lerror Order L1 error Order

(16, 128) 3.323× 10−1 7.727× 10−2

(32, 256) 7.854× 10−2 2.081 1.845× 10−2 2.066

(64, 512) 1.893× 10−2 2.053 4.535× 10−3 2.025

(128, 1024) 4.878× 10−3 1.956 1.129× 10−3 2.006

(21)

10–2 10–1 100 101 102 10–4

10–3 10–2 10–1

time (seconds)

error

maximum solution error on adaptive grids maximum solution error on uniform grids

Fig. 10. Log–log plot of the solution error as a function of the computational time for example 5.1.1. Our method on adaptive grids is compared with that on uniform grids in [11].

5.1.3. Example 3

Consider ∇ · (ρ∇u) = f on Ω = [−1, 1] × [−1, 1] with an exact solu- tion of u= sin(πx) sin(πy), where ρ = sin(xy) + 2. This equation is solved within an annulus between two circles with radii being 0.25 and 0.75. In this example, and all the following examples in this paper, we generate the adaptive grids by the criterion in 4, and put the finest resolution in a uni- form band along the interface. A non-graded Cartesian grid with (min resoln, max resoln) = (8, 128), as well as the interface, are illustrated in Fig. 14. The numerical solution on this grid is plotted in Fig. 15. Numer- ical accuracy test results for the solution and its gradients are given in Tables VI and VII, respectively.

5.1.4. Example 4

Consider∇ ·(ρ∇u)=f on Ω =[−1, 1]×[−1, 1] with an exact solution of u= exy, where ρ= x2+ y2. The interface is diamond shaped, given by the set of points where φ= |y| + 1.5|x| − 0.75 = 0. A non-graded Cartesian grid with (min resoln, max resoln) = (8, 128), as well as the interface, are

(22)

10–2 10–1 100 101 102 10–3

10–2 10–1 100 101

time (seconds)

error

maximum gradient error on adaptive grids maximum gradient error on uniform grids

Fig. 11. Log–log plot of the gradient error as a function of the computational time for example 5.1.1. Our method on adaptive grids is compared with that on uniform grids in [11].

Fig. 12. Domain Ω= [−1, 1] × [−1, 1] and the spatial discretization in example 5.1.2 with (min resoln, max resoln)= (16, 128).

(23)

–1

–0.5 0

0.5 1

–1 –0.5 0 0.5 1 0 0.5 1

x y

u

Fig. 13. Graph of the solution in example 5.1.2, where (min resoln, max resoln) = (16, 128). The dots represent the approximate solution and the mesh represents the exact solution.

Fig. 14. Domain Ω= [−1, 1] × [−1, 1] and the spatial discretization in example 5.1.3 with (min resoln, max resoln)= (8, 128).

참조

관련 문서

The “Asset Allocation” portfolio assumes the following weights: 25% in the S&amp;P 500, 10% in the Russell 2000, 15% in the MSCI EAFE, 5% in the MSCI EME, 25% in the

In addition to the problem of this bias, the problem caused by using the time variable with a weighted wage rate may be a multicollinearity between time value (=time x

Histogram shows the difference of pleural effusion volume depending on the experimental conditions in freshwater group... Youn Shin

Degree Centrality The counts of how many connections a node has Popularity or influence of a node (e.g., word, person) in the network Betweenness Centrality The extent to which

• Useful if the forces or torques acting on the object or mechanical part are difficult to determine.. • Very useful for more complicated systems later (MDOF and

“Electron that moves in a periodically varying potential field can only occupy certain allowed energy zone”.. Solution

• The molar volume at given pressure and temperature can be calculated by solving the equation of state or the cubic equation for V. • Compared to the Z equations

with the experimental C versus t data. If the fit is unsatisfactory, another rate equation is guessed and tested. Integral method is especially useful for fitting simple