Preconditioning is essential
in many areas of mathematics, and in particular
is a fundamental tool for accelerating
iterative methods for solving linear systems.
In this work, we study optimal diagonal preconditioning
under two distinct notions of conditioning:
the classical worst-case \(\kappa\)-condition number
and the averaging-based \(\omega\)-condition number.
We observe that \(\omega\)-optimal preconditioning generally
outperforms \(\kappa\)-optimal preconditioning.
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. Numerical results indicate that our approach is substantially more
scalable, efficient, and accurate than existing SDP-based methods, often
achieving dramatic speedups.
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.
These results suggest that the
\(\omega\)-condition number is
more predictive of practical
solver performance
and highlight
the advantages of
\(\omega\)-based preconditioning in large-scale settings.