| Author | Wesley D. Turner |
|---|---|
| Title | Multilevel preconditioning methods for parallel iterative solution of large, sparse, systems of equations |
| Year | 2000 |
| School | RPI |
| Abstract | We present an efficient solution strategy for general problems arising from the finite element method applied to partial differential equations over a spatial doamin. The thesis is devided 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 preconditionnings 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- refinment, and non-positive definite systems. We extend the discussion of the preconditionner by considering an alternative to the algebraic coarsenong. This spacial coarsener leverages 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. We demonstrate that this coarsener gives superior convergence behavior as the problem size grows via h- refinment. We also consider one of the available submatrix approximations required for the AMLI preconditionner and derive an alternate approximation to Symmetric Successive Over Relaxation (SSOR) which can be computed with a single SOR-like iteration. We prove that under certain conditions of diagonal dominance, this approximation to SSOR is valid and show that it works similary to SSOR in practice by applying it to several test problems. The second effort is concerned with an efficient and maintenable 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. Is 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 presents 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 in terms of iterations to convergence for the parallel algorithm and parallel efficiency are measured. |
| PDF File |  Download |