Parallel multilevel block ILU preconditioning techniques for solving general sparse linear systems

In many numerical simulation and modeling problems, the most CPU consuming part of the computation is to solve some large sparse linear systems, in the form of Ax = b. For solving such linear systems, preconditioned Krylov subspace methods have become a popular choice of iterative solution techniques due to their more favorable memory and computational costs, compared to the direct solution methods based on Gaussian elimination. The convergence rate of a preconditioned iterative method is usually dictated by the quality of the preconditioner.;In this thesis, we present a class of parallel preconditioning strategies utilizing multilevel block incomplete LU (ILU) factorization techniques to solve large sparse linear systems. In Chapter 2, we will discuss two level block ILU preconditioning strategies. In this part, a Schur complement matrix is generated in a parallel environment.;Then a class of truly parallel multilevel ILU preconditioning techniques are presented in Chapter 3. The preconditioners are constructed by exploiting the concept of block independent sets. One of the most difficult works in this parallel implementation is how to find a block independent set in a distributed environment. Two algorithms for block independent set searching are proposed. In order to find a larger block independent set in parallel and to achieve better parallel performance of our preconditioners, a new parallel block independent set algorithm is proposed. A few implementations of the parallel multilevel ILU preconditioners with different block independent set construction strategies are compared in Chapter 4.;Optimizing the performance of a parallel program requires attention to CPU utilization, memory subsystem utilization, communication efficiency, and other details. In Chapter 5, we will mainly discuss the parallel performance of the parallel block ILU preconditioner PBILUM. We conduct performance analysis of PBILUM on both the preconditioner construction phase and iterative solution phase.;Some theoretical analyses are given in Chapter 6. In this chapter, the analytical bounds for the Schur complement and preconditioned errors matrices are demonstrated. The distribution of eigenvalues of the reduced matrix is discussed. Also based on some special data structure of the coefficient matrix arising from discretization of elliptic partial differential equations, two problem-tailored strategies for the block independent set searching are proposed.;The last chapter is my future research plan along the line of this research work.