Preconditioning techniques for sparse linear systems
Abstract/Contents
- Abstract
- We present two novel methods, SSAI and HyKKT, for sparse linear systems. The methods differ in that SSAI is meant to be an out of the box solver that is robust on many different types of Hermitian positive definite (HPD) linear systems and has a variant that can be used to solve general systems (including rectangular ones), but is not necessarily the best for a given linear system. This is due to the fact that SSAI in an effort to be general, ignores domain knowledge of the problem. In contrast, HyKKT is a specialized solver for very sparse symmetric indefinite linear systems with a Karush-Kuhn-Tucker (KKT) structure. These two methods represent the main parts of the thesis. Chapter 2 introduces SSAI, a method for solving a Hermitian positive definite linear system Ax=b, where A is an explicit sparse matrix (real or complex). A sparse approximate right inverse is computed and replaced by its symmetrization M, which is used as a left-right preconditioner in a modified version of the preconditioned conjugate-gradient method (PCG), where M is modified occasionally, if necessary, to make it more positive definite. Before symmetrization, M is formed column by column and can therefore be computed in parallel with no communication except at the beginning and end. PCG requires only matrix-vector multiplications with A and M (not solving a linear system with M), and so too can be carried out in parallel. We compare it with incomplete Cholesky factorization (the gold standard for PCG) and with a direct Cholesky factorization and solve on sparse matrices from various applications and show it is robust. For least-squares problems, we implement an analogous form of preconditioned Conjugate Gradient Least-Squares (PCGLS) and show it is also robust. The contributions of the work in Chapter 2 are summarized in Section 2.2. Chapter 3 introduces HyKKT, a solution strategy for the large indefinite linear systems arising in interior methods for nonlinear optimization. The method is suitable for implementation on hardware accelerators such as graphical processing units (GPUs). The current gold standard for sparse indefinite systems is the LBL factorization, where L is a lower triangular matrix and B is 1X1 or 2X2 block diagonal. However, this requires pivoting, which substantially increases communication cost and degrades performance on GPUs. Our approach solves a large indefinite system by solving multiple smaller positive definite systems, using an iterative solver on the Schur complement and an inner direct solve (via Cholesky factorization) within each iteration. Cholesky is stable without pivoting, thereby reducing communication and allowing reuse of the symbolic factorization. We demonstrate the practicality of our approach on large optimal power flow problems and show that it can efficiently utilize GPUs and outperform LBL factorization of the full system. The contributions of the work in Chapter 3 are summarized in Section 3.3.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2022; ©2022 |
| Publication date | 2022; 2022 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Regev, Shaked |
|---|---|
| Degree supervisor | Darve, Eric |
| Degree supervisor | Saunders, Michael A |
| Thesis advisor | Darve, Eric |
| Thesis advisor | Saunders, Michael A |
| Thesis advisor | Wootters, Mary |
| Thesis advisor | Ying, Lexing |
| Degree committee member | Wootters, Mary |
| Degree committee member | Ying, Lexing |
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Shaked Regev. |
|---|---|
| Note | Submitted to the Institute for Computationa and Mathematical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2022. |
| Location | https://purl.stanford.edu/zc485bz0015 |
Access conditions
- Copyright
- © 2022 by Shaked Regev
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...