Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2110.03636 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912945818042368 |
|---|---|
| author | Regev, Shaked Chiang, Nai-Yuan Darve, Eric Petra, Cosmin G. Saunders, Michael A. Świrydowicz, Kasia Peleš, Slaven |
| author_facet | Regev, Shaked Chiang, Nai-Yuan Darve, Eric Petra, Cosmin G. Saunders, Michael A. Świrydowicz, Kasia Peleš, Slaven |
| contents | We propose a solution strategy for linear systems arising in interior method optimization, which is suitable for implementation on hardware accelerators such as graphical processing units (GPUs). The current gold standard for solving these systems is the LDL^T factorization. However, LDL^T requires pivoting during factorization, which substantially increases communication cost and degrades performance on GPUs. Our novel approach solves a large indefinite system by solving multiple smaller positive definite systems, using an iterative solve for 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 and show that on large systems it can efficiently utilize GPUs and outperform LDL^T factorization of the full system. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_03636 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Hybrid Direct-Iterative Method for Solving KKT Linear Systems Regev, Shaked Chiang, Nai-Yuan Darve, Eric Petra, Cosmin G. Saunders, Michael A. Świrydowicz, Kasia Peleš, Slaven Optimization and Control Distributed, Parallel, and Cluster Computing 15, 65, 68 G.1 We propose a solution strategy for linear systems arising in interior method optimization, which is suitable for implementation on hardware accelerators such as graphical processing units (GPUs). The current gold standard for solving these systems is the LDL^T factorization. However, LDL^T requires pivoting during factorization, which substantially increases communication cost and degrades performance on GPUs. Our novel approach solves a large indefinite system by solving multiple smaller positive definite systems, using an iterative solve for 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 and show that on large systems it can efficiently utilize GPUs and outperform LDL^T factorization of the full system. |
| title | A Hybrid Direct-Iterative Method for Solving KKT Linear Systems |
| topic | Optimization and Control Distributed, Parallel, and Cluster Computing 15, 65, 68 G.1 |
| url | https://arxiv.org/abs/2110.03636 |