Scalable Approximate Optimal Diagonal Preconditioning
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909378504818688 |
|---|---|
| author | Gao, Wenzhi Qu, Zhaonan Udell, Madeleine Ye, Yinyu |
| author_facet | Gao, Wenzhi Qu, Zhaonan Udell, Madeleine Ye, Yinyu |
| contents | We consider the problem of finding the optimal diagonal preconditioner for a positive definite matrix. Although this problem has been shown to be solvable and various methods have been proposed, none of the existing approaches are scalable to matrices of large dimension, or when access is limited to black-box matrix-vector products, thereby significantly limiting their practical application. In view of these challenges, we propose practical algorithms applicable to finding approximate optimal diagonal preconditioners of large sparse systems. Our approach is based on the idea of dimension reduction, and combines techniques from semi-definite programming (SDP), random projection, semi-infinite programming (SIP), and column generation. Numerical experiments demonstrate that our method scales to sparse matrices of size greater than $10^7$. Notably, our approach is efficient and implementable using only black-box matrix-vector product operations, making it highly practical for a wide variety of applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15594 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Scalable Approximate Optimal Diagonal Preconditioning Gao, Wenzhi Qu, Zhaonan Udell, Madeleine Ye, Yinyu Numerical Analysis Optimization and Control We consider the problem of finding the optimal diagonal preconditioner for a positive definite matrix. Although this problem has been shown to be solvable and various methods have been proposed, none of the existing approaches are scalable to matrices of large dimension, or when access is limited to black-box matrix-vector products, thereby significantly limiting their practical application. In view of these challenges, we propose practical algorithms applicable to finding approximate optimal diagonal preconditioners of large sparse systems. Our approach is based on the idea of dimension reduction, and combines techniques from semi-definite programming (SDP), random projection, semi-infinite programming (SIP), and column generation. Numerical experiments demonstrate that our method scales to sparse matrices of size greater than $10^7$. Notably, our approach is efficient and implementable using only black-box matrix-vector product operations, making it highly practical for a wide variety of applications. |
| title | Scalable Approximate Optimal Diagonal Preconditioning |
| topic | Numerical Analysis Optimization and Control |
| url | https://arxiv.org/abs/2312.15594 |