Ahmed Sameh and Vivek Sarin
This paper presents an efficient iterative scheme for the generalized Stokes problem, which arises frequently in the simulation of time-dependent Navier-Stokes equations for incompressible fluid flow. The general form of the linear system is
where is an symmetric positive definite matrix, in which M is the mass matrix, T is the discrete Laplace operator, and are positive constants proportional to the inverses of the time-step and the Reynolds number Re respectively, and B is the discrete gradient operator of size (k;SPMlt;n). Even though the matrix A is symmetric and positive definite, the system is indefinite due to the incompressibility constraint ( ). This causes difficulties both for iterative methods and commonly used preconditioners. Moreover, depending on the ratio , A behaves like the mass matrix M at one extreme and the Laplace operator T at the other, causing problems for the common iterative methods employed to solve this system.
The generalized Stokes problem is one of the most time-consuming steps in the large scale simulation of incompressible fluid flows. Iterative methods, which are indispensable for solving this problem in realistic situations, rely heavily on effective preconditioners that can be efficiently implemented on multiprocessors. Therefore, the issues of efficient iterative algorithms and robust, effective and parallelizable preconditioners for the generalized Stokes problem must be resolved satisfactorily.
Previous efforts to solve the linear system in Eq. 1 can be broadly classified as follows:
Each iteration requires the solution of the linear system Ax=b. If an iterative method is used to solve Ax=b, then we obtain a two-level solver with inner and outer iterations. The inner system may be solved in many ways including multigrid, spectral methods and preconditioned CG algorithm. Convergence may be considerably improved by replacing A with or by accelerating the linear system by the CG method. Single-level methods which approximate the generalized Stokes problem by a nearly incompressible problem have also been developed. However, effective preconditioners for this approach often rely on expensive linear system solves using an inner iterative method. The reader is referred to [4, 1, 3, 7, 10, 9] for a variety of Uzawa-type methods.
where P is the orthogonal projection onto the null space of . In each iteration, one computes the action of the projector on a vector u, which requires solving the system , where is analogous to a Laplace operator on the domain. For a large three dimensional problem, computing the projection of u onto is almost as difficult as solving the system Au=b, and may require the use of an inner iterative method.
Both Uzawa-type and projection methods are expensive two-level nested iterative methods with rapid convergence assured only for certain extreme values of . Further, these schemes suffer from the lack of good preconditioners, which have been elusive due to the complicated coefficient matrices arising in these methods.
In this paper, we propose a multilevel scheme for the solution of elliptic problems that has the desirable properties of effective preconditioning and efficient implementation on multiprocessors. We also extend this multilevel scheme to the generalized Stokes problem and present numerical experiments comparing the multilevel scheme with the Uzawa and projection methods.
Multilevel Scheme for the Generalized Stokes Problem A multilevel approach is used to compute a basis for , where B is the discrete gradient operator. This null-space-basis, is expressed as the product of a sequence of sparse matrices, s.t. it requires only O(n) operations to perform a matrix-vector product with . In fact, we determine matrices P, D and Z such that
where P is a nonsingular matrix, D is a diagonal matrix and Zis a orthogonal matrix. Further, where comprises of the last n-k columns of P.
Eq. 1 may be rewritten as
where . The algorithm for computing the solution of the generalized Stokes problem is as follows:
To solve the generalized Stokes problem efficiently, it is imperative that the matrix , in which , is well-conditioned for a wide range of the parameters and . When is large, A may be approximated by , and when is small, A approaches the Laplace operator . It can be shown that for large values of , standard preprocessing techniques like scaling the matrix A with a diagonal matrix obtained by lumping the mass matrix M yields a well-conditioned system. In cases where is small, we expect to be well-conditioned due to the ``inverse'' nature of the matrices A and .
Numerical experiments for the solution of the generalized Stokes problem for a lid-driven cavity problem were performed on an IBM RS6000 with 66.5 MHz clock and 256 MB memory. We consider a two-dimensional unit square domain with on the boundary except the top edge where , and p=0 at the bottom-left corner. The domain is uniformly discretized with the Marker-and-Cell (MAC) scheme. Figs. 1 and 2 presents the number of iterations and time required to solve the linear system in Eq. 5. From these results, it may be concluded that in the worst case, the condition number of the system matrix is , which indicates effective preconditioning of the system matrix.
The number of iterations and time required by the outer iterative method in the Uzawa method are presented in Figs. 3 and 4. It may be noted that in general, each iteration of these methods is relatively expensive due to system solves.
Figure 1: Multilevel scheme for the solution of the generalized Stokes problem on a uniform mesh for .
Figure 2: Multilevel scheme for the solution of the generalized Stokes problem on a uniform mesh for .
Figure 3: Uzawa methods for the solution of the generalized Stokes problem on a uniform mesh for .
Figure 4: Uzawa methods for the solution of the generalized Stokes problem on a uniform mesh for .
These results clearly indicate that the multilevel scheme is a robust and effective preconditioning strategy for the solution of the linear system of the generalized Stokes problem for a wide choice of . This makes the multilevel scheme an attractive approach especially since convergence is relatively independent of , and therefore doesn't constrain the choice of the time-step . Furthermore, it is a single-level scheme with O(n) computation per iteration, unlike the two-level Uzawa-type and projection methods which require expensive linear system solves in each iteration. It must also be pointed out that the effort required in generating the basis can be amortized over a number of system solves since B is invariant over numerous time steps for the nonlinear Navier-Stokes equations. Current work includes numerical experiments with systems obtained using the finite elements method on unstructured grids for two and three-dimensional domains. We expect to present comparative results of numerical experiments for these problems.
Tue Sep 22 08:12:33 EST 1998
| AEM Home | Institute of Technology |
| Academics |
Research | People |
Information | Contact
| Major Projects | by Specialty | Other Programs |
Solid-Liquid Flows Home | Publications
Last updated October 16, 2000