Multilevel preconditioners: analysis, performance enhancements and parallel algorithms
Xian-Zhong Guo · 1992
The finite element and finite difference methods are common numerical techniques for solving partial differential equations in many application areas. Linear system solvers are indispensable to the finite element and finite difference computations. One standard iterative solver for the symmetric positive definite matrix is the preconditioned conjugate gradient (PCG) method. A good preconditioner is crucial for a good performance of the PCG method. We study in this thesis a class of preconditioners, multilevel preconditioners, and their performances on parallel computers. We study the hierarchical basis preconditioner (HB), the Bramble-Pasciak-Xu parallel multilevel preconditioner (BPX), the hierarchical basis multigrid method (HBMG), the algebraic hierarchical basis multigrid method (AHBMG), and the Axelsson-Vassilevski algebraic multilevel iterative preconditioner (AMLI). We present and study several new variants of the hierarchical basis and BPX methods, which enhance the performance of the both multilevel methods. For a class of problems consisting of and piecewise anisotropic problems, we develop a grid-generation strategy that relates the multilevel preconditioners to the underlying operator, and we demonstrate that this strategy is effective in terms of both iteration counts and elapsed time. We also propose and study an optimal algebraic multilevel method, the algebraic hierarchical basis multigrid (AHBMG) method. The method is a generalization of the HBMG method and is similar to the AMLI method. As for the AMLI method, the analysis of the AHBMG method is purely algebraic and the main mathematical tool is the CBS inequality. In addition, we present new parallel algorithms for both the hierarchical basis and BPX methods. Furthermore, the computational complexity and some performance issues of both multilevel and algebraic preconditioners are discussed.