Parallel Multilevel Methods for Unstructured Grid ProblemsDescriptionOur goal in this project is to provide parallel tools that facilitate the use of multilevel techniques. These tools leverage recent advances applying multigrid to applications with complex grids and complicated physics, as well as recent developments at Sandia using h-adaptivity technology. To provide the new capabilities, we will have to address the following issues regarding multilevel techniques
Candidate methodologies for constructing hierarchies of grids are, but not limited to, (1) user-provided non-nested coarse grids, (2) nested coarse grids through h-adaptivity, (3) automatic node-based or edge-based coarsenings, (4) automatic coarsening using agglomeration techniques, and (5) algebraic multilevel techniques. We propose to examine each of these alternatives, with particular emphasis on agglomeration techniques and h-adaptive meshes. Agglomeration techniques are appealing for application codes that have no convenient mechanism for creating grid hierarchies. This is because agglomeration schemes automatically generate coarse grids (using primarily information from the fine grid) without user intervention, allow for the straight-forward construction of inter-grid transfer operators, and offer an elegant way of dealing with complex geometries, especially in three dimensions. However, for applications which generate grid hierarchies (e.g. h-adaptive schemes), the creation of auxiliary meshes is not necessary. Instead, it is natural to use the h-adaptive grids in a multilevel preconditioner (though the advantages mentioned above may still warrant experimenting with agglomeration in h-adaptive schemes). In this case, the most critical task in handling a given mesh hierarchy corresponds to extracting grid information in a way that does not depend on the specific data-structures used within the finite element application (so that the same scheme can be used by several different applications). The design of a generic multilevel finite element framework is especially challenging. Important elements in this framework are (1) an interface between the multilevel module and the main solver (e.g. Krylov methods), (2) an interface between the multilevel and finite element modules, and (3) an interface between the solver and finite element modules (using interface expertise from ISIS++). Each interface in turn involves many design issues to support the different ways of constructing the grid hierarchy, the choices of inter-grid transfer operators, the handling of boundary conditions, the construction of discrete coarse grid operators, etc. In addition to a grid hierarchy, a multilevel method requires inter-grid transfer operators, coarse grid discretization operators, and relaxation/smoothing operators (for multigrid). The choice of each of these operators can have an immense effects on convergence rates. For example, poor interpolations introduce excessive error in the solution process and thus may slow down or even stall convergence. Dealing with different boundary conditions within the grid transfer process may also introduce additional complications that can slow convergence. Simple schemes like injection and piecewise linear interpolation are popular candidates. However, others methods such as matrix-dependent or energy-minimized interpolants can potentially improve robustness and efficiency and thus need to be explored in the context of our four application codes. Additional local conservation considerations must be made for application codes based on finite volume formulations. Similar to the grid transfers, coarse grid discretization choices exist with different consequences in terms of programming, work per iteration, and overall convergence rates. The most popular candidates here fall into two categories: schemes that rediscretize the continuous operator using the application program on the coarse grid and methods which project automatically the fine grid discretization (e.g. Galerkin coarse grid operators) onto the coarse grid without requiring further consultation with the application. The former often impose additional user requirements and thus may not always be feasible. The latter is more general, but it may incur substantially larger computational cost. Once again a detailed assessment of these alternatives is warranted in the context of our primary applications. For the multilevel methods to be useful, the various multilevel components have to be efficiently implemented on massively parallel supercomputers, such as the TFLOP and the 'C-plant' machines. In particular, methods for parallel agglomeration and parallel construction of inter-grid transfer operators are to be devised, parallel strategies for coarse problem formation and solution are to be determined, and a parallel interface to the Krylov solver and finite element module is to be implemented. SoftwareWe currently have a working version (called ML 2.0) which has been tested successfully (coupled as preconditioner to Aztec) on several applications. Team MembersThe following people participate in the ML project in various capacities:
ContactFor more information, please contact Ray Tuminaro (tuminaro@ca.sandia.gov). |
CSMR Department Projects
at Sandia National Labs in
California.
Copyright © 2001, Sandia Corp. All rights reserved.
Comments: tgkolda@sandia.gov.
Acknowledgments and Disclaimer.