Abstract:We study optimal diagonal preconditioning using the classical worst-case $\kappa$-condition number and the averaging-based $\omega$-condition number.
For the $\kappa$-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 $\omega$-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 $\omega$-optimal, and that matrix balancing schemes monotonically reduce $\omega$ 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 $\kappa$ and $\omega$-based preconditioning.
Our numerical experiments further reveal a striking phenomenon: although $\kappa$-optimal preconditioners achieve stronger reductions in the worst-case condition number, $\omega$-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 $\omega$-optimal scaling to linear systems that are already $\kappa$-optimally preconditioned leads to further improvements in PCG iterations.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG); Numerical Analysis (math.NA) |
| MSC classes: | 15A12, 65F35, 49J52, 49K10, 90C32, 90C26 |
| Cite as: | arXiv:2509.23439 [math.OC] |
| (or arXiv:2509.23439v2 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2509.23439 arXiv-issued DOI via DataCite |
From: Arnesh Sujanani [view email]
[v1]
Sat, 27 Sep 2025 18:16:21 UTC (631 KB)
[v2]
Wed, 29 Apr 2026 18:13:32 UTC (675 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。