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

Thumbnail Image

Persistent link to this item

View Statistics

Journal Title

Journal ISSN

Volume Title


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

Published Date




Thesis or Dissertation


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.


University of Minnesota Ph.D. dissertation. July 2023. Major: Computer Science. Advisor: Yousef Saad. 1 computer file (PDF); ix, 169 pages.

Related to




Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Xu, Tianshi. (2023). Parallel Schur Complement Algorithms for the Solution of Sparse Linear Systems and Eigenvalue Problems. Retrieved from the University Digital Conservancy,

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.