Optimal Diagonal Preconditioning
Zhaonan Qu, Wenzhi Gao, Oliver Hinder, Yinyu Ye, Zhengyuan Zhou · Operations Research · 2024
A New Practical Algorithm Enables Optimal Preconditioning A classic and important question in optimization and numerical methods is how to find diagonal preconditioners to maximally reduce the condition number of any matrix with full rank. Until recently, few practical methods could handle large sparse matrices. In “Optimal Diagonal Preconditioning,” the authors show that this problem can be modeled using quasiconvex optimization and semidefinite programming. Leveraging these insights, they develop algorithms to efficiently find optimal diagonal preconditioners for large sparse systems. They find that although heuristic diagonal preconditioners are popular in practice, their performance at reducing condition numbers could have a significant gap to optimal diagonal preconditioners. This work provides theoretical foundation for future works on optimal preconditioning as well as practical implementations that could be used to build more sophisticated software for optimal preconditioning at scale. A main advantage of the framework in “Optimal Diagonal Preconditioning” is its potential to be scaled up to handle even larger matrices, which is an exciting direction for numerical optimization.