Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910177706377216 |
|---|---|
| author | Ghadimi, Saeed Jung, Woosuk L. Sujanani, Arnesh Torregrosa-Belén, David Wolkowicz, Henry |
| author_facet | Ghadimi, Saeed Jung, Woosuk L. Sujanani, Arnesh Torregrosa-Belén, David Wolkowicz, Henry |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23439 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling Ghadimi, Saeed Jung, Woosuk L. Sujanani, Arnesh Torregrosa-Belén, David Wolkowicz, Henry Optimization and Control Machine Learning Numerical Analysis 15A12, 65F35, 49J52, 49K10, 90C32, 90C26 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. |
| title | Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling |
| topic | Optimization and Control Machine Learning Numerical Analysis 15A12, 65F35, 49J52, 49K10, 90C32, 90C26 |
| url | https://arxiv.org/abs/2509.23439 |