The CGBI domain decomposition method and application to Navier-Stokes flow problems


The Conjugate Gradient Boundary Iteration (CGBI) method is a parallelization method for symmetric elliptic boundary value problems based on non-overlapping domain decomposition. It was introduced by W. Borchers.

Obviously it is easy to find the solution of the global partial differential equation in parallel as soon as the corresponding boundary conditions on the subdomain interfaces are known. CGBI searchs these boundary conditions of Neumann type by a conjugate gradient (CG) iteration. The name CGBI comes from the fact that the global conjugate gradient method and its preconditioner are running on the interfaces ('boundaries') of the subdomains. During each CG iteration step local elliptic problems on the subdomains are to be solved. The CGBI method enables us to couple different local solvers to get a high performance. For example, on rectangular subdomains spectral methods provide highly efficient solvers. On non-rectangular subdomains, finite element methods (FE, FEM) should be used because of their flexibility.

CGBI is similar to the domain decomposition method FETI (finite element tearing and interconnecting method) developed in the early 1990s for problems from structural mechanics. Both methods were developed independendly from each other. The main advantage of CGBI is the fact that CGBI uses preconditioners acting only on the interfaces.

Many publications on domain decomposition methods focus on the discrete ('matrix') level for the description of the algorithm and for the investigation of preconditioners. In our work we concentrate on the investigation of the underlying continuous problems. This approach directly leads to our preconditioner as a discretization of the square root of the negative of the Laplacian operator acting on the subdomain interfaces. Theoretical considerations show that this preconditioner yields a condition number (i.e. a CGBI convergence rate) independent of the number of mesh points and the number of subdomains. In contrast to other approaches, our interface preconditioner does not require the solution of any time-consuming subdomain-based problems. Here we have to mention the work of Dryja and Bjørstad/Widlund who proposed interface-based preconditioners in the context of the Schur method with local FE/FD solvers in the 1980s.

Some efficient discretizations of our preconditioning operator are developed and tested for the case of rectangular subdomains. These discretizations are easy to find on an equidistant mesh. However, our Chebyshev spectral subdomain solvers are working on a Chebyshev-Gauss-Lobatto mesh. It turns out that on a Gauss-Lobatto boundary mesh, it is much more difficult to find a discretization of the preconditioner. The mathematical method to construct a Gauss-Lobatto mesh based preconditioner is the interpolation theory of weighted Sobolev spaces. The resulting preconditioner yields for Dirichlet problems a CGBI convergence rate independent of the number of grid points, the number of the subdomains, the size of the channel and the Helmholtz resolvent equation parameter, both on equidistant and on Gauss-Lobatto boundary meshes. Only for the combination of a Gauss-Lobatto boundary mesh and Neumann boundary conditions on the physical channel walls, a very moderate dependence of the condition number on the discretization parameter may occur.

A limitation of our preconditioner is, that the condition number increases for bad aspect ratios (approx. <0.1) of the subdomains. For this case and Neumann boundary conditions a different preconditioner is proposed.

The discretization of our preconditioners is based on the spectral decomposition (fast Fourier transform, FFT) of a function given on the interfaces. As an alternative, discretizations based on sparse matrices are constructed.

As an application for CGBI, a parallel solver for the incompressible instationary Navier-Stokes equations is constructed in this paper. Using a pressure correction scheme (the pressure correction methods, also called fractional step methods) our solver splits each Navier-Stokes timestep into one hyperbolic and two elliptic problems. The hyperbolic problem is solved with the method of characteristics. The elliptic problems are solved with CGBI.

The project was supported by the Deutsche Forschungsgemeinschaft (DFG). The programming was done in collaboration with the University of Paderborn (Kerstin Wielage, Dr. Nicole Roß, Prof. Rautmann) and the University of Nice, France (Dr. Pasquetti and co-workers).


Application. Navier-Stokes flow around a cylinder at Re=100, computed in parallel with the CGBI-domain-decomposition technique, FE-method on left subdomain, spectral method on the other subdomains. Upper part: norm of velocity field, lower part: vorticity field. Computed in 2001.

Convergence history of CGBI method for 4 subdomains, spectral Chebychev solver/mesh on each subdomain, 16x16 to 256x256 nodes per subdomain. Using the developed preconditioner, about 8 CGBI iteration steps are required, independently of the discretization parameter (bold lines). Without the preconditioner, 25-200 iteration steps are required, depending on the discretization parameter (dashed lines).

See my doctoral thesis and my publications 1997-2005 in my publication list.