
In this paper, a new Cartesian grid finite difference method is introduced to solve two-dimensional parabolic interface problems with second order accuracy achieved in both temporal and spatial discretization. Corrected central difference and the Matched Interface and Boundary (MIB) method are adopted to restore second order spatial accuracy across the interface, while the standard Crank-Nicolson scheme is employed for the implicit time stepping. In the proposed augmented MIB (AMIB) method, an augmented system is formulated with auxiliary variables introduced so that the central difference discretization of the Laplacian could be disassociated with the interface corrections. A simple geometric multigrid method is constructed to efficiently invert the discrete Laplacian in the Schur complement solution of the augmented system. This leads a significant improvement in computational efficiency in comparing with the original MIB method. Being free of a stability constraint, the implicit AMIB method could be asymptotically faster than explicit schemes. Extensive numerical results are carried out to validate the accuracy, efficiency, and stability of the proposed AMIB method.
Citation: Hongsong Feng, Shan Zhao. A multigrid based finite difference method for solving parabolic interface problem[J]. Electronic Research Archive, 2021, 29(5): 3141-3170. doi: 10.3934/era.2021031
[1] | Hongsong Feng, Shan Zhao . A multigrid based finite difference method for solving parabolic interface problem. Electronic Research Archive, 2021, 29(5): 3141-3170. doi: 10.3934/era.2021031 |
[2] | Youngmok Jeon, Dongwook Shin . Immersed hybrid difference methods for elliptic boundary value problems by artificial interface conditions. Electronic Research Archive, 2021, 29(5): 3361-3382. doi: 10.3934/era.2021043 |
[3] | Derrick Jones, Xu Zhang . A conforming-nonconforming mixed immersed finite element method for unsteady Stokes equations with moving interfaces. Electronic Research Archive, 2021, 29(5): 3171-3191. doi: 10.3934/era.2021032 |
[4] | Yijun Chen, Yaning Xie . A kernel-free boundary integral method for reaction-diffusion equations. Electronic Research Archive, 2025, 33(2): 556-581. doi: 10.3934/era.2025026 |
[5] | Guanrong Li, Yanping Chen, Yunqing Huang . A hybridized weak Galerkin finite element scheme for general second-order elliptic problems. Electronic Research Archive, 2020, 28(2): 821-836. doi: 10.3934/era.2020042 |
[6] | Lian Zhang, Mingchao Cai, Mo Mu . Decoupling PDE computation with intrinsic or inertial Robin interface condition. Electronic Research Archive, 2021, 29(2): 2007-2028. doi: 10.3934/era.2020102 |
[7] | Michael Barg, Amanda Mangum . Statistical analysis of numerical solutions to constrained phase separation problems. Electronic Research Archive, 2023, 31(1): 229-250. doi: 10.3934/era.2023012 |
[8] | Haiyan Song, Fei Sun . A numerical method for parabolic complementarity problem. Electronic Research Archive, 2023, 31(2): 1048-1064. doi: 10.3934/era.2023052 |
[9] | Yujia Chang, Yi Jiang, Rongliang Chen . A parallel domain decomposition algorithm for fluid-structure interaction simulations of the left ventricle with patient-specific shape. Electronic Research Archive, 2022, 30(9): 3377-3396. doi: 10.3934/era.2022172 |
[10] | Changling Xu, Huilai Li . Two-grid methods of finite element approximation for parabolic integro-differential optimal control problems. Electronic Research Archive, 2023, 31(8): 4818-4842. doi: 10.3934/era.2023247 |
In this paper, a new Cartesian grid finite difference method is introduced to solve two-dimensional parabolic interface problems with second order accuracy achieved in both temporal and spatial discretization. Corrected central difference and the Matched Interface and Boundary (MIB) method are adopted to restore second order spatial accuracy across the interface, while the standard Crank-Nicolson scheme is employed for the implicit time stepping. In the proposed augmented MIB (AMIB) method, an augmented system is formulated with auxiliary variables introduced so that the central difference discretization of the Laplacian could be disassociated with the interface corrections. A simple geometric multigrid method is constructed to efficiently invert the discrete Laplacian in the Schur complement solution of the augmented system. This leads a significant improvement in computational efficiency in comparing with the original MIB method. Being free of a stability constraint, the implicit AMIB method could be asymptotically faster than explicit schemes. Extensive numerical results are carried out to validate the accuracy, efficiency, and stability of the proposed AMIB method.
The paper is focused on the following two dimensional (2D) parabolic interface problem
∂u∂t=∇⋅(β∇u)+f,inΩ⊂R2 | (1) |
with Dirichlet boundary conditions imposed along the boundary
[[u]]:=u+−u−=ϕ(x,y,t), | (2) |
[[βun]]:=β+∇u+⋅→n−β−∇u−⋅→n=ψ(x,y,t), | (3) |
where superscripts
The parabolic interface problem modeled by (1) - (3) plays important roles in multiple physical and engineering applications. The conductive heat transfer process over composite media is widely investigated through this model when the interface conditions are homogeneous, i.e.,
Various specially designed numerical schemes with the jump conditions being incorporated into discretization have been introduced in the literature for solving parabolic interface problems. These include finite element methods and finite volume methods based on body-fitted interface treatments [3,8,32,33,34], finite difference methods based on Cartesian grids [2,5,6,17,18,19,20,22,24,30,36,40], and immersed finite element methods based on Cartesian meshes [25,39]. For instance, the immersed interface method (IIM) is one of the most successful finite difference methods in solving parabolic interface problems [5,6,18,19,20]. By avoiding mesh generation, generalized Taylor expansions are adopted to locally modify the finite difference weights so that the accuracy loss across the interface can be recovered.
Time integration is also crucial to the numerical solution of parabolic interface problems. Explicit time stepping would require a severe stability restriction with the time step size
The core philosophy of ADI methods [12,11,29] is to reduce a multidimensional system from discretizing parabolic equation to a sequence of independent one-dimensional (1D) sub-systems of tridiagonal structure, which can be solved efficiently with the Thomas algorithm [31]. Compared with generic iterative solvers, ADI methods can be regarded as an exact solver due to the fact that computation will be completed within a fixed number of steps. Recently, ADI schemes have been developed to cope with parabolic interface problems with desired ADI efficiency maintained. Li and Mayo [22] introduced the first ADI algorithm with help of the IIM to correct local differences near interface when facing a special interface jump with
The multigrid method is another popular fast solver used in solving PDEs with discontinuous coefficients. Based on structured or unstructured meshes, approaches for constructing interpolation, smoothing operators and coarse gird points selection would require special designs [7]. Algebraic multigrid (AMG) [28] selects coarse grid points in a pure algebraic sense to define interpolation without interface geometry and dimensionality needed in the construction. Yet it exploits the discontinuous coefficients and geometry in the matrix-dependent interpolation. A great amount of storage is usually needed for its coarse grid operator matrices generated by Galerkin process. Recently, the AMG scheme has been successfully applied in the immersed finite element method for solving both stationary and moving interface problems [13]. Geometric multigrid method is the other class of multigrid methods, which includes interface geometry in the process of discretization to the PDE with related boundary and interface jump conditions. In [2], Adams and Li proposed a 2D IIM multigrid method, which preserves maximum principle. Black box multigrid interpolation is adopted away from the interface, while interpolation weights are derived with help of Taylor expansion for the grid points adjacent to the interface. Later on, an improved IIM based multigrid method [1] has been developed with interpolation and restriction operators being modified such that coarse-grid matrices are M-matrices. The number of
In this paper, we propose a new geometric multigrid method based on the augmented matched interface and boundary (AMIB) method for solving parabolic interface problems. The AMIB method was originally designed to solve elliptic interface problems [14,15,16]. With a FFT acceleration, the AMIB method can deliver fourth order accuracy in treating both interfaces [16] and boundaries [15]. Nevertheless, the AMIB method has never been coupled with a multigrid method before. In this study, due to the augmented approach adopted, the finite difference interface treatment and the multigrid solution procedure can be decoupled in the proposed AMIB method. This considerably simplifies the interpolation and restriction process for the coarse grid operators in the multigrid method. Hence standard multigrid components can be applied in such augmented framework with the advantages including that storage for coarse grid matrix is avoided and the implementation is fairly simple. Second order corrected central differences are applied for spatial accuracy to compensate accuracy loss across the interface, and the Crank-Nicolson scheme is used for temporal discretization. This leads to second order accuracy in both space and time, while the multigrid approach considerably accelerates the computational speed.
The rest of the paper is organized as follows. Section 2 focuses on discussion of the several key aspects of the proposed efficient algorithm. In section 3, numerical experiments are implemented to justify the effectiveness of our method in solving parabolic interface problems. Comparisons to other methods are carried out to show the efficiency of our method. A summary and acknowledgment are included in the end of the paper.
In this work, we focus on the piecewise constant coefficient parabolic interface problem. We first rewrite the original problem
1β∂u∂t=Δu+fβ,inΩ+∪Ω−∖Γ. | (4) |
Subject to the same initial, boundary, and interface conditions, the solution to (4) is equivalent to that of (1). We partition the given rectangular domain
xi=a+ih,yj=c+jh,i=0,⋯,nx,j=0,⋯,ny. |
Assume that the interface
Γ={(x,y),φ(x,y)=0}, |
with
Γ={(x,y),φ(x,y)=0}, |
The subscript
Moreover, a uniform time increment
For temporal discretization, the Crank-Nicolson scheme is adopted
un+1i,j−uni,jβi,j△t=12Δuni,j+12Δun+1i,j+12βi,j(fni,j+fn+1i,j), | (5) |
which has the equivalent form below after reorganizing the terms in (5)
2βi,j△tun+1i,j−Δun+1i,j=2βi,j△tuni,j+Δuni,j+1βi,j(fni,j+fn+1i,j). | (6) |
The above Crank-Nicolson scheme admits a second order temporal truncation error. Note that the Laplacian terms at time step
Ignoring the time dependence, we concern ourselves with second order spatial discretization to the Laplacian operator
Δu=∂2u∂x2+∂2u∂y2. |
We may focus the discussion on
uxx(xi)=u(xi+1)−2u(xi)+u(xi−1)h2−112h2uxxxx(xi)+O(h4). | (7) |
The above formulation (7) is applicable to the case of regular points, while approximation in irregular points needs different treatment due to the fact that function loses regularity across the interface. Corrected differences are employed below [37]:
Jump-corrected difference. Suppose
uxx(xi)≈u(xi+1)−2u(xi)+u(xi−1)h2−1h2K∑k=0(h+)kk![u(k)], | (8) |
uxx(xi+1)≈u(xi+2)−2u(xi+1)+u(xi)h2+1h2K∑k=0(h−)kk![u(k)], | (9) |
where
The global regularity for
The corrected differences in Eqns.(8) and (9) will reduce to Eq. (7) with the introduced jump terms vanishing if no interface is met. Such jump quantities are compensating for the function discontinuity across the interface. Since the derivative jumps in the correction terms are not analytically available, numerical approximations are needed for the corrected differences to be applied at irregular points. In following subsection, a systematical procedure is discussed for reconstruction of the derivative jumps with aid of fictitious values generated by the matched interface and boundary (MIB) method [42].
The derivative jumps in the above corrected differences are defined as
[∂ku∂xk]|x=α=limx→α+∂ku∂xk−limx→α−∂ku∂xk, | (10) |
where
For the sake of accuracy and stability, it is better to approximate each one-sided derivative limit with central or pseudo-central difference. As shown in Fig. 1, if one layer of fictitious values is available on each side of the interface
[∂ku∂xk]|x=α≈(wki,jˆui,j+2∑l=1wki+l,jui+l,j)−(2∑l=1wki−2+l,jui−2+l,j+wki+1,jˆui+1,j), | (11) |
where the linear combinations in the two parenthesis denote the derivatives of the two constructed Lagrange polynomials for approximating one-sided derivative limits at
It is possible that only one real function value is available on one side of the interface due to sharp topology change of the interface. To deal with such a corner case [14], a fictitious value is employed at where the needed real value is missing. Just consider the derivative jumps at
Likewise, the discretization for the
The jump conditions
[[uτ]]=u+τ−u−τ=ρ(x,y). | (12) |
Consider a point
[[u]]=u+−u−=ϕ(x∗,y∗), | (13) |
[[uτ]]=(−u+xsinθ+u+ycosθ)−(−u−xsinθ+u−ycosθ)=ρ(x∗,y∗), | (14) |
[[βun]]=β+(u+xcosθ+u+ysinθ)−β−(u−xcosθ+u−ysinθ)=ψ(x∗,y∗). | (15) |
In this way, jump conditions from tangential or normal direction are transformed into
If
[[u]]=u+−u−,[[βun]]−β−tanθ[[uτ]]=C+xu+x−C−xu−x+C+yu+y, | (16) |
where
If
[[u]]=u+−u−,[[βun]]+β−cotθ[[uτ]]=D+yu+y−D−yu−y+D+xu+x, | (17) |
where
Eqns. (16) and (17) allow us to reduce the 2D jump conditions to 1D ones along Cartesian direction provided that
[[u]]=W+0U+−W−0U− | (18) |
[[βun]]−β−tanθ[[uτ]]=C+xW+1U+−C−xW−1U−+C+yP+Uo, | (19) |
with the following vector representations
[[βun]]−β−tanθ[[uτ]]=C+xW+1U+−C−xW−1U−+C+yP+Uo, | (19) |
Here
With the function values in
ˆui,j=∑(xI,yJ)∈Si,jWI,JuI,J+W0[[u]]+W1[[uτ]]+W2[[βun]]=∑(xI,yJ)∈Si,jWI,JuI,J+W0ϕ(x∗,y∗)+W1ρ(x∗,y∗)+W2ψ(x∗,y∗), | (20) |
where
In this manner, the needed two layers of fictitious values can be generated along
Remark 1. The above MIB formulation utilizes extrapolations in
Remark 2. It is found in our experiments that the accuracy of derivative jump reconstruction in Eq. (11) could be affected by the fictitious value generated by MIB-PLUS or MIB-MINUS depending on
Great details have been given to demonstrate how corrected differences are used to approximate the Laplacian operator. The right side of the Crank-Nicolson scheme (6) can be easily determined once the information of solution
The right hand side of the time-stepping scheme (6) can be explicitly calculated with the known information on boundary or interface conditions, while the left hand side of (6) needs efficient algorithm design. For this purpose, we introduce auxiliary variables to form an augmented system.
With the general formulation of fictitious values in (20), the approximation (11) can be well defined. At each intersection point between the interface
CkU+[∂ku∂xk]=Φk, | (21) |
where
CU+IQ=Φ, | (22) |
where
Let
DhUn+1i,j−LhUn+1i,j−Cn+1i,j=DhUni,j+LhUni,j+Cni,j+1βi,j(fn+1i,j+fni,j),for1≤i≤nx−1,1≤j≤ny−1, | (23) |
where
LhUi,j:=Ui+1,j+Ui−1,j+Ui,j+1+Ui,j−1−4Ui,jh2, | (24) |
DhUi,j:=2βi,j△tUi,j. | (25) |
Note that the subscript
DUn+1+ˆAUn+1+BQn+1=DUn−ˆAUn−BQn+ˆFn | (26) |
where
AU+BQ=F, | (27) |
after we combine the coefficient matrix
We need to determine
KW=R, | (28) |
where
K=(ABCI),W=(UQ),andR=(FΦ). |
Note that the dimensions of matrix
The matrix structure of
In each time step, we aim at solving
AU=F−BQ, | (29) |
after we determine
(I−CA−1B)Q=Φ−CA−1F, | (30) |
which is obtained by eliminating
Note that the linear system (30) for
● GMRES approach.
1. As a linear system, the right hand side RHS =
2. For the left hand side(LHS), we may consider an iteration approach by the GMRES method. In this approach, the matrix vector product of
3. For the first time step
● LU approach.
1. The first step is the same as that in the above GMRES approach.
2. For the left hand side(LHS), we will explicitly construct the matrix
3. The solution
Remark 3. The efficiency of GMRES approach depends on the iteration number for the GMRES iteration process. Note that each iteration involves one multigrid inversion with a complexity
Remark 4. The strategy of LU approach is different from GMRES approach in the sense that the Schur complement matrix is formed with multigrid algorithm applied for each column of matrix
Remark 5. The complexities of the two approaches are in the same magnitude. As it is second order accurate for both temporal and spatial discretization, it is reasonable to set time increment
O(N)×M+O(M2)×Nt+23M2=C2NM+C1M2Nt+23M2=C1C20n2C3n+C2n2C0n+23C30n2=C1C20C3n3+C2C0n3+23C30n2=C0(C0C1C3+C2+23C20)n3, |
where the first and second term in the first equality indicates the total sum of matrix generation cost arising from multigrid solver and the cost of multigrid for inversion deployed on (29) and right side of (30), and the LU forward and backward substitution cost in all time evolution steps. Besides, the last term in the first equality denotes the LU decomposition for the generated matrix in the first time stepping.
The computational complexity of the GMRES approach is
O(N)×C4×Nt=C2n2C4C3n=C2C3C4n3=C3(C2C4)n3, |
where
The computational complexities of the two approaches are all of
Remark 6. When an explicit finite difference method is employed to solve parabolic PDEs, a stability condition with
In the preceding section, a multigrid approach has been assumed in the discussion of building efficient algorithm. In this section, details on this solver are provided.
The multigrid approach is an efficient algebraic algorithm for solving a linear system
AU=B | (31) |
with known matrix
−Δu+a(x,y)u=b(x,y), | (32) |
where the domain and its partition are the same as that for the problem in this work, the discrete values of
To be more clear, at the interior node,
a(xi,yj)=D((j−1)nx+i,(j−1)nx+i),b(xi,yj)=B((j−1)nx+i,(j−1)nx+i), |
for
b(xi,yj)=B((j−1)nx+i,(j−1)nx+i), | (33) |
for
The discrete problem can then be reformulated as below according to the discrete data,
−LhUh+DhUh=bhinΩh, | (34) |
BhUh=bh,on∂Ωh, | (35) |
where
This makes it possible for applying multigrid method to solve the linear system (31) efficiently. Once
The main idea of multigrid method lies in reducing the high frequency components of solution error on fine mesh, and that the low frequency errors are solved on coarse grids. Due to the fact that low frequency components of the errors can not be effectively reduced, the residual is restricted to coarser grids such that the low frequency errors are solved therein. Such determined errors are then interpolated onto fine meshes to provide some correction to the already obtained solution on fine meshes. Over the process, relaxation is needed on fine mesh to improve the solution accuracy, while restriction operator is imposed from fine mesh to coarse mesh and interpolation is needed from coarse mesh to fine mesh. Such process is iterated until the solution meets certain accuracy.
The relaxation is used to reduce errors in two aspects. One is for smoothing the high frequency component on the fine mesh. The other is used after the obtained errors are interpolated to add correction on solution on fine mesh. In this case, the relaxation is to reduce the error introduced from interpolation. In this work, we adopt the red-black Gauss-Seidal smoother as the relaxation scheme. The two-grid correction scheme as the simplest multigrid adopts only two level of meshes to achieve the solution correction via iteration between restriction and interpolation. We use such two-grid correction scheme to illustrate the way we apply multigrid scheme to obtain the solution of the linear system (31).
Algorithm 1 Two-grid correction scheme |
1: The initial guess for |
2: Relax Eq.(34) |
3: Compute the residual on fine grid, |
4: for |
5: Restrict the residual to coarse grid |
6: Exactly solve for the solution |
7: Interpolate the correction to fine grid |
8: Apply the correction to get a better approximation |
9: Relax the Eq.(34) |
10: Compute the residual on fine grid, |
11: end for |
The above process continues until convergence. In our multigrid approach, we generalize the above process to more grid levels to avoid the exact correction solution for Eq.(36) in case that the cost is still very high on that coarse grid. This promotes the necessity of even coarser grids for correction solutions. The above procedure demonstrates the two-grid correction scheme using
Restriction and interpolation are two needed transfer operators in the correction procedure. In our implementation, it is sufficient to adopt the following standard full-weighting stencil for restriction,
RHh=116[121242121]Hh, | (37) |
and the following standard interpolation scheme
IhH=14]121242121[hH. | (38) |
The subscript
For the practical implementation of our multigrid algorithm for problem (34)(35), we set both
In this section, numerical experiments are carried out to demonstrate the accuracy, efficiency and stability of the proposed two AMIB algorithms for solving parabolic interface problems. For sake of notation, we name the AMIB method coupled with the GMRES approach on Schur complement as AMIB-GMRES, while the AMIB method associated with LU decomposition is called as AMIB-LU. For comparison purpose, the standard MIB method [42] with Crank-Nicolson scheme for time-stepping is also implemented.
For simplicity, a square domain with uniform number of partitions in each direction is assumed. We consider the number as
The iteration solver used in MIB method is biconjugate gradient iterative solver [31]. The maximal iteration number is 5000, and the tolerance error is set as
All the experiments were carried out on MacBook Pro with 8.00 RAM and Intel 2.3 GHz Intel Core i5.
Example 1. In this example, we consider a parabolic problem on a square domain
u(x,y)={sin(t)+e−x−y,r≤0.5,sin(t)+ex+y,otherwise, | (39) |
with the diffusion coefficients
β={1,r≤0.5,10,otherwise. |
Here we call
[u]=e12(cos(θ)+sin(θ))−e−12(cos(θ)+sin(θ))[βun]=β+(cos(θ)e12(cos(θ)+sin(θ))+sin(θ)e12(cos(θ)+sin(θ)))+β−(cos(θ)e−12(cos(θ)+sin(θ))+sin(θ)e−12(cos(θ)+sin(θ)))[uτ]=β+(sin(θ)e12(cos(θ)+sin(θ))−cos(θ)e12(cos(θ)+sin(θ)))+β−(sin(θ)e−12(cos(θ)+sin(θ))−cos(θ)e−12(cos(θ)+sin(θ))) |
It follows the same principle in below notations. The source term
f(x,y)={(cos(t)−2β−sin(t))e−x−y,r≤0.5,(cos(t)−2β+sin(t))ex+y,otherwise. |
The initial condition and boundary conditions can be easily determined by the analytical solutions. Beside, we may observe that both the zeroth and first order jump conditions on the interface are time-independent. To test spatial convergence rate, we consider the fixed stopping time at
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
2.08E-4 | – | 8.82E-4 | – | 0.94 | |
3.21E-5 | 2.70 | 1.69E-4 | 2.38 | 5.48 | |
7.52E-6 | 2.09 | 3.13E-5 | 2.43 | 26.6 | |
1.94E-6 | 1.95 | 9.07E-6 | 1.79 | 175 | |
5.66E-7 | 1.95 | 2.97E-6 | 1.79 | 1143 | |
AMIB-LU | |||||
Error | Order | Error | Order | ||
2.08E-4 | – | 8.82E-4 | – | 0.30 | |
3.19E-5 | 2.70 | 1.68E-4 | 2.38 | 1.49 | |
7.52E-6 | 2.09 | 3.13E-5 | 2.43 | 6.50 | |
1.94E-6 | 1.95 | 9.08E-6 | 1.79 | 29.8 | |
5.71E-7 | 1.95 | 2.99E-6 | 1.79 | 200 | |
MIB | |||||
Error | Order | Error | Order | ||
2.07E-4 | – | 8.75E-4 | – | 0.62 | |
3.19E-5 | 2.70 | 1.68E-4 | 2.38 | 4.76 | |
7.50E-6 | 2.08 | 3.13E-5 | 2.42 | 35.4 | |
1.94E-6 | 1.94 | 9.09E-6 | 1.79 | 336 | |
5.66E-7 | 1.95 | 2.97E-6 | 1.79 | 2935 |
On the other hand, the temporal convergence needs to be tested. For such concern, the spatial partition in each direction is set to be
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
1.32E-4 | – | 5.46E-4 | – | 2.76 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 5.28 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.13 | 9.73 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.99 | 19.36 | |
1.56E-6 | 1.99 | 4.88E-6 | 2.02 | 37.88 | |
6.26E-7 | 1.32 | 3.21E-6 | 0.60 | 76.9 | |
5.60E-7 | 0.16 | 2.99E-6 | 0.10 | 148.4 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
1.32E-4 | – | 5.46E-4 | – | 58 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 59.4 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.13 | 61.5 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.99 | 63.2 | |
1.56E-6 | 1.99 | 4.88E-6 | 1.94 | 64.7 | |
6.34E-7 | 1.30 | 3.24E-6 | 0.59 | 66.8 | |
5.76E-7 | 0.13 | 3.04E-6 | 0.09 | 74 | |
MIB | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
1.32E-4 | – | 5.46E-4 | – | 21.97 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 42.34 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.14 | 81.72 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.98 | 153.34 | |
1.56E-6 | 1.99 | 4.88E-6 | 1.94 | 287.03 | |
6.27E-7 | 1.31 | 3.22E-6 | 0.60 | 533 | |
5.69E-7 | 0.14 | 3.02E-6 | 0.09 | 863 |
Example 2. In this example, we consider a parabolic problem on a square domain
u(x,y)={sin(kx)cos(ky)cos(t),r≤0.5,cos(kx)sin(ky)cos(t),otherwise, | (40) |
The source terms can be correspondingly determined,
f(x,y)={(2k2β−cos(t)−sin(t))sin(kx)cos(ky),r≤0.5,(2k2β+cos(t)−sin(t))cos(kx)sin(ky),otherwise. |
The zeroth and first order interface can be found to be time and space dependent, representing the most general jump conditions. In this example, we consider
It is also reasonable to approximate the equation (4) with
un+1i,j−uni,jβi,j△t=12Δuni,j+12Δun+1i,j+1βi,jfn+12i,j, | (41) |
with the difference to Eq.(5) on the approximation to
AMIB-GMRES- |
AMIB-GMRES | |||||||||
CPU | CPU | |||||||||
Error | Order | Error | Order | Error | Order | Error | Order | |||
3.22E-2 | – | 7.55E-2 | – | 3.04 | 1.39E-3 | – | 3.43E-3 | – | 2.81 | |
5.56E-3 | 2.53 | 1.57E-2 | 2.27 | 5.9 | 3.14E-4 | 2.15 | 7.77E-4 | 2.14 | 5.69 | |
9.47E-4 | 2.55 | 2.94E-3 | 2.42 | 12.5 | 7.59E-5 | 2.05 | 1.88E-4 | 2.05 | 11.2 | |
1.67E-4 | 2.50 | 4.35E-4 | 2.76 | 23 | 1.89E-5 | 2.01 | 4.68E-5 | 2.01 | 22 | |
3.82E-5 | 2.13 | 8.32E-5 | 2.39 | 45 | 5.00E-6 | 1.92 | 1.21E-5 | 1.95 | 45.4 | |
9.68E-6 | 1.99 | 2.13E-5 | 1.98 | 87 | 1.44E-6 | 1.80 | 3.30E-6 | 1.87 | 96.3 | |
2.579E-6 | 1.91 | 6.05E-6 | 1.82 | 168 | 6.60E-7 | 1.13 | 2.84E-6 | 0.22 | 170 | |
9.03E-7 | 1.53 | 3.25E-6 | 0.91 | 334 | ||||||
AMIB-LU- |
AMIB-LU | |||||||||
CPU | CPU | |||||||||
Error | Order | Error | Order | Error | Order | Error | Order | |||
3.22E-2 | – | 7.55E-2 | – | 65 | 1.40E-3 | – | 3.44E-3 | – | 57 | |
5.56E-3 | 2.53 | 1.57E-2 | 2.27 | 69 | 3.15E-4 | 2.15 | 7.79E-4 | 2.15 | 59.6 | |
9.47E-4 | 2.55 | 2.94E-3 | 2.42 | 62 | 7.64E-5 | 2.04 | 1.89E-4 | 2.04 | 58.9 | |
1.67E-4 | 2.50 | 4.35E-4 | 2.76 | 62 | 1.90E-5 | 2.01 | 4.70E-5 | 2.01 | 57.7 | |
3.82E-5 | 2.13 | 8.32E-5 | 2.39 | 60.6 | 4.82E-6 | 1.98 | 1.17E-5 | 2.01 | 60.7 | |
9.65E-6 | 1.99 | 2.11E-5 | 1.98 | 66 | 1.34E-6 | 1.85 | 3.05E-6 | 1.94 | 64.6 | |
2.57E-6 | 1.91 | 5.98E-6 | 1.82 | 75.1 | 6.16E-7 | 1.12 | 2.70E-6 | 0.18 | 75.9 | |
8.88E-7 | 1.53 | 3.18E-6 | 0.91 | 91 | ||||||
5.69E-7 | 0.64 | 2.76E-6 | 0.20 | 129 |
AMIB-GMRES- |
AMIB-GMRES | |||||||||
CPU | CPU | |||||||||
Error | Order | Error | Order | Error | Order | Error | Order | |||
1.15E-4 | – | 5.16E-4 | – | 1.11 | 2.25E-4 | – | 5.16E-4 | – | 1.19 | |
1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 7.39 | 1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 7.86 | |
1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 42 | 1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 43 | |
2.06E-6 | 2.82 | 1.54E-5 | 2.61 | 264 | 2.04E-6 | 2.82 | 1.04E-5 | 2.61 | 258 | |
5.18E-7 | 2.01 | 2.65E-6 | 1.99 | 1457 | 5.05E-7 | 2.01 | 2.62E-6 | 1.99 | 1463 | |
AMIB-LU- |
AMIB-LU | |||||||||
CPU | CPU | |||||||||
Error | Order | Error | Order | Error | Order | Error | Order | |||
1.15E-4 | – | 5.16E-4 | – | 0.34 | 2.25E-4 | – | 5.16E-4 | – | 0.7 | |
1.10E-4 | 0.06 | 3.42E-4 | 0.59 | 1.66 | 1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 1.78 | |
1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 8.04 | 1.44E-5 | 2.93 | 6.40E-5 | 2.43 | 8.76 | |
2.06E-6 | 2.81 | 1.05E-5 | 2.61 | 39.4 | 2.05E-6 | 2.91 | 1.04E-5 | 1.79 | 41.6 | |
5.28E-7 | 1.96 | 2.68E-6 | 1.97 | 231 | 5.15E-7 | 1.99 | 2.65E-6 | 1.99 | 227 |
AMIB-GMRES | ||||||
Small |
Large |
|||||
CPU time(s) | CPU time(s) | |||||
1.63E-5 | 5.11E-5 | 71.4 | 1.86E-5 | 6.70E-5 | 92.6 | |
1.63E-5 | 5.10E-5 | 65.4 | 1.86E-5 | 6.69E-5 | 92.8 | |
1.61E-5 | 5.04E-5 | 52.4 | 1.84E-5 | 6.60E-5 | 69.3 | |
1.47E-5 | 4.43E-5 | 31.4 | 1.65E-5 | 5.74E-5 | 33.8 | |
9.48E-6 | 4.71E-5 | 36.2 | 7.01E-6 | 3.44E-5 | 36.2 | |
6.03E-5 | 1.56E-4 | 58.3 | 6.20E-5 | 1.45E-4 | 66.4 | |
4.66E-4 | 9.00E-4 | 67.8 | 6.38E-4 | 1.19E-3 | 81.6 | |
5.26E-4 | 8.52E-4 | 71.2 | 5.62E-3 | 1.02E-2 | 89.5 | |
AMIB-LU | ||||||
Small |
Large |
|||||
CPU time(s) | CPU time(s) | |||||
1.63E-5 | 5.11E-5 | 10.9 | 1.86E-5 | 6.72E-5 | 10.9 | |
1.63E-5 | 5.10E-5 | 10.58 | 1.86E-5 | 6.71E-5 | 10.46 | |
1.61E-5 | 5.04E-5 | 8.8 | 1.84E-5 | 6.61E-5 | 9.1 | |
1.47E-5 | 4.43E-5 | 6.8 | 1.66E-5 | 5.75E-5 | 6.9 | |
9.48E-6 | 4.71E-5 | 7.0 | 7.03E-6 | 3.43E-5 | 6.9 | |
6.03E-5 | 1.56E-4 | 9.2 | 6.20E-5 | 1.45E-4 | 8.5 | |
4.66E-4 | 9.00E-4 | 8.6 | 6.38E-4 | 1.19E-3 | 8.6 | |
5.29E-4 | 8.56E-4 | 9.0 | 5.63E-3 | 1.02E-2 | 8.7 |
The error versus time partition increment
On the other hand, the spatial convergence are investigated on the two methods. The stopping time is fixed as
We then want to study the impact of ratio of
Note that the "Small
Example 3. We are interested in the performance of the two AMIB methods on complicated interface shape. In this example, we focus on the case of interface shape governed by parametric function
r=0.5+0.1sin(3θ), | (42) |
embedded in the domain
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
6.70E-4 | – | 2.17E-3 | – | 1.67 | |
1.52E-4 | 2.14 | 5.05E-4 | 2.10 | 9.82 | |
3.63E-5 | 2.07 | 1.39E-4 | 1.86 | 53 | |
8.62E-6 | 2.07 | 3.52E-5 | 1.98 | 399 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
6.70E-4 | – | 2.17E-3 | – | 0.42 | |
1.52E-4 | 2.14 | 5.05E-4 | 2.10 | 1.94 | |
3.63E-5 | 2.07 | 1.39E-4 | 1.86 | 8.54 | |
8.62E-6 | 2.07 | 3.52E-5 | 1.98 | 45.5 |
We next examine the temporal order of the two AMIB methods by setting
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.83E-5 | – | 2.18E-4 | – | 4.1 | |
1.39E-5 | 1.80 | 5.61E-5 | 1.96 | 7.9 | |
5.22E-6 | 1.41 | 1.92E-5 | 1.55 | 15.9 | |
2.68E-6 | 0.96 | 9.40E-6 | 1.03 | 31.5 | |
2.15E-6 | 0.32 | 8.56E-6 | 0.14 | 66.6 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.62E-5 | – | 2.13E-4 | – | 62.7 | |
1.23E-5 | 1.91 | 5.46E-5 | 1.96 | 63.2 | |
4.25E-6 | 1.53 | 1.60E-5 | 1.77 | 63.5 | |
2.57E-6 | 0.73 | 9.15E-6 | 0.81 | 67.6 | |
2.23E-6 | 0.20 | 8.88E-6 | 0.04 | 68.1 |
Since the AMIB algorithm achieves second order accuracy for both spatial and temporal discretization, we test the computing efficiency by refining the spatial and temporal steps simultaneously. See the Table 8 with stopping time
AMIB-GMRES | |||||||
CPU time(s) | time ratio | ANMG | |||||
Error | Order | Error | Order | ||||
1.53E-4 | – | 5.08E-4 | – | 0.25 | 31.3 | ||
3.63E-5 | 2.08 | 1.39E-4 | 1.87 | 2.22 | 8.9 | 35.2 | |
8.63E-6 | 2.07 | 3.52E-5 | 1.98 | 26.7 | 12.0 | 48.1 | |
2.16E-6 | 2.00 | 8.88E-6 | 1.99 | 342.9 | 12.8 | 57.3 | |
AMIB-LU | |||||||
CPU time(s) | time ratio | ||||||
Error | Order | Error | Order | ||||
1.53E-4 | – | 5.08E-4 | – | 0.15 | 15.2 | ||
3.63E-5 | 2.08 | 1.39E-4 | 1.87 | 1.15 | 7.7 | 15.2 | |
8.63E-6 | 2.07 | 3.52E-5 | 1.98 | 10.1 | 8.8 | 15.2 | |
2.14E-6 | 2.01 | 8.79E-6 | 2.00 | 100.8 | 10 | 15.2 | |
MIB | |||||||
CPU time(s) | time ratio | ||||||
Error | Order | Error | Order | ||||
1.47E-4 | – | 5.05E-4 | – | 0.43 | |||
3.62E-5 | 2.08 | 1.42E-4 | 1.87 | 5.94 | 13.8 | ||
8.53E-6 | 2.07 | 3.56E-5 | 1.98 | 113.4 | 19.1 | ||
NA | NA | NA | NA | NA | NA |
It can be noticed that the numerical results for MIB in the last row of Table 8 are not available due to failure of convergence from the biconjugate gradient solver [31]. The non-convergence is not caused by stability issue on the algorithm, as a different iterative solver, such as GMRES, can produce convergent iterative solution in our numerical test. This demonstrated that the performance of the AMIB methods does not heavily depend on the iterative solvers, while the MIB method does.
Example 4. We are interested in the stability performance of the two methods on complicated interface shape. In this example, we focus on the case of interface shape governed by parametric function
r=0.5+0.1sin(5θ), | (43) |
embedded in the domain
The exact solution to this problem is
u(x,y)={cos(t)e−x−y,inΩ−,cos(t)ex+y,inΩ+, | (44) |
with the diffusion coefficients
β={1,inΩ−,100,inΩ+. |
The spatial convergence is validated by refining the mesh with the stopping time
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.08E-3 | – | 6.81E-3 | – | 1.67 | |
6.26E-4 | 2.70 | 1.12E-3 | 2.60 | 12.5 | |
2.26E-4 | 1.47 | 3.92E-4 | 1.51 | 89 | |
9.01E-5 | 1.33 | 1.54E-4 | 1.35 | 524 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.08E-3 | – | 6.81E-3 | – | 0.48 | |
6.26E-4 | 2.70 | 1.12E-3 | 2.60 | 2.50 | |
2.25E-4 | 1.47 | 3.91E-4 | 1.52 | 12.4 | |
8.83E-5 | 1.33 | 1.51E-4 | 1.37 | 57 |
We next examine the temporal order of the two AMIB methods by setting
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
3.28E-3 | – | 5.60E-3 | – | 5.2 | |
8.22E-4 | 2.00 | 1.38E-3 | 2.02 | 10.1 | |
2.23E-4 | 1.88 | 3.65E-4 | 1.92 | 20.2 | |
7.45E-5 | 1.58 | 1.16E-4 | 1.65 | 40.1 | |
3.75E-5 | 0.99 | 6.05E-5 | 0.94 | 76.6 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
3.28E-3 | – | 5.60E-3 | – | 75.8 | |
8.21E-4 | 2.00 | 1.38E-3 | 2.02 | 75.3 | |
2.23E-4 | 1.88 | 3.64E-4 | 1.92 | 77.7 | |
7.41E-5 | 1.59 | 1.15E-4 | 1.66 | 80.1 | |
3.75E-5 | 0.98 | 6.10E-5 | 0.94 | 82.7 |
To numerically analyze the stability of the two AMIB schemes, we examine different time stepping. We choose
Example 5. We next study a problem with multiple subdomains. Consider a 2D parabolic equation
ut=(βux)x+(βuy)y+q(x,y) |
defined in a square domain
ΓL:(x+π6π9)2+(y+π7π12)2=1ΓR:(x−π6π12)2+(y−π7π9)2=1 |
Three pieces of solutions are defined in each subdomain
u(x,y)={cos(t)cos(kx)sin(ky)insideΓL,cos(t)cos(kx)sin(ky)insideΓR,cos(t)ex+yotherwise, |
where parameter
β={100,insideΓL,10,insideΓR,1,otherwise, |
and the parameter
The second order spatial and temporal accuracy of solutions have been examined through above examples. Besides, we want to further investigate the convergence rate of the gradient recovery. Second order central difference is adopted to approximate the gradients with fictitious values replacing obtained numerical real function values when the stencil cuts through the interface. Table 11 shows that second order convergence is achieved for both solutions and gradients from the three methods in solving the multi-domain problem. With the confirmed second orders of the three methods, we pay attention to the comparison of the methods on overall efficiency for solving multi-domain problem. Table 11 demonstrates the efficiency test, where it can be observed that AMIB-LU outperform the other methods for solving such problems. The last column of Table 11 shows that AMIB-LU has smaller time ratio than AMIB-GMRES or AMIB with mesh refinement. In particular, the computing time by MIB is almost 19 times larger than that of AMIB-LU in dealing the multi-domain problem on the
|
AMIB-GMRES | |||||
Solution | ||||||
CPU time(s) | time ratio | |||||
Error | Order | Error | Order | |||
3.00E-2 | – | 7.43E-2 | – | 0.37 | ||
8.96E-3 | 1.74 | 2.24E-2 | 1.73 | 3.96 | 10.7 | |
1.57E-3 | 2.51 | 4.02E-3 | 2.48 | 44.46 | 11.2 | |
3.23E-4 | 2.28 | 8.28E-4 | 2.28 | 562 | 12.6 | |
Gradient | ||||||
Error | Order | Error | Order | |||
9.38E-2 | – | 0.37 | – | |||
2.83E-2 | 1.732 | 0.12 | 1.62 | |||
5.07E-3 | 2.48 | 2.15E-2 | 2.48 | |||
1.21E-3 | 2.07 | 5.29E-3 | 2.02 | |||
AMIB-LU | ||||||
Solution | ||||||
CPU time(s) | time ratio | |||||
Error | Order | Error | Order | |||
3.00E-2 | – | 7.43E-2 | – | 0.15 | ||
8.95E-3 | 1.75 | 2.23E-2 | 1.74 | 1.22 | 8.1 | |
1.58E-3 | 2.50 | 4.05E-3 | 2.46 | 11.7 | 9.6 | |
3.71E-4 | 2.09 | 9.54E-4 | 2.09 | 127 | 10.9 | |
Gradient | ||||||
Error | Order | Error | Order | |||
9.38E-2 | – | 0.37 | – | |||
2.82E-2 | 1.73 | 0.12 | 1.62 | |||
5.11E-3 | 2.46 | 2.17E-2 | 2.47 | |||
1.21E-3 | 2.08 | 5.29E-3 | 2.04 | |||
MIB | ||||||
Solution | ||||||
CPU time(s) | time ratio | |||||
Error | Order | Error | Order | |||
3.61E-2 | – | 9.21E-2 | – | 0.44 | ||
1.10E-2 | 1.74 | 2.87E-2 | 1.68 | 7.38 | 16.8 | |
1.41E-3 | 2.46 | 3.90E-3 | 2.88 | 143 | 19.4 | |
2.17E-4 | 2.09 | 9.89E-4 | 1.98 | 2372 | 16.6 | |
Gradient | ||||||
Error | Order | Error | Order | |||
0.12 | – | 1.93 | – | |||
3.53E-2 | 1.76 | 0.44 | 2.13 | |||
4.51E-3 | 2.97 | 0.13 | 1.76 | |||
9.73E-4 | 2.21 | 2.42E-2 | 2.43 |
We note that there exist more challenging multi-material interface problems, in which two or more material interfaces join together or cross each other. A second order accurate MIB method has been developed in [38] for elliptic equations with intersecting interfaces. Based on such a MIB method, an augmented MIB method could be developed for intersecting interface problems. This is an interesting direction to explore in the future.
Example 6. We investigate a physical problem modeled by the heat equation without analytical solutions
ut=∇⋅(β∇u) |
subject to the homogeneous interface condition
[u]=0 | (45) |
[βu]=0 | (46) |
on the interface
β={100,inΩ−,1,inΩ+. |
The Dirichlet boundary condition equal to zero is imposed at the boundary of given domain. Besides, the initial condition is defined as
u(x,y)={e−(x2+y2)/σ2inΩ−,0,inΩ+, | (47) |
with parameter
The spatial convergence is validated by refining the mesh under time increment
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.09E-5 | – | 6.66E-5 | – | 0.65 | |
2.24E-5 | 0.87 | 3.63E-5 | 0.88 | 4.02 | |
5.04E-6 | 2.15 | 8.19E-6 | 2.15 | 22.3 | |
9.47E-7 | 2.41 | 1.56E-6 | 2.39 | 151 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.09E-5 | – | 6.66E-5 | – | 0.25 | |
2.23E-5 | 0.88 | 3.62E-5 | 0.88 | 1.36 | |
5.06E-6 | 2.14 | 8.22E-6 | 2.24 | 7.06 | |
9.97E-7 | 2.34 | 1.63E-6 | 2.33 | 34.9 |
The temporal convergence is validated in a similar fashion by refining time increment for a fixed stopping time
The figure 8 shows solution evolution over time for this physical model. As discussed before, the temperature drops quickly in a short time. This can be observed in Fig. 7 when time is changing from 0 to 0.1. When time equals to 1, the temperature has dropped to a magnitude of
In this work, a new finite difference method has been proposed to solve parabolic interface problem with second order accuracy achieved in both time and space. The efficiency is fulfilled with multigrid method built in the Schur complement process in the framework of an augmented system. A simple multigrid solver is designed to solve the linear system due to the special structure of coefficient matrix as part of the augmented system. Two approaches based on the multigrid solver are proposed in the time-step process, with one incorporated in GMRES iteration for each time evolution, and the other one used in the coefficient matrix formation of LU decomposition solver in the first time step. The latter approach with LU decomposition can be more efficient especially when a lot of time-stepping evolutions are needed for solving the given parabolic interface problem. Both AMIB methods are significantly faster than the standard MIB method. Moreover, being free of stability constraint, the present implicit method could be asymptotically faster than explicit schemes.
The immersed interface method (IIM) has been applied to variable coefficient elliptic equations [4,21], and these studies demonstrated how to adopt numerical components, such as jump-corrected differences, augmented system, and multigrid solver, for variable coefficient problems. Thus, based on these studies, it is possible to generalize the present mulitgrid AMIB method for variable coefficient interface problems. This will be explored in the future.
This research is supported in part by the National Science Foundation (NSF) of USA under grant DMS-1812930.
[1] |
New geometric immersed interface multigrid solvers. SIAM J. Sci. Comput. (2004) 25: 1516-1533. ![]() |
[2] |
The immersed interface/multigrid methods for interface problems. SIAM J. Sci. Comput. (2002) 24: 463-479. ![]() |
[3] | Convergence of an immersed finite element method for semilinear parabolic interface problems. Appl. Math. Sci. (Ruse) (2011) 5: 135-147. |
[4] |
A decomposed immersed interface method for variable coefficient elliptic equations with non-smooth and discontinuous solutions. J. Comput. Phys. (2004) 197: 364-386. ![]() |
[5] |
F. Bouchon and G. H. Peichl, An immersed interface technique for the numerical solution of the heat equation on a moving domain, Numerical Mathematics and Advanced Applications 2009, Springer Berlin Heidelberg, (2010), 181–189. doi: 10.1007/978-3-642-11795-4_18
![]() |
[6] |
The immersed interface technique for parabolic problems with mixed boundary conditions. SIAM J. Numer. Anal. (2010) 48: 2247-2266. ![]() |
[7] |
Robust multigrid methods for nonsmooth coefficient elliptic linear systems. J. Comput. Appl. Math. (2000) 123: 323-352. ![]() |
[8] |
Finite element methods and their convergence for elliptic and parabolic interface problems. Numer. Math. (1998) 79: 175-202. ![]() |
[9] |
Finite-difference ghost-point multigrid methods on Cartesian grids for elliptic problems in arbitrary domains. J. Comput. Phys. (2013) 241: 464-501. ![]() |
[10] |
Second order finite-difference ghost-point multigrid methods for elliptic problems with discontinuous coefficients on an arbitrary interface. J. Comput. Phys. (2018) 361: 299-330. ![]() |
[11] | On the numerical integration of ∂2u∂x2+∂2u∂y2=∂u∂t by implicit methods. J. Soc. Indust. Appl. Math. (1955) 3: 42-65. |
[12] | Numerical solution of two-dimensional heat-flow problems. AIChEJ. (1955) 1: 505-512. |
[13] |
Immersed finite element method for interface problems with algebraic multigrid solver. Commun. Comput. Phys. (2014) 15: 1045-1067. ![]() |
[14] |
An augmented matched interface and boundary (MIB) method for solving elliptic interface problem. J. Comput. Appl. Math. (2019) 361: 426-443. ![]() |
[15] |
H. Feng and S. Zhao, FFT-based high order central difference schemes for the three-dimensional Poisson's equation with various types of boundary conditions, J. Comput. Phys., 410 (2020), 109391, 24 pp. doi: 10.1016/j.jcp.2020.109391
![]() |
[16] |
H. Feng and S. Zhao, A fourth order finite difference method for solving elliptic interface problems with the FFT acceleration, J. Comput. Phys., 419 (2020), 109677, 25 pp. doi: 10.1016/j.jcp.2020.109677
![]() |
[17] |
A fourth order accurate discretization for the Laplace and heat equations on arbitrary domains, with applications to the Stefan problem. J. Comput. Phys. (2005) 202: 577-601. ![]() |
[18] |
The immersed interface method for a nonlinear chemical diffusion equation with local sites of reactions. Numer. Algorithms (2004) 36: 285-307. ![]() |
[19] |
The immersed interface method for two-dimensional heat-diffusion equations with singular own sources. Appl. Numer. Math. (2007) 57: 486-497. ![]() |
[20] |
On multiscale ADI methods for parabolic PDEs with a discontinuous coefficient. Multiscale Model. Simul. (2018) 16: 1623-1647. ![]() |
[21] |
Accurate solution and gradient computation for elliptic interface problems with variable coefficients. SIAM J. Numer. Anal. (2017) 55: 570-597. ![]() |
[22] |
ADI methods for heat quations with discontinuous along an arbitrary interface. Proc. Sympos. Appl. Math. (1993) 48: 311-315. ![]() |
[23] |
Alternating direction ghost-fluid methods for solving the heat equation with interfaces. Comput. Math. Appl. (2020) 80: 714-732. ![]() |
[24] |
A matched Peaceman–Achford ADI method for solving parabolic interface problems. Appl. Math. Comput. (2017) 299: 28-44. ![]() |
[25] |
Partially penalized immersed finite element methods for parabolic interface problems. Numer. Methods Partial Differential Equations (2015) 31: 1925-1947. ![]() |
[26] |
IIM-based ADI finite difference scheme for nonlinear convection–diffusion equations with interfaces. Appl. Math. Model. (2013) 37: 1196-1207. ![]() |
[27] |
A dimension by dimension splitting immersed interface method for heat conduction equation with interfaces. J. Comput. Appl. Math. (2014) 261: 221-231. ![]() |
[28] |
S. F. McCormick, Multigrid Methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1987. doi: 10.1137/1.9781611971057
![]() |
[29] |
The numerical solution of parabolic and elliptic equations. J. Soc. Indust. Appl. Math. (1955) 3: 28-41. ![]() |
[30] |
Efficient symmetric discretization for the Poisson, heat and Stefan-type problems with Robin boundary conditions. J. Comput. Phys. (2010) 229: 875-889. ![]() |
[31] | W. H. Press and S. A. Teukolsky, Numerical Recipes in FORTRAN, the Art of Scientific Computing, 2nd edition, Cambridge University Press, New York, 1992. |
[32] |
Optimal error estimates for linear parabolic problems with discontinuous coefficients. SIAM J. Numer. Anal. (2005) 43: 733-749. ![]() |
[33] |
Finite element methods for semilinear elliptic and parabolic interface problems. Appl. Numer. Math. (2009) 59: 1870-1883. ![]() |
[34] |
Symmetric interior penalty Galerkin approaches for two-dimensional parabolic interface problems with low regularity solutions. J. Comput. Appl. Math. (2018) 330: 356-379. ![]() |
[35] |
A boundary condition-capturing multigrid approach to irregular boundary problems. SIAM J. Sci. Comput. (2004) 25: 1982-2003. ![]() |
[36] |
A spatially second order alternating direction implicit (ADI) method for three dimensional parabolic interface problems. Comput. Math. Appl. (2018) 75: 2173-2192. ![]() |
[37] |
The explicit-jump immersed interface method: Finite difference methods for PDEs with piecewise smooth solutions. SIAM J. Numer. Anal. (2000) 37: 827-862. ![]() |
[38] |
MIB method for elliptic equations with multi-material interfaces. J. Comput. Phys. (2011) 230: 4588-4615. ![]() |
[39] | Discontinuous Galerkin immersed finite element methods for parabolic interface problems. J. Comput. Appl. Math. (2016) 299: 127-139. |
[40] |
A matched alternating direction implicit (ADI) method for solving the heat equation with interfaces. J. Sci. Comput. (2015) 63: 118-137. ![]() |
[41] |
High-order FDTD methods via derivative matching for Maxwell's equations with material interfaces. J. Comput. Phys. (2004) 200: 60-103. ![]() |
[42] |
High order matched interface and boundary method for elliptic equations with discontinuous coefficients and singular source. J. Comput. Phys. (2006) 213: 1-30. ![]() |
1. | Chuan Li, Guangqing Long, Yiquan Li, Shan Zhao, Alternating Direction Implicit (ADI) Methods for Solving Two-Dimensional Parabolic Interface Problems with Variable Coefficients, 2021, 9, 2079-3197, 79, 10.3390/computation9070079 | |
2. | Chuan Li, Yiming Ren, Guangqing Long, Eric Boerman, Shan Zhao, A Fast Sine Transform Accelerated High-Order Finite Difference Method for Parabolic Problems over Irregular Domains, 2023, 95, 0885-7474, 10.1007/s10915-023-02177-7 | |
3. | Fan Chen, Ming Cui, Chenguang Zhou, A type of efficient multigrid method for semilinear parabolic interface problems, 2025, 143, 10075704, 108632, 10.1016/j.cnsns.2025.108632 |
Algorithm 1 Two-grid correction scheme |
1: The initial guess for |
2: Relax Eq.(34) |
3: Compute the residual on fine grid, |
4: for |
5: Restrict the residual to coarse grid |
6: Exactly solve for the solution |
7: Interpolate the correction to fine grid |
8: Apply the correction to get a better approximation |
9: Relax the Eq.(34) |
10: Compute the residual on fine grid, |
11: end for |
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
2.08E-4 | – | 8.82E-4 | – | 0.94 | |
3.21E-5 | 2.70 | 1.69E-4 | 2.38 | 5.48 | |
7.52E-6 | 2.09 | 3.13E-5 | 2.43 | 26.6 | |
1.94E-6 | 1.95 | 9.07E-6 | 1.79 | 175 | |
5.66E-7 | 1.95 | 2.97E-6 | 1.79 | 1143 | |
AMIB-LU | |||||
Error | Order | Error | Order | ||
2.08E-4 | – | 8.82E-4 | – | 0.30 | |
3.19E-5 | 2.70 | 1.68E-4 | 2.38 | 1.49 | |
7.52E-6 | 2.09 | 3.13E-5 | 2.43 | 6.50 | |
1.94E-6 | 1.95 | 9.08E-6 | 1.79 | 29.8 | |
5.71E-7 | 1.95 | 2.99E-6 | 1.79 | 200 | |
MIB | |||||
Error | Order | Error | Order | ||
2.07E-4 | – | 8.75E-4 | – | 0.62 | |
3.19E-5 | 2.70 | 1.68E-4 | 2.38 | 4.76 | |
7.50E-6 | 2.08 | 3.13E-5 | 2.42 | 35.4 | |
1.94E-6 | 1.94 | 9.09E-6 | 1.79 | 336 | |
5.66E-7 | 1.95 | 2.97E-6 | 1.79 | 2935 |
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
1.32E-4 | – | 5.46E-4 | – | 2.76 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 5.28 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.13 | 9.73 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.99 | 19.36 | |
1.56E-6 | 1.99 | 4.88E-6 | 2.02 | 37.88 | |
6.26E-7 | 1.32 | 3.21E-6 | 0.60 | 76.9 | |
5.60E-7 | 0.16 | 2.99E-6 | 0.10 | 148.4 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
1.32E-4 | – | 5.46E-4 | – | 58 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 59.4 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.13 | 61.5 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.99 | 63.2 | |
1.56E-6 | 1.99 | 4.88E-6 | 1.94 | 64.7 | |
6.34E-7 | 1.30 | 3.24E-6 | 0.59 | 66.8 | |
5.76E-7 | 0.13 | 3.04E-6 | 0.09 | 74 | |
MIB | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
1.32E-4 | – | 5.46E-4 | – | 21.97 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 42.34 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.14 | 81.72 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.98 | 153.34 | |
1.56E-6 | 1.99 | 4.88E-6 | 1.94 | 287.03 | |
6.27E-7 | 1.31 | 3.22E-6 | 0.60 | 533 | |
5.69E-7 | 0.14 | 3.02E-6 | 0.09 | 863 |
AMIB-GMRES- |
AMIB-GMRES | |||||||||
CPU | CPU | |||||||||
Error | Order | Error | Order | Error | Order | Error | Order | |||
3.22E-2 | – | 7.55E-2 | – | 3.04 | 1.39E-3 | – | 3.43E-3 | – | 2.81 | |
5.56E-3 | 2.53 | 1.57E-2 | 2.27 | 5.9 | 3.14E-4 | 2.15 | 7.77E-4 | 2.14 | 5.69 | |
9.47E-4 | 2.55 | 2.94E-3 | 2.42 | 12.5 | 7.59E-5 | 2.05 | 1.88E-4 | 2.05 | 11.2 | |
1.67E-4 | 2.50 | 4.35E-4 | 2.76 | 23 | 1.89E-5 | 2.01 | 4.68E-5 | 2.01 | 22 | |
3.82E-5 | 2.13 | 8.32E-5 | 2.39 | 45 | 5.00E-6 | 1.92 | 1.21E-5 | 1.95 | 45.4 | |
9.68E-6 | 1.99 | 2.13E-5 | 1.98 | 87 | 1.44E-6 | 1.80 | 3.30E-6 | 1.87 | 96.3 | |
2.579E-6 | 1.91 | 6.05E-6 | 1.82 | 168 | 6.60E-7 | 1.13 | 2.84E-6 | 0.22 | 170 | |
9.03E-7 | 1.53 | 3.25E-6 | 0.91 | 334 | ||||||
AMIB-LU- |
AMIB-LU | |||||||||
CPU | CPU | |||||||||
Error | Order | Error | Order | Error | Order | Error | Order | |||
3.22E-2 | – | 7.55E-2 | – | 65 | 1.40E-3 | – | 3.44E-3 | – | 57 | |
5.56E-3 | 2.53 | 1.57E-2 | 2.27 | 69 | 3.15E-4 | 2.15 | 7.79E-4 | 2.15 | 59.6 | |
9.47E-4 | 2.55 | 2.94E-3 | 2.42 | 62 | 7.64E-5 | 2.04 | 1.89E-4 | 2.04 | 58.9 | |
1.67E-4 | 2.50 | 4.35E-4 | 2.76 | 62 | 1.90E-5 | 2.01 | 4.70E-5 | 2.01 | 57.7 | |
3.82E-5 | 2.13 | 8.32E-5 | 2.39 | 60.6 | 4.82E-6 | 1.98 | 1.17E-5 | 2.01 | 60.7 | |
9.65E-6 | 1.99 | 2.11E-5 | 1.98 | 66 | 1.34E-6 | 1.85 | 3.05E-6 | 1.94 | 64.6 | |
2.57E-6 | 1.91 | 5.98E-6 | 1.82 | 75.1 | 6.16E-7 | 1.12 | 2.70E-6 | 0.18 | 75.9 | |
8.88E-7 | 1.53 | 3.18E-6 | 0.91 | 91 | ||||||
5.69E-7 | 0.64 | 2.76E-6 | 0.20 | 129 |
AMIB-GMRES- |
AMIB-GMRES | |||||||||
CPU | CPU | |||||||||
Error | Order | Error | Order | Error | Order | Error | Order | |||
1.15E-4 | – | 5.16E-4 | – | 1.11 | 2.25E-4 | – | 5.16E-4 | – | 1.19 | |
1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 7.39 | 1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 7.86 | |
1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 42 | 1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 43 | |
2.06E-6 | 2.82 | 1.54E-5 | 2.61 | 264 | 2.04E-6 | 2.82 | 1.04E-5 | 2.61 | 258 | |
5.18E-7 | 2.01 | 2.65E-6 | 1.99 | 1457 | 5.05E-7 | 2.01 | 2.62E-6 | 1.99 | 1463 | |
AMIB-LU- |
AMIB-LU | |||||||||
CPU | CPU | |||||||||
Error | Order | Error | Order | Error | Order | Error | Order | |||
1.15E-4 | – | 5.16E-4 | – | 0.34 | 2.25E-4 | – | 5.16E-4 | – | 0.7 | |
1.10E-4 | 0.06 | 3.42E-4 | 0.59 | 1.66 | 1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 1.78 | |
1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 8.04 | 1.44E-5 | 2.93 | 6.40E-5 | 2.43 | 8.76 | |
2.06E-6 | 2.81 | 1.05E-5 | 2.61 | 39.4 | 2.05E-6 | 2.91 | 1.04E-5 | 1.79 | 41.6 | |
5.28E-7 | 1.96 | 2.68E-6 | 1.97 | 231 | 5.15E-7 | 1.99 | 2.65E-6 | 1.99 | 227 |
AMIB-GMRES | ||||||
Small |
Large |
|||||
CPU time(s) | CPU time(s) | |||||
1.63E-5 | 5.11E-5 | 71.4 | 1.86E-5 | 6.70E-5 | 92.6 | |
1.63E-5 | 5.10E-5 | 65.4 | 1.86E-5 | 6.69E-5 | 92.8 | |
1.61E-5 | 5.04E-5 | 52.4 | 1.84E-5 | 6.60E-5 | 69.3 | |
1.47E-5 | 4.43E-5 | 31.4 | 1.65E-5 | 5.74E-5 | 33.8 | |
9.48E-6 | 4.71E-5 | 36.2 | 7.01E-6 | 3.44E-5 | 36.2 | |
6.03E-5 | 1.56E-4 | 58.3 | 6.20E-5 | 1.45E-4 | 66.4 | |
4.66E-4 | 9.00E-4 | 67.8 | 6.38E-4 | 1.19E-3 | 81.6 | |
5.26E-4 | 8.52E-4 | 71.2 | 5.62E-3 | 1.02E-2 | 89.5 | |
AMIB-LU | ||||||
Small |
Large |
|||||
CPU time(s) | CPU time(s) | |||||
1.63E-5 | 5.11E-5 | 10.9 | 1.86E-5 | 6.72E-5 | 10.9 | |
1.63E-5 | 5.10E-5 | 10.58 | 1.86E-5 | 6.71E-5 | 10.46 | |
1.61E-5 | 5.04E-5 | 8.8 | 1.84E-5 | 6.61E-5 | 9.1 | |
1.47E-5 | 4.43E-5 | 6.8 | 1.66E-5 | 5.75E-5 | 6.9 | |
9.48E-6 | 4.71E-5 | 7.0 | 7.03E-6 | 3.43E-5 | 6.9 | |
6.03E-5 | 1.56E-4 | 9.2 | 6.20E-5 | 1.45E-4 | 8.5 | |
4.66E-4 | 9.00E-4 | 8.6 | 6.38E-4 | 1.19E-3 | 8.6 | |
5.29E-4 | 8.56E-4 | 9.0 | 5.63E-3 | 1.02E-2 | 8.7 |
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
6.70E-4 | – | 2.17E-3 | – | 1.67 | |
1.52E-4 | 2.14 | 5.05E-4 | 2.10 | 9.82 | |
3.63E-5 | 2.07 | 1.39E-4 | 1.86 | 53 | |
8.62E-6 | 2.07 | 3.52E-5 | 1.98 | 399 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
6.70E-4 | – | 2.17E-3 | – | 0.42 | |
1.52E-4 | 2.14 | 5.05E-4 | 2.10 | 1.94 | |
3.63E-5 | 2.07 | 1.39E-4 | 1.86 | 8.54 | |
8.62E-6 | 2.07 | 3.52E-5 | 1.98 | 45.5 |
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.83E-5 | – | 2.18E-4 | – | 4.1 | |
1.39E-5 | 1.80 | 5.61E-5 | 1.96 | 7.9 | |
5.22E-6 | 1.41 | 1.92E-5 | 1.55 | 15.9 | |
2.68E-6 | 0.96 | 9.40E-6 | 1.03 | 31.5 | |
2.15E-6 | 0.32 | 8.56E-6 | 0.14 | 66.6 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.62E-5 | – | 2.13E-4 | – | 62.7 | |
1.23E-5 | 1.91 | 5.46E-5 | 1.96 | 63.2 | |
4.25E-6 | 1.53 | 1.60E-5 | 1.77 | 63.5 | |
2.57E-6 | 0.73 | 9.15E-6 | 0.81 | 67.6 | |
2.23E-6 | 0.20 | 8.88E-6 | 0.04 | 68.1 |
AMIB-GMRES | |||||||
CPU time(s) | time ratio | ANMG | |||||
Error | Order | Error | Order | ||||
1.53E-4 | – | 5.08E-4 | – | 0.25 | 31.3 | ||
3.63E-5 | 2.08 | 1.39E-4 | 1.87 | 2.22 | 8.9 | 35.2 | |
8.63E-6 | 2.07 | 3.52E-5 | 1.98 | 26.7 | 12.0 | 48.1 | |
2.16E-6 | 2.00 | 8.88E-6 | 1.99 | 342.9 | 12.8 | 57.3 | |
AMIB-LU | |||||||
CPU time(s) | time ratio | ||||||
Error | Order | Error | Order | ||||
1.53E-4 | – | 5.08E-4 | – | 0.15 | 15.2 | ||
3.63E-5 | 2.08 | 1.39E-4 | 1.87 | 1.15 | 7.7 | 15.2 | |
8.63E-6 | 2.07 | 3.52E-5 | 1.98 | 10.1 | 8.8 | 15.2 | |
2.14E-6 | 2.01 | 8.79E-6 | 2.00 | 100.8 | 10 | 15.2 | |
MIB | |||||||
CPU time(s) | time ratio | ||||||
Error | Order | Error | Order | ||||
1.47E-4 | – | 5.05E-4 | – | 0.43 | |||
3.62E-5 | 2.08 | 1.42E-4 | 1.87 | 5.94 | 13.8 | ||
8.53E-6 | 2.07 | 3.56E-5 | 1.98 | 113.4 | 19.1 | ||
NA | NA | NA | NA | NA | NA |
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.08E-3 | – | 6.81E-3 | – | 1.67 | |
6.26E-4 | 2.70 | 1.12E-3 | 2.60 | 12.5 | |
2.26E-4 | 1.47 | 3.92E-4 | 1.51 | 89 | |
9.01E-5 | 1.33 | 1.54E-4 | 1.35 | 524 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.08E-3 | – | 6.81E-3 | – | 0.48 | |
6.26E-4 | 2.70 | 1.12E-3 | 2.60 | 2.50 | |
2.25E-4 | 1.47 | 3.91E-4 | 1.52 | 12.4 | |
8.83E-5 | 1.33 | 1.51E-4 | 1.37 | 57 |
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
3.28E-3 | – | 5.60E-3 | – | 5.2 | |
8.22E-4 | 2.00 | 1.38E-3 | 2.02 | 10.1 | |
2.23E-4 | 1.88 | 3.65E-4 | 1.92 | 20.2 | |
7.45E-5 | 1.58 | 1.16E-4 | 1.65 | 40.1 | |
3.75E-5 | 0.99 | 6.05E-5 | 0.94 | 76.6 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
3.28E-3 | – | 5.60E-3 | – | 75.8 | |
8.21E-4 | 2.00 | 1.38E-3 | 2.02 | 75.3 | |
2.23E-4 | 1.88 | 3.64E-4 | 1.92 | 77.7 | |
7.41E-5 | 1.59 | 1.15E-4 | 1.66 | 80.1 | |
3.75E-5 | 0.98 | 6.10E-5 | 0.94 | 82.7 |
|
AMIB-GMRES | |||||
Solution | ||||||
CPU time(s) | time ratio | |||||
Error | Order | Error | Order | |||
3.00E-2 | – | 7.43E-2 | – | 0.37 | ||
8.96E-3 | 1.74 | 2.24E-2 | 1.73 | 3.96 | 10.7 | |
1.57E-3 | 2.51 | 4.02E-3 | 2.48 | 44.46 | 11.2 | |
3.23E-4 | 2.28 | 8.28E-4 | 2.28 | 562 | 12.6 | |
Gradient | ||||||
Error | Order | Error | Order | |||
9.38E-2 | – | 0.37 | – | |||
2.83E-2 | 1.732 | 0.12 | 1.62 | |||
5.07E-3 | 2.48 | 2.15E-2 | 2.48 | |||
1.21E-3 | 2.07 | 5.29E-3 | 2.02 | |||
AMIB-LU | ||||||
Solution | ||||||
CPU time(s) | time ratio | |||||
Error | Order | Error | Order | |||
3.00E-2 | – | 7.43E-2 | – | 0.15 | ||
8.95E-3 | 1.75 | 2.23E-2 | 1.74 | 1.22 | 8.1 | |
1.58E-3 | 2.50 | 4.05E-3 | 2.46 | 11.7 | 9.6 | |
3.71E-4 | 2.09 | 9.54E-4 | 2.09 | 127 | 10.9 | |
Gradient | ||||||
Error | Order | Error | Order | |||
9.38E-2 | – | 0.37 | – | |||
2.82E-2 | 1.73 | 0.12 | 1.62 | |||
5.11E-3 | 2.46 | 2.17E-2 | 2.47 | |||
1.21E-3 | 2.08 | 5.29E-3 | 2.04 | |||
MIB | ||||||
Solution | ||||||
CPU time(s) | time ratio | |||||
Error | Order | Error | Order | |||
3.61E-2 | – | 9.21E-2 | – | 0.44 | ||
1.10E-2 | 1.74 | 2.87E-2 | 1.68 | 7.38 | 16.8 | |
1.41E-3 | 2.46 | 3.90E-3 | 2.88 | 143 | 19.4 | |
2.17E-4 | 2.09 | 9.89E-4 | 1.98 | 2372 | 16.6 | |
Gradient | ||||||
Error | Order | Error | Order | |||
0.12 | – | 1.93 | – | |||
3.53E-2 | 1.76 | 0.44 | 2.13 | |||
4.51E-3 | 2.97 | 0.13 | 1.76 | |||
9.73E-4 | 2.21 | 2.42E-2 | 2.43 |
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.09E-5 | – | 6.66E-5 | – | 0.65 | |
2.24E-5 | 0.87 | 3.63E-5 | 0.88 | 4.02 | |
5.04E-6 | 2.15 | 8.19E-6 | 2.15 | 22.3 | |
9.47E-7 | 2.41 | 1.56E-6 | 2.39 | 151 | |
AMIB-LU | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
4.09E-5 | – | 6.66E-5 | – | 0.25 | |
2.23E-5 | 0.88 | 3.62E-5 | 0.88 | 1.36 | |
5.06E-6 | 2.14 | 8.22E-6 | 2.24 | 7.06 | |
9.97E-7 | 2.34 | 1.63E-6 | 2.33 | 34.9 |
Algorithm 1 Two-grid correction scheme |
1: The initial guess for |
2: Relax Eq.(34) |
3: Compute the residual on fine grid, |
4: for |
5: Restrict the residual to coarse grid |
6: Exactly solve for the solution |
7: Interpolate the correction to fine grid |
8: Apply the correction to get a better approximation |
9: Relax the Eq.(34) |
10: Compute the residual on fine grid, |
11: end for |
AMIB-GMRES | |||||
CPU time(s) | |||||
Error | Order | Error | Order | ||
2.08E-4 | – | 8.82E-4 | – | 0.94 | |
3.21E-5 | 2.70 | 1.69E-4 | 2.38 | 5.48 | |
7.52E-6 | 2.09 | 3.13E-5 | 2.43 | 26.6 | |
1.94E-6 | 1.95 | 9.07E-6 | 1.79 | 175 | |
5.66E-7 | 1.95 | 2.97E-6 | 1.79 | 1143 | |
AMIB-LU | |||||
Error | Order | Error | Order | ||
2.08E-4 | – | 8.82E-4 | – | 0.30 | |
3.19E-5 | 2.70 | 1.68E-4 | 2.38 | 1.49 | |
7.52E-6 | 2.09 | 3.13E-5 | 2.43 | 6.50 | |
1.94E-6 | 1.95 | 9.08E-6 | 1.79 | 29.8 | |
5.71E-7 | 1.95 | 2.99E-6 | 1.79 | 200 | |
MIB | |||||
2.07E-4 | – | 8.75E-4 | – | 0.62 | |
3.19E-5 | 2.70 | 1.68E-4 | 2.38 | 4.76 | |
7.50E-6 | 2.08 | 3.13E-5 | 2.42 | 35.4 | |
1.94E-6 | 1.94 | 9.09E-6 | 1.79 | 336 | |
5.66E-7 | 1.95 | 2.97E-6 | 1.79 | 2935 |
AMIB-GMRES | |||||
CPU time(s) | |||||
1.32E-4 | – | 5.46E-4 | – | 2.76 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 5.28 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.13 | 9.73 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.99 | 19.36 | |
1.56E-6 | 1.99 | 4.88E-6 | 2.02 | 37.88 | |
6.26E-7 | 1.32 | 3.21E-6 | 0.60 | 76.9 | |
5.60E-7 | 0.16 | 2.99E-6 | 0.10 | 148.4 | |
AMIB-LU | |||||
CPU time(s) | |||||
1.32E-4 | – | 5.46E-4 | – | 58 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 59.4 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.13 | 61.5 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.99 | 63.2 | |
1.56E-6 | 1.99 | 4.88E-6 | 1.94 | 64.7 | |
6.34E-7 | 1.30 | 3.24E-6 | 0.59 | 66.8 | |
5.76E-7 | 0.13 | 3.04E-6 | 0.09 | 74 | |
MIB | |||||
CPU time(s) | |||||
1.32E-4 | – | 5.46E-4 | – | 21.97 | |
8.98E-5 | 0.56 | 3.25E-4 | 0.75 | 42.34 | |
2.48E-5 | 1.86 | 7.42E-5 | 2.14 | 81.72 | |
6.21E-6 | 2.00 | 1.87E-5 | 1.98 | 153.34 | |
1.56E-6 | 1.99 | 4.88E-6 | 1.94 | 287.03 | |
6.27E-7 | 1.31 | 3.22E-6 | 0.60 | 533 | |
5.69E-7 | 0.14 | 3.02E-6 | 0.09 | 863 |
AMIB-GMRES- |
AMIB-GMRES | |||||||||
CPU | CPU | |||||||||
3.22E-2 | – | 7.55E-2 | – | 3.04 | 1.39E-3 | – | 3.43E-3 | – | 2.81 | |
5.56E-3 | 2.53 | 1.57E-2 | 2.27 | 5.9 | 3.14E-4 | 2.15 | 7.77E-4 | 2.14 | 5.69 | |
9.47E-4 | 2.55 | 2.94E-3 | 2.42 | 12.5 | 7.59E-5 | 2.05 | 1.88E-4 | 2.05 | 11.2 | |
1.67E-4 | 2.50 | 4.35E-4 | 2.76 | 23 | 1.89E-5 | 2.01 | 4.68E-5 | 2.01 | 22 | |
3.82E-5 | 2.13 | 8.32E-5 | 2.39 | 45 | 5.00E-6 | 1.92 | 1.21E-5 | 1.95 | 45.4 | |
9.68E-6 | 1.99 | 2.13E-5 | 1.98 | 87 | 1.44E-6 | 1.80 | 3.30E-6 | 1.87 | 96.3 | |
2.579E-6 | 1.91 | 6.05E-6 | 1.82 | 168 | 6.60E-7 | 1.13 | 2.84E-6 | 0.22 | 170 | |
9.03E-7 | 1.53 | 3.25E-6 | 0.91 | 334 | ||||||
AMIB-LU- |
AMIB-LU | |||||||||
CPU | CPU | |||||||||
3.22E-2 | – | 7.55E-2 | – | 65 | 1.40E-3 | – | 3.44E-3 | – | 57 | |
5.56E-3 | 2.53 | 1.57E-2 | 2.27 | 69 | 3.15E-4 | 2.15 | 7.79E-4 | 2.15 | 59.6 | |
9.47E-4 | 2.55 | 2.94E-3 | 2.42 | 62 | 7.64E-5 | 2.04 | 1.89E-4 | 2.04 | 58.9 | |
1.67E-4 | 2.50 | 4.35E-4 | 2.76 | 62 | 1.90E-5 | 2.01 | 4.70E-5 | 2.01 | 57.7 | |
3.82E-5 | 2.13 | 8.32E-5 | 2.39 | 60.6 | 4.82E-6 | 1.98 | 1.17E-5 | 2.01 | 60.7 | |
9.65E-6 | 1.99 | 2.11E-5 | 1.98 | 66 | 1.34E-6 | 1.85 | 3.05E-6 | 1.94 | 64.6 | |
2.57E-6 | 1.91 | 5.98E-6 | 1.82 | 75.1 | 6.16E-7 | 1.12 | 2.70E-6 | 0.18 | 75.9 | |
8.88E-7 | 1.53 | 3.18E-6 | 0.91 | 91 | ||||||
5.69E-7 | 0.64 | 2.76E-6 | 0.20 | 129 |
AMIB-GMRES- |
AMIB-GMRES | |||||||||
CPU | CPU | |||||||||
1.15E-4 | – | 5.16E-4 | – | 1.11 | 2.25E-4 | – | 5.16E-4 | – | 1.19 | |
1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 7.39 | 1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 7.86 | |
1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 42 | 1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 43 | |
2.06E-6 | 2.82 | 1.54E-5 | 2.61 | 264 | 2.04E-6 | 2.82 | 1.04E-5 | 2.61 | 258 | |
5.18E-7 | 2.01 | 2.65E-6 | 1.99 | 1457 | 5.05E-7 | 2.01 | 2.62E-6 | 1.99 | 1463 | |
AMIB-LU- |
AMIB-LU | |||||||||
CPU | CPU | |||||||||
1.15E-4 | – | 5.16E-4 | – | 0.34 | 2.25E-4 | – | 5.16E-4 | – | 0.7 | |
1.10E-4 | 0.06 | 3.42E-4 | 0.59 | 1.66 | 1.10E-4 | 1.03 | 3.42E-4 | 0.59 | 1.78 | |
1.44E-5 | 2.93 | 6.40E-5 | 2.42 | 8.04 | 1.44E-5 | 2.93 | 6.40E-5 | 2.43 | 8.76 | |
2.06E-6 | 2.81 | 1.05E-5 | 2.61 | 39.4 | 2.05E-6 | 2.91 | 1.04E-5 | 1.79 | 41.6 | |
5.28E-7 | 1.96 | 2.68E-6 | 1.97 | 231 | 5.15E-7 | 1.99 | 2.65E-6 | 1.99 | 227 |
AMIB-GMRES | ||||||
Small |
Large |
|||||
CPU time(s) | CPU time(s) | |||||
1.63E-5 | 5.11E-5 | 71.4 | 1.86E-5 | 6.70E-5 | 92.6 | |
1.63E-5 | 5.10E-5 | 65.4 | 1.86E-5 | 6.69E-5 | 92.8 | |
1.61E-5 | 5.04E-5 | 52.4 | 1.84E-5 | 6.60E-5 | 69.3 | |
1.47E-5 | 4.43E-5 | 31.4 | 1.65E-5 | 5.74E-5 | 33.8 | |
9.48E-6 | 4.71E-5 | 36.2 | 7.01E-6 | 3.44E-5 | 36.2 | |
6.03E-5 | 1.56E-4 | 58.3 | 6.20E-5 | 1.45E-4 | 66.4 | |
4.66E-4 | 9.00E-4 | 67.8 | 6.38E-4 | 1.19E-3 | 81.6 | |
5.26E-4 | 8.52E-4 | 71.2 | 5.62E-3 | 1.02E-2 | 89.5 | |
AMIB-LU | ||||||
Small |
Large |
|||||
CPU time(s) | CPU time(s) | |||||
1.63E-5 | 5.11E-5 | 10.9 | 1.86E-5 | 6.72E-5 | 10.9 | |
1.63E-5 | 5.10E-5 | 10.58 | 1.86E-5 | 6.71E-5 | 10.46 | |
1.61E-5 | 5.04E-5 | 8.8 | 1.84E-5 | 6.61E-5 | 9.1 | |
1.47E-5 | 4.43E-5 | 6.8 | 1.66E-5 | 5.75E-5 | 6.9 | |
9.48E-6 | 4.71E-5 | 7.0 | 7.03E-6 | 3.43E-5 | 6.9 | |
6.03E-5 | 1.56E-4 | 9.2 | 6.20E-5 | 1.45E-4 | 8.5 | |
4.66E-4 | 9.00E-4 | 8.6 | 6.38E-4 | 1.19E-3 | 8.6 | |
5.29E-4 | 8.56E-4 | 9.0 | 5.63E-3 | 1.02E-2 | 8.7 |
AMIB-GMRES | |||||
CPU time(s) | |||||
6.70E-4 | – | 2.17E-3 | – | 1.67 | |
1.52E-4 | 2.14 | 5.05E-4 | 2.10 | 9.82 | |
3.63E-5 | 2.07 | 1.39E-4 | 1.86 | 53 | |
8.62E-6 | 2.07 | 3.52E-5 | 1.98 | 399 | |
AMIB-LU | |||||
CPU time(s) | |||||
6.70E-4 | – | 2.17E-3 | – | 0.42 | |
1.52E-4 | 2.14 | 5.05E-4 | 2.10 | 1.94 | |
3.63E-5 | 2.07 | 1.39E-4 | 1.86 | 8.54 | |
8.62E-6 | 2.07 | 3.52E-5 | 1.98 | 45.5 |
AMIB-GMRES | |||||
CPU time(s) | |||||
4.83E-5 | – | 2.18E-4 | – | 4.1 | |
1.39E-5 | 1.80 | 5.61E-5 | 1.96 | 7.9 | |
5.22E-6 | 1.41 | 1.92E-5 | 1.55 | 15.9 | |
2.68E-6 | 0.96 | 9.40E-6 | 1.03 | 31.5 | |
2.15E-6 | 0.32 | 8.56E-6 | 0.14 | 66.6 | |
AMIB-LU | |||||
CPU time(s) | |||||
4.62E-5 | – | 2.13E-4 | – | 62.7 | |
1.23E-5 | 1.91 | 5.46E-5 | 1.96 | 63.2 | |
4.25E-6 | 1.53 | 1.60E-5 | 1.77 | 63.5 | |
2.57E-6 | 0.73 | 9.15E-6 | 0.81 | 67.6 | |
2.23E-6 | 0.20 | 8.88E-6 | 0.04 | 68.1 |
AMIB-GMRES | |||||||
CPU time(s) | time ratio | ANMG | |||||
1.53E-4 | – | 5.08E-4 | – | 0.25 | 31.3 | ||
3.63E-5 | 2.08 | 1.39E-4 | 1.87 | 2.22 | 8.9 | 35.2 | |
8.63E-6 | 2.07 | 3.52E-5 | 1.98 | 26.7 | 12.0 | 48.1 | |
2.16E-6 | 2.00 | 8.88E-6 | 1.99 | 342.9 | 12.8 | 57.3 | |
AMIB-LU | |||||||
CPU time(s) | time ratio | ||||||
1.53E-4 | – | 5.08E-4 | – | 0.15 | 15.2 | ||
3.63E-5 | 2.08 | 1.39E-4 | 1.87 | 1.15 | 7.7 | 15.2 | |
8.63E-6 | 2.07 | 3.52E-5 | 1.98 | 10.1 | 8.8 | 15.2 | |
2.14E-6 | 2.01 | 8.79E-6 | 2.00 | 100.8 | 10 | 15.2 | |
MIB | |||||||
CPU time(s) | time ratio | ||||||
1.47E-4 | – | 5.05E-4 | – | 0.43 | |||
3.62E-5 | 2.08 | 1.42E-4 | 1.87 | 5.94 | 13.8 | ||
8.53E-6 | 2.07 | 3.56E-5 | 1.98 | 113.4 | 19.1 | ||
NA | NA | NA | NA | NA | NA |
AMIB-GMRES | |||||
CPU time(s) | |||||
4.08E-3 | – | 6.81E-3 | – | 1.67 | |
6.26E-4 | 2.70 | 1.12E-3 | 2.60 | 12.5 | |
2.26E-4 | 1.47 | 3.92E-4 | 1.51 | 89 | |
9.01E-5 | 1.33 | 1.54E-4 | 1.35 | 524 | |
AMIB-LU | |||||
CPU time(s) | |||||
4.08E-3 | – | 6.81E-3 | – | 0.48 | |
6.26E-4 | 2.70 | 1.12E-3 | 2.60 | 2.50 | |
2.25E-4 | 1.47 | 3.91E-4 | 1.52 | 12.4 | |
8.83E-5 | 1.33 | 1.51E-4 | 1.37 | 57 |
AMIB-GMRES | |||||
CPU time(s) | |||||
3.28E-3 | – | 5.60E-3 | – | 5.2 | |
8.22E-4 | 2.00 | 1.38E-3 | 2.02 | 10.1 | |
2.23E-4 | 1.88 | 3.65E-4 | 1.92 | 20.2 | |
7.45E-5 | 1.58 | 1.16E-4 | 1.65 | 40.1 | |
3.75E-5 | 0.99 | 6.05E-5 | 0.94 | 76.6 | |
AMIB-LU | |||||
CPU time(s) | |||||
3.28E-3 | – | 5.60E-3 | – | 75.8 | |
8.21E-4 | 2.00 | 1.38E-3 | 2.02 | 75.3 | |
2.23E-4 | 1.88 | 3.64E-4 | 1.92 | 77.7 | |
7.41E-5 | 1.59 | 1.15E-4 | 1.66 | 80.1 | |
3.75E-5 | 0.98 | 6.10E-5 | 0.94 | 82.7 |
|
AMIB-GMRES | |||||
CPU time(s) | time ratio | |||||
3.00E-2 | – | 7.43E-2 | – | 0.37 | ||
8.96E-3 | 1.74 | 2.24E-2 | 1.73 | 3.96 | 10.7 | |
1.57E-3 | 2.51 | 4.02E-3 | 2.48 | 44.46 | 11.2 | |
3.23E-4 | 2.28 | 8.28E-4 | 2.28 | 562 | 12.6 | |
9.38E-2 | – | 0.37 | – | |||
2.83E-2 | 1.732 | 0.12 | 1.62 | |||
5.07E-3 | 2.48 | 2.15E-2 | 2.48 | |||
1.21E-3 | 2.07 | 5.29E-3 | 2.02 | |||
AMIB-LU | ||||||
CPU time(s) | time ratio | |||||
3.00E-2 | – | 7.43E-2 | – | 0.15 | ||
8.95E-3 | 1.75 | 2.23E-2 | 1.74 | 1.22 | 8.1 | |
1.58E-3 | 2.50 | 4.05E-3 | 2.46 | 11.7 | 9.6 | |
3.71E-4 | 2.09 | 9.54E-4 | 2.09 | 127 | 10.9 | |
9.38E-2 | – | 0.37 | – | |||
2.82E-2 | 1.73 | 0.12 | 1.62 | |||
5.11E-3 | 2.46 | 2.17E-2 | 2.47 | |||
1.21E-3 | 2.08 | 5.29E-3 | 2.04 | |||
MIB | ||||||
CPU time(s) | time ratio | |||||
3.61E-2 | – | 9.21E-2 | – | 0.44 | ||
1.10E-2 | 1.74 | 2.87E-2 | 1.68 | 7.38 | 16.8 | |
1.41E-3 | 2.46 | 3.90E-3 | 2.88 | 143 | 19.4 | |
2.17E-4 | 2.09 | 9.89E-4 | 1.98 | 2372 | 16.6 | |
0.12 | – | 1.93 | – | |||
3.53E-2 | 1.76 | 0.44 | 2.13 | |||
4.51E-3 | 2.97 | 0.13 | 1.76 | |||
9.73E-4 | 2.21 | 2.42E-2 | 2.43 |
AMIB-GMRES | |||||
CPU time(s) | |||||
4.09E-5 | – | 6.66E-5 | – | 0.65 | |
2.24E-5 | 0.87 | 3.63E-5 | 0.88 | 4.02 | |
5.04E-6 | 2.15 | 8.19E-6 | 2.15 | 22.3 | |
9.47E-7 | 2.41 | 1.56E-6 | 2.39 | 151 | |
AMIB-LU | |||||
CPU time(s) | |||||
4.09E-5 | – | 6.66E-5 | – | 0.25 | |
2.23E-5 | 0.88 | 3.62E-5 | 0.88 | 1.36 | |
5.06E-6 | 2.14 | 8.22E-6 | 2.24 | 7.06 | |
9.97E-7 | 2.34 | 1.63E-6 | 2.33 | 34.9 |