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

arXiv:2509.23439v2 Announce Type: replace-cross 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 nimes 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.

Source: arXiv cs.LG | 2026-05-01