Parallel Schur Complement Algorithms for the Solution of Sparse Linear Systems and Eigenvalue Problems

Abstract

Large sparse matrices arise in many applications in science and engineering, where the solution of a linear system or an eigenvalue problem is needed.While direct methods are still preferable when solving linear systems arising from two-dimensional models, iterative methods are widely used when solving linear systems arising from three-dimensional models due to their superiority in memory efficiency and computational efficiency. Meanwhile, iterative methods are also widely used for solving eigenvalue problems since no direct methods are available in general. Many efforts have been spent in developing iterative methods either for general problems or for specific applications. Among those methods, the Krylov subspace method is one of the most successful types. For finding the approximation solution of linear systems, incomplete LU (ILU) factorization preconditioned Krylov subspace methods are one of the most popular algorithms known for their robustness. On the other hand, the filtering strategies and Krylov subspace methods are one of the most efficient combinations for computing the entire spectrum of matrix pencils. Due to the increasingly larger size of matrix problems and the architecture of modern supercomputers, parallel computing has become an important component of numerical linear algebra. Domain decomposition (DD) methods partition the original problem into an interface problem and multiple decoupled subproblems that only depend on the solution of the interface problem. Those subproblems can be computed in parallel once the interface problem is solved. In the matrix representation of the problem, the interface problem is usually related to the Schur complement. Both ILU factorization and eigenvalue problems can be accelerated using the DD-based Schur complement approaches. This dissertation focuses on the parallel DD-based Schur complement approach for the solution of large sparse linear systems and eigenvalue problems on distributed memory systems, especially those equipped with GPUs.The unique contributions of this dissertation include a two-level Galerkin Schur complement preconditioner, a Schur complement low-rank preconditioner, and a polynomial-based Schur complement low-rank preconditioner. We also introduce an efficient parallel algorithm for computing several extreme eigenvalues and a parallel block Givens QR decomposition algorithm.