Scholarlink

<p>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 dimensions 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(10^7\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>10</mn> <mn>7</mn> </msup> </math></EquationSource> </InlineEquation>. Notably, our approach is efficient and implementable using only black-box matrix-vector product operations, making it highly practical for various applications.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Scalable approximate optimal diagonal preconditioning

  • 期刊论文

  • 发表日期：

    2026年2月14日

查看全文
  • Wenzhi Gao,
  • Zhaonan Qu,
  • Madeleine Udell,
  • Yinyu Ye

摘要

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 dimensions 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\) 10 7 . Notably, our approach is efficient and implementable using only black-box matrix-vector product operations, making it highly practical for various applications.