M. Behr, Rice MEMS - Iterative Solution Techniques

Iterative Solution Strategies

[CFD Picture]

Figure 9: Flow around a submarine: Partitioning of the hull.

[CFD Picture]

Figure 10: Tidal flow in Tokyo bay: Partitioning of the mesh.

A common factor in all implicit finite element simulations is the need to solve large linear systems of equations. These systems can be either symmetric or non-symmetric, and are typically sparse. The conditioning of the system improves with the use of stabilized methods and good quality meshes, but can be nevertheless quite poor. Due to the size, a direct solution methods are for the most part out of the question, and iterative strategies must be employed. The solver used to obtain the results presented in the preceding sections is based on the General Minimum RESidual (GMRES) technique for non-symmetric systems. The performance of this solver is determined by the implementation of two major tasks: the matrix-vector product evaluation, and the preconditioning. In the matrix-vector product stage, the global system matrix is never assembled, and instead is stored as a set of either element- or subdomain-level matrices. An alternative Matrix-Free (MF) implementation avoids storing the matrices altogether, and approximates the matrix-vector product with several residual evaluations. The MF approach provides significant reduction in memory requirements, at a slightly higher computation cost. The preconditioning techniques used range from a simple diagonal preconditioning, adequate for most problems discussed here, to complex preconditioners based on domain-decomposition or multi-grid. The two latter approaches can also be combined for an even more accelerated convergence. Many of the GMRES phases involve communication between element- or subdomain-level storage and global unknown vectors. Crucial to the scalability of the algorithm is maximization of data locality and minimization of the amount of data that has to be exchanged between processors. This is accomplished by partitioning of the mesh, and aligning both the element-level storage and the global storage with the resulting subdomains. The decomposition of the mesh employs either a parallel Recursive Spectral Bisection algorithm available on CM-5, or serial graph partitioning METIS package. Figures 9-10 show the effect of partitioning on two of the meshes used in the previously discussed projects.