Expand description
§Chapter 5.13 — Row and column scaling
New with task L1.5 (PLAN.md trilha L; the contract’s §5.4).
§Purpose
The entries of a constraint matrix often span many orders of magnitude
(1e-6 next to 1e6 in the same row), and every factorization pays
for it: pivot tests compare magnitudes, growth is measured against
max|a|, and the condition of A D Aᵀ in an interior-point method
is that of A squared. Equilibration replaces A by
A' = R A C with positive diagonal R = diag(row), C = diag(col)
chosen so that the nonzeros of A' are close to one in magnitude;
solutions are mapped back afterwards. This chapter computes such
factors by three classic policies (Equilibration) and applies or
removes them (Scaling).
§Notation
A ∈ R^{m×n} with nonzeros a_ij, (i, j) ∈ 𝒩; r_i, c_j > 0 the
row and column factors; a'_ij = r_i a_ij c_j. The spread of a
matrix is max |a'_ij| / min |a'_ij| over 𝒩 (one for a matrix
without nonzeros). For the logarithmic policies v_ij = log₂|a_ij|,
ρ_i = log₂ r_i, γ_j = log₂ c_j; n_i and n_j count the nonzeros
of row i and column j. Rounding to a power of two is
⌊x⌉₂ = 2^{round(log₂ x)}.
§Algorithm G (Geometric mean iteration; Maros 2003, §6.2)
G1. Set r_i ← 1, c_j ← 1.
G2. Repeat max_iters times:
(a) for every nonempty row i, r_i ← 1 / √(max_j |a_ij| c_j · min_j |a_ij| c_j);
(b) for every nonempty column j, c_j ← 1 / √(max_i r_i |a_ij| · min_i r_i |a_ij|).
G3. If power_of_two, replace every factor f by ⌊f⌉₂.
Each half-step makes the largest and the smallest entry of a row (a column) reciprocal, so the spread of every row and column is reduced towards its square root; a few passes suffice in practice (Maros recommends 4–8).
§Algorithm R (Curtis & Reid 1972, least squares)
Find ρ, γ minimizing Σ_{(i,j)∈𝒩} (v_ij + ρ_i + γ_j)², the sum of
squared logarithms of the scaled entries. The normal equations are
n_i ρ_i + Σ_{j:(i,j)∈𝒩} γ_j = −σ_i, σ_i = Σ_j v_ij (rows)
Σ_{i:(i,j)∈𝒩} ρ_i + n_j γ_j = −τ_j, τ_j = Σ_i v_ij (columns)a singular but consistent positive semidefinite system (adding t to
every ρ_i and −t to every γ_j changes nothing).
R1. Form σ, τ, n_i, n_j.
R2. Solve the normal equations by conjugate gradients preconditioned by
their diagonal diag(n_i, n_j) (Curtis & Reid’s own iteration is
this method), from ρ = γ = 0, for at most max_iters steps or
until the preconditioned residual rᵀ P⁻¹ r falls to ε_{f64}
times its initial value (the precision of the computation, not a
tuning constant). Empty rows and columns keep ρ_i = 0, γ_j = 0.
R3. r_i ← ⌊2^{ρ_i}⌉₂, c_j ← ⌊2^{γ_j}⌉₂: Curtis & Reid round to
powers of two, and so do we (exact unscaling, (S8)).
§Algorithm I (Infinity norm, once)
I1. r_i ← 1 / max_j |a_ij| for every nonempty row.
I2. c_j ← 1 / max_i r_i |a_ij| for every nonempty column.
After it every row and column of A' has infinity norm at most one and
every column exactly one. The factors are not rounded.
§Applying and removing
Scaling::apply maps each stored value to (a_ij · r_i) · c_j,
Scaling::unapply to (a'_ij / r_i) / c_j. The factors are
computed in f64 (they are a policy, not data) and enter T through
Real::from_f64.
§Invariants
(S8) (the contract’s) Round trip. When every factor is a power of two
— always for Algorithm R, for Algorithm G with power_of_two —
unapply(apply(A)) = A bit for bit, provided no product leaves the
normal range of T (no overflow, no subnormal result): a
multiplication or division by 2^k only changes the exponent.
Otherwise the round trip holds to working precision (two
roundings per entry each way). Checked by the tests of Chapter
5.13 and by a property test.
(S9) Every factor is finite and positive; a row or column without
nonzeros has factor one. Asserted in debug builds by
Scaling::compute and checked by Scaling::check_invariants.
§References
Curtis & Reid, “On the automatic scaling of matrices for Gaussian
elimination”, J. Inst. Maths Applics 10, 1972; Maros, Computational
Techniques of the Simplex Method (2003), ch. 6; Duff, Erisman & Reid,
Direct Methods for Sparse Matrices (2017), §6.10; HiGHS
HighsLpUtils scaling routines (read, not copied).
Structs§
- Scaling
- Row and column factors:
A' = diag(row) · A · diag(col)(invariants (S8), (S9)).
Enums§
- Equilibration
- Row/column equilibration policies (Algorithms G, R and I).