Research On Scalable Parallel Algebraic Multigrid Algorithms

With the development and application of advanced parallel computers, the high-resolution numerical simulation for complicated multi-physics system is possible. Solving large scale sparse linear systems arising from the discretization of Partial Differential Equations(PDEs) are required in many numerical simulations, and iterative method is the only feasible way to solve such type of equations due to the storage and time complexity constraint. However, due to the complexity of the physical model and large scale of the systems, scalable iterative methods are required. Many factors contribute to the scalability of the iterative method, mainly including two aspects: algorithmic scalability and parallelization scalability. The former describes how the total computational works grow with the size of problem and the number of processors. The later describes the parallel efficiency of a single iteration on a parallel computer. Most iterative methods used today, however, lack the scalability mentioned above. So, it is urgent to design scalable iterative methods to address the difficulties encountered in the large-scale complicated physics simulations using hundreds or thousands of processors.Algebraic multigrid (AMG) is a well known iterative method with optimal algorithmic scalability for many complicated real applications. However, the parallelization of AMG is challenging because of the component of grid coarsening is sequential. In recent years. Many parallel coarsening strategies have been presented by balancing the algorithmic scalability and the parallelization scalability. This dissertation mainly focus on this topic and presents some new methods and techniques.The main contributions of this dissertation are summarized as follows:1. Firstly, in order to measure the algorithmic scalability and the parallelization scalability of a iterative method, a suit of scalability analysis approach is presented. We introduce the concept of scalability factor to describe how the parallel execution time will be enlarged while compared to the serial execution. So, the algorithmic scalability and parallelization scalability are described by their contributions on the scalability factor. Secondly, we analyze the scalability of parallel AMG algorithms using this method. Some important results are got for the design of scalable algorithms.2. Two new parallel coarsening strategies are proposed: Relaxed-type RS and CLJP (RRS & RCLJP). The main idea of these strategies is to smartly synchronize processors during the coarsening process of well-known RS0 or CLJP strategies. Qualitative analyses and numerical experiments show that our new strategies perform better using hundreds of processors, not only in faster convergence but also in smaller operator complexity. They show better scalability if we compare them to well-known parallel coarsening strategies such as RS3, Falgout and CLJP.3. The concepts of single-scale and multi-scale for sparse matrix are presented according to the strength of connection among grid points from the algebraic point of view. These concepts discover the difficulties on the solution of the linear systems. A blocking technique is presented to find all single-scale blocks partitioning the grid. In each block, connections have the same scale of strength, so, inherent parallel coarsening strategies and simple point relaxation scheme can get good algorithmic scalability. However, in the regions linking different scales of blocks, we call them the algebraic interfaces, the coarsening and relaxation should be especially designed. Based on these observations, new heuristic approaches for effective AMG algorithms are presented.4. Based on the blocking technique, two new AMG algorithms are presented. One is the SPRC-AMG method using the Smallest-scale Primary Relaxation and Coarsening strategies, another is the IPRC-AMG method using the Interface Primary Relaxation and Coarsening strategies. The main idea of the former is to decrease or eliminate the multi-scale property of the coarse operator through relaxation and coarsening in the local blocks with smallest scale property. The later method firstly selects coarse points within the algebraic interfaces, and second selects other coarse points in the interior of blocks. Numerical experiments show the effectiveness of our methods. The convergence analysis of the SPRC-AMG method is also presented.5. By integrating the interface primary coarsening into the relaxed-type parallel coarsening strategies, interface primary relaxed-type parallel coarsening strategies (RIPC) is introduced. In this strategy, interface primary coarsening is regarded as the synchronization condition of the relaxed-type method. Specially, we use the well-known parallel coarsening strategy of PMIS in both the algebraic interfaces and the blocks. So, RIPC-PMIS coarsening strategy is formed. Numerical results on hundreds of processors show the effectiveness.6. A novel two-level iterative method is presented for solving 2D radiative diffusion equations with photon, electron, ion temperatures. The main idea of this method is to decouple one temperature from the other two by a special coarsening strategy, where all the variables related to electron temperature are forced selected coarse points, other variables (photon and ion temperatures) are all forced to be fine points. So, only several single temperature equations need to be solved instead of the coupled linear systems. Because of the multiscale property of the single temperature equations, we use the IPRC-AMG method presented in this dissertation to solve those single temperature equations. Numerical results show the effectiveness of our method.