Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling

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.

Optimization and Control (math.OC); Machine Learning (cs.LG); Numerical Analysis (math.NA)

arXiv:2509.23439 [math.OC]

(or arXiv:2509.23439v3 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2509.23439 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.