Research

Ph.D. Theses

Multilevel Preconditioning Methods for the Parallel Iterative Solution of Large, Sparse Systems of Equations

By Wesley D. Turner
Advisor: Joseph E. Flaherty
December 15, 2000

We present an efficient solution strategy for general problems arising from the finite ele ment method applied to partial differential equations over a spatial domain. The thesis is divided into two main efforts. The first effort centers around the development of an efficient algorithm for the serial solution of linear algebraic equations. In proceeding with the serial algorithm, we define preconditionings and introduce the Algebraic Multilevel Iteration (AMLI) preconditioner of Axelsson and Vassilevski that will be a focus of this research. After adding some adaptations to allow efficient operation within our environment, we show preliminary results demonstrating the applicability of this method to complex problems involving h- and p-refinement, and non-positive definite systems. We extend the discussion of the preconditioner by considering a spatial coarsening algorithm leveraging the TRELLIS octree structure to impose regular coarsening on the irregular mesh comprising the discrete problem domain. The octree structure is defined and the operations required for the serial generation of the octree coarsened system are explained. This coarsener gives superior convergence behavior as the problem size grows via h-refinement.

The second effort is concerned with an efficient and maintainable parallel implementation of the algorithm. We present an abstraction for the matrix and vector objects sufficient for the implementation of Krylov space techniques, and apply that abstraction to the generation of a transparently parallel generic library. The generic library makes significant use of C++ templates and can be easily extended to multiple data storage formats. It allows a user to write one version of code sufficient for multiple serial and parallel applications. The parallel portion of the library encapsulates the data distribution and communication requirements in an easily maintained class for portability among distributed and parallel computing models.

Finally, we combine the parallel and serial efforts into a single implementation. We present extensions to the generic parallel library and to the octree coarsener sufficient to implement and maintain the octree coarsener in parallel. Modifications to the underlying serial components necessary for efficient parallel implementation are discussed and the behavior of the solver is measured.

Return to main PhD Theses page