A Boundary Condition Capturing Multigrid Approach to Irregular Boundary Problems

SIAM Journal on Scientific Computing, vol. 25, no. 6, pp. 1982--2003, 2004.
(Co-authors: Xu-dong Liu)

A geometric multigrid method is proposed to solve linear systems arising from irregular boundary problems involving multiple interfaces in 2D and 3D. In this method, we adopt a matrix-free approach; i.e. we do not form the fine grid matrix explicitly and we never form nor store the coarse grid matrices, as many other robust multigrid methods do. The main idea is to construct an accurate interpolation which captures the correct boundary conditions at the interfaces via a level set function. Numerical results show our multigrid method is more efficient than the black box and algebraic multigrid methods in terms of complexity and memory consumption for multiple interface problems.

Boundary Capturing Interpolation

Model equation:
- ∇ a(x) u ∇ u = f

The domain Ω consists of m interfaces Γi. The model problem is to solve the PDE subject to boundary conditions on ∂Ω and coupling conditions on Γi. We say the model problem if of Dirichlet type if a Dirichlet boundary condition is used on Γi, and of interface type if jump conditions are used instead. The idea is to construct an interpolation which captures the boundary conditions on the interfaces which can be easily and precisely located by a level set function.


Linear interpolation for the Dirichlet-type problem in 1D. The solid line shows the coarse grid solution uH. The two dashed lines show the linear interpolations applied at different points.


The solid line denotes the coarse grid solution uH, and the dotted line the linear interpolant. (Left) O(h) approximation error results at the kink if linear interpolation is used. (Right) Jump-preserving interpolation near interface with jump conditions.

Numerical Results

Example 1: 2D irregular boundary problem of Dirichlet type


Circle interfaces (left) and their corresponding solutions (right) to the irregular boundary problem of Dirichlet type in 2D.

PCG = conjugate gradient method preconditioned by ILU(0)
GMG = our geometric multigrid method
AMG = algebraic multigrid method
BMG = blackbox multigrid method

h Circle array PCG GMG AMG BMG
1/16 1x1 4 7 7 11
1/32 1x1 8 8 8 15
2x2 7 7 8 14
1/64 1x1 15 10 10 18
2x2 13 8 8 19
4x4 8 7 8 15
1/128 1x1 31 11 10 20
2x2 24 10 10 20
4x4 14 8 8 20
6x6 10 8 8 18
Comparison by work units of our multigrid method with other methods (1 work unit = 1 GMG iteration).

The convergence rate of PCG deteriorates with decreasing mesh size; the number of work units doubles as h is reduced by half. BMG requires more work units to converge. GMG and AMG show similar efficiency. However, GMG does not require to store the coarse grid matrices (matrix-free method) whereas AMG has to store all the coarse grid matrices.

Example 2: 3D irregular boundary problem of Dirichlet type


Sphere interfaces (left) and their corresponding solutions (right, a contour plot) to the irregular boundary problem of Dirichlet type in 3D.

h Sphere array PCG GMG AMG
1/8 1x1x1 4 7 9
1/16 1x1x1 8 7 14
2x2x2 6 9 16
1/32 1x1x1 16 8 23
2x2x2 11 8 17
4x4x4 8 9 18
1/64 1x1x1 >100 10 40
2x2x2 93 8 23
4x4x4 30 8 15
Comparison by work units of our multigrid method with other methods.

For 3D problems, our GMG is much more efficient than PCG and AMG. The convergence results for BMG are not known since 3D BMG code is not available.

Sphere array GMG AMG
1 2 3 4 1 2 3 4 5 6
1x1x1 226 28 3 0.4 226 303 118 85 70 34
2x2x2 223 27 3 0.4 223 295 126 89 75 39
3x3x3 219 26 3 0.4 219 286 133 10285 47
4x4x4 213 25 3 0.4 213 284 134 12187 46
Number of nonzero entries (thousands) in the coarse grid matrices on different coarse grids (1 to 4 for GMG and 1 to 6 for AMG).

Example 3: 2D irregular boundary problem of interface type


Solution to the irregular boundary problem of interface type in 2D.

h Circle array PCG GMG AMG BMG
1 103 106 1 103 106 1 103 106 1 103 106
1/16 1x1 6 7 9 5 6 7 7 11 9 4 6 6
2x2 6 10 13 5 9 9 7 9 9 4 7 7
1/32 1x1 10 12 14 5 6 7 7 9 8 5 6 6
2x2 10 16 21 5 6 6 7 14 14 5 7 7
1/64 1x1 16 22 27 5 6 7 7 9 9 5 7 6
2x2 16 30 41 5 7 7 7 13 13 5 9 9
1/128 1x1 33 44 52 5 6 8 7 9 10 5 10 7
2x2 33 56 80 5 6 8 7 12 12 5 11 12
Comparison by work units of our multigrid method with other methods. The jump size at the interfaces = 1, 103, 106.

BMG shows is more efficient than for Dirichlet-type problems. Its convergence is comparable to GMG and insensitive to jump size but deteriorates when the mesh size decreases or when the number of interfaces increases. AMG requires more work than the other two largely due to denser coase grid matrices. The convergence of PCG is slowed down by the mesh size, the size of the jump and the number of interfaces.

Example 4: 3D irregular boundary problem of interface type


Solution to the irregular boundary problem of interface type in 3D.

h Sphere array PCG GMG AMG
102 104 106 102 104 106 102 104 106
1/8 1x1x1 5 6 7 8 8 8 12 16 17
2x2x2 7 9 12 6 6 6 12 15 15
1/16 1x1x1 9 10 12 9 10 10 18 21 21
2x2x2 12 17 22 8 8 8 40 32 32
1/32 1x1x1 16 20 24 10 11 11 20 24 >100
2x2x2 24 32 42 9 9 9 77 42 42
1/64 1x1x1 30 38 42 8 10 11 19 29 26
2x2x2 46 67 84 10 12 12 31 45 >100
4x4x4 58 89 98 9 11 11 >100 >100 >100
Comparison by work units of our multigrid method with other methods. The jump size at the interfaces = 102, 104, 106.

GMG is relatively insensitive to the mesh size and the size of the jump. The convergence of PCG and AMG, on the other hand, deteriorates with the number of interfaces and decreasing mesh size.