提出更优的对角预条件方法,兼顾计算效率与实际迭代性能。
Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling
- 用伪凸优化重构预条件问题,可高效求解且全局最优。
- ω-最优预条件比κ-最优更省计算,实际迭代更快收敛。
- 首次统一给出κ与ω最优的显式条件,适合大规模线性系统求解者。
本文研究基于经典最坏情况κ-条件数和平均型ω-条件数的最优对角预条件。针对κ-最优问题,推导出基于仿射的伪凸重构,具有三个优势:所有驻点均为全局最优、次梯度计算廉价、优化变量为n维向量而非SDP中的n×n矩阵。设计了一种简单高效的次梯度算法,收敛性有保证,相比现有SDP方法更高效准确。对于ω-条件数,给出了对角与分块对角预条件的显式最优刻画。特别地,证明雅可比预条件和行列归一化均为ω-最优,矩阵平衡算法单调降低ω并收敛至双侧问题的驻点。据我们所知,这是首个统一且显式的κ与ω-最优条件刻画。数值实验揭示:虽κ-最优预条件在最坏情况下改善更大,但ω-最优预条件计算成本更低,且在预条件共轭梯度(PCG)和最小二乘法(LSQR)中表现更优。将ω-最优缩放应用于已κ-最优预条件的线性系统,可进一步减少PCG迭代次数。
原文摘要 · Abstract (English)
We study optimal diagonal preconditioning using the classical worst-case $κ$-condition number and the averaging-based $ω$-condition number. For the $κ$-optimal preconditioning problem, we derive an affine-based pseudoconvex reformulation with three key advantages: all stationary points are global minima, subgradients are inexpensive to compute, and the optimization variable is an $n$-dimensional vector rather than an $n\times n$ matrix as in semidefinite programming (SDP) approaches. We develop a simple and highly efficient subgradient method, with convergence guarantees, for solving this pseudoconvex formulation that is substantially more scalable and accurate than existing SDP-based methods. For the $ω$-condition number, we provide explicit characterizations of optimal diagonal and block diagonal preconditioners. In particular, we show that several classical preconditioners, including Jacobi and row/column normalization, are $ω$-optimal, and that matrix balancing schemes monotonically reduce $ω$ and converge to stationary points of the two-sided problem. To the best of our knowledge, this is the first unified and explicit characterization of optimality conditions for both $κ$ and $ω$-based preconditioning. Our numerical experiments further reveal a striking phenomenon: although $κ$-optimal preconditioners achieve stronger reductions in the worst-case condition number, $ω$-optimal preconditioners are substantially cheaper to compute and yield better performance for iterative methods such as preconditioned conjugate gradient (PCG) and least squares method (LSQR). Moreover, applying $ω$-optimal scaling to linear systems that are already $κ$-optimally preconditioned leads to further improvements in PCG iterations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。