xingo_sparse/scaling.rs
1//! # Chapter 5.13 — Row and column scaling
2//!
3//! *New with task L1.5 (PLAN.md trilha L; the contract's §5.4).*
4//!
5//! ## Purpose
6//! The entries of a constraint matrix often span many orders of magnitude
7//! (`1e-6` next to `1e6` in the same row), and every factorization pays
8//! for it: pivot tests compare magnitudes, growth is measured against
9//! `max|a|`, and the condition of `A D Aᵀ` in an interior-point method
10//! is that of `A` squared. *Equilibration* replaces `A` by
11//! `A' = R A C` with positive diagonal `R = diag(row)`, `C = diag(col)`
12//! chosen so that the nonzeros of `A'` are close to one in magnitude;
13//! solutions are mapped back afterwards. This chapter computes such
14//! factors by three classic policies ([`Equilibration`]) and applies or
15//! removes them ([`Scaling`]).
16//!
17//! ## Notation
18//! `A ∈ R^{m×n}` with nonzeros `a_ij`, `(i, j) ∈ 𝒩`; `r_i`, `c_j > 0` the
19//! row and column factors; `a'_ij = r_i a_ij c_j`. The *spread* of a
20//! matrix is `max |a'_ij| / min |a'_ij|` over `𝒩` (one for a matrix
21//! without nonzeros). For the logarithmic policies `v_ij = log₂|a_ij|`,
22//! `ρ_i = log₂ r_i`, `γ_j = log₂ c_j`; `n_i` and `n_j` count the nonzeros
23//! of row `i` and column `j`. Rounding to a power of two is
24//! `⌊x⌉₂ = 2^{round(log₂ x)}`.
25//!
26//! ## Algorithm G (Geometric mean iteration; Maros 2003, §6.2)
27//! G1. Set `r_i ← 1`, `c_j ← 1`.
28//! G2. Repeat `max_iters` times:
29//! (a) for every nonempty row `i`, `r_i ← 1 / √(max_j |a_ij| c_j ·
30//! min_j |a_ij| c_j)`;
31//! (b) for every nonempty column `j`, `c_j ← 1 / √(max_i r_i |a_ij| ·
32//! min_i r_i |a_ij|)`.
33//! G3. If `power_of_two`, replace every factor `f` by `⌊f⌉₂`.
34//!
35//! Each half-step makes the largest and the smallest entry of a row (a
36//! column) reciprocal, so the spread of every row and column is reduced
37//! towards its square root; a few passes suffice in practice (Maros
38//! recommends 4–8).
39//!
40//! ## Algorithm R (Curtis & Reid 1972, least squares)
41//! Find `ρ`, `γ` minimizing `Σ_{(i,j)∈𝒩} (v_ij + ρ_i + γ_j)²`, the sum of
42//! squared logarithms of the scaled entries. The normal equations are
43//! ```text
44//! n_i ρ_i + Σ_{j:(i,j)∈𝒩} γ_j = −σ_i, σ_i = Σ_j v_ij (rows)
45//! Σ_{i:(i,j)∈𝒩} ρ_i + n_j γ_j = −τ_j, τ_j = Σ_i v_ij (columns)
46//! ```
47//! a singular but consistent positive semidefinite system (adding `t` to
48//! every `ρ_i` and `−t` to every `γ_j` changes nothing).
49//! R1. Form `σ`, `τ`, `n_i`, `n_j`.
50//! R2. Solve the normal equations by conjugate gradients preconditioned by
51//! their diagonal `diag(n_i, n_j)` (Curtis & Reid's own iteration is
52//! this method), from `ρ = γ = 0`, for at most `max_iters` steps or
53//! until the preconditioned residual `rᵀ P⁻¹ r` falls to `ε_{f64}`
54//! times its initial value (the precision of the computation, not a
55//! tuning constant). Empty rows and columns keep `ρ_i = 0`, `γ_j = 0`.
56//! R3. `r_i ← ⌊2^{ρ_i}⌉₂`, `c_j ← ⌊2^{γ_j}⌉₂`: Curtis & Reid round to
57//! powers of two, and so do we (exact unscaling, (S8)).
58//!
59//! ## Algorithm I (Infinity norm, once)
60//! I1. `r_i ← 1 / max_j |a_ij|` for every nonempty row.
61//! I2. `c_j ← 1 / max_i r_i |a_ij|` for every nonempty column.
62//! After it every row and column of `A'` has infinity norm at most one and
63//! every column exactly one. The factors are not rounded.
64//!
65//! ## Applying and removing
66//! [`Scaling::apply`] maps each stored value to `(a_ij · r_i) · c_j`,
67//! [`Scaling::unapply`] to `(a'_ij / r_i) / c_j`. The factors are
68//! computed in `f64` (they are a policy, not data) and enter `T` through
69//! [`Real::from_f64`].
70//!
71//! ## Invariants
72//! (S8) (the contract's) *Round trip.* When every factor is a power of two
73//! — always for Algorithm R, for Algorithm G with `power_of_two` —
74//! `unapply(apply(A)) = A` bit for bit, provided no product leaves the
75//! normal range of `T` (no overflow, no subnormal result): a
76//! multiplication or division by `2^k` only changes the exponent.
77//! Otherwise the round trip holds to working precision (two
78//! roundings per entry each way). Checked by the tests of Chapter
79//! 5.13 and by a property test.
80//! (S9) Every factor is finite and positive; a row or column without
81//! nonzeros has factor one. Asserted in debug builds by
82//! [`Scaling::compute`] and checked by [`Scaling::check_invariants`].
83//!
84//! ## References
85//! Curtis & Reid, "On the automatic scaling of matrices for Gaussian
86//! elimination", J. Inst. Maths Applics 10, 1972; Maros, *Computational
87//! Techniques of the Simplex Method* (2003), ch. 6; Duff, Erisman & Reid,
88//! *Direct Methods for Sparse Matrices* (2017), §6.10; HiGHS
89//! `HighsLpUtils` scaling routines (read, not copied).
90
91use crate::real::{Real, approx_eq, is_exact_zero, le_exact, lt};
92use crate::{CscMatrix, SparseError};
93
94/// Row/column equilibration policies (Algorithms G, R and I).
95#[derive(Clone, Copy, Debug, PartialEq)]
96pub enum Equilibration {
97 /// Geometric mean iteration (Maros 2003, ch. 6), Algorithm G, rounded
98 /// to powers of two when `power_of_two` (exact unscaling, (S8)).
99 Geometric {
100 /// Passes over rows and columns.
101 max_iters: usize,
102 /// Round the factors to powers of two.
103 power_of_two: bool,
104 },
105 /// Curtis & Reid (1972) least-squares scaling, Algorithm R: at most
106 /// `max_iters` conjugate-gradient steps; factors are powers of two.
107 CurtisReid {
108 /// Conjugate-gradient steps.
109 max_iters: usize,
110 },
111 /// Rows then columns by the infinity norm, once (Algorithm I).
112 InfinityNorm,
113}
114
115/// Row and column factors: `A' = diag(row) · A · diag(col)` (invariants
116/// (S8), (S9)).
117#[derive(Clone, Debug, PartialEq)]
118pub struct Scaling<T: Real = f64> {
119 /// `r_i`, one per row.
120 pub row: Vec<T>,
121 /// `c_j`, one per column.
122 pub col: Vec<T>,
123}
124
125impl<T: Real> Scaling<T> {
126 /// The factors of `a` under `policy` (Algorithms G, R, I).
127 ///
128 /// ```
129 /// use xingo_sparse::{CscMatrix, Col, Equilibration, Row, Scaling};
130 /// let a = CscMatrix::from_triplets(2, 2, &[
131 /// (Row(0), Col(0), 1e-3), (Row(1), Col(0), 4.0), (Row(1), Col(1), 1e3),
132 /// ])
133 /// .unwrap();
134 /// let policy = Equilibration::Geometric { max_iters: 4, power_of_two: true };
135 /// let s = Scaling::compute(&a, policy);
136 /// assert!(s.spread(&a) < 1e6); // the spread of `a` itself is 1e3 / 1e-3
137 /// let mut b = a.clone();
138 /// s.apply(&mut b);
139 /// s.unapply(&mut b);
140 /// assert_eq!(a, b); // (S8): powers of two round-trip exactly
141 /// ```
142 #[must_use]
143 pub fn compute(a: &CscMatrix<T>, policy: Equilibration) -> Self {
144 let (row, col) = match policy {
145 Equilibration::Geometric {
146 max_iters,
147 power_of_two,
148 } => geometric(a, max_iters, power_of_two),
149 Equilibration::CurtisReid { max_iters } => curtis_reid(a, max_iters),
150 Equilibration::InfinityNorm => infinity_norm(a),
151 };
152 let s = Self {
153 row: row.into_iter().map(T::from_f64).collect(),
154 col: col.into_iter().map(T::from_f64).collect(),
155 };
156 debug_assert_eq!(s.check_invariants(), Ok(()));
157 debug_assert!(
158 !matches!(
159 policy,
160 Equilibration::CurtisReid { .. }
161 | Equilibration::Geometric {
162 power_of_two: true,
163 ..
164 }
165 ) || s.is_power_of_two(),
166 "(S8): the policy rounds to powers of two"
167 );
168 s
169 }
170
171 /// `A ← diag(row) · A · diag(col)` in place.
172 ///
173 /// # Panics
174 /// If the factor lengths do not match the dimensions of `a`.
175 pub fn apply(&self, a: &mut CscMatrix<T>) {
176 self.assert_fits(a);
177 for j in 0..a.n_cols() {
178 let cj = self.col[j];
179 for p in a.col_ptr[j]..a.col_ptr[j + 1] {
180 let ri = self.row[a.row_idx[p] as usize];
181 a.val[p] = a.val[p] * ri * cj;
182 }
183 }
184 }
185
186 /// `A ← diag(row)⁻¹ · A · diag(col)⁻¹` in place: the inverse of
187 /// [`Scaling::apply`], exactly so for powers of two ((S8)).
188 ///
189 /// # Panics
190 /// If the factor lengths do not match the dimensions of `a`.
191 pub fn unapply(&self, a: &mut CscMatrix<T>) {
192 self.assert_fits(a);
193 for j in 0..a.n_cols() {
194 let cj = self.col[j];
195 for p in a.col_ptr[j]..a.col_ptr[j + 1] {
196 let ri = self.row[a.row_idx[p] as usize];
197 a.val[p] = a.val[p] / ri / cj;
198 }
199 }
200 }
201
202 /// The spread `max|a'| / min|a'|` over the nonzeros of the scaled
203 /// matrix `a' = diag(row) · a · diag(col)` (`a` itself is not
204 /// modified); one when `a` has no nonzeros.
205 ///
206 /// # Panics
207 /// If the factor lengths do not match the dimensions of `a`.
208 pub fn spread(&self, a: &CscMatrix<T>) -> T {
209 self.assert_fits(a);
210 let mut big = T::ZERO;
211 let mut small = T::ZERO;
212 let mut any = false;
213 for j in 0..a.n_cols() {
214 for p in a.col_ptr[j]..a.col_ptr[j + 1] {
215 let v = (a.val[p] * self.row[a.row_idx[p] as usize] * self.col[j]).abs();
216 if any {
217 big = big.max(v);
218 small = small.min(v);
219 } else {
220 (big, small, any) = (v, v, true);
221 }
222 }
223 }
224 if any && !is_exact_zero(small) {
225 big / small
226 } else {
227 T::ONE
228 }
229 }
230
231 /// Checks (S9): every factor finite and positive.
232 pub fn check_invariants(&self) -> Result<(), SparseError> {
233 for (what, f) in [
234 ("row scale factor", &self.row),
235 ("column scale factor", &self.col),
236 ] {
237 for (k, &x) in f.iter().enumerate() {
238 if !x.is_finite() || !lt(T::ZERO, x) {
239 return Err(SparseError::InvalidValue {
240 what,
241 index: k,
242 value: x.to_f64(),
243 });
244 }
245 }
246 }
247 Ok(())
248 }
249
250 /// Every factor is a power of two (the premise of the exact case of
251 /// (S8)).
252 fn is_power_of_two(&self) -> bool {
253 self.row
254 .iter()
255 .chain(&self.col)
256 .all(|&x| approx_eq(x.to_f64(), round_pow2(x.to_f64()), 0.0))
257 }
258
259 fn assert_fits(&self, a: &CscMatrix<T>) {
260 assert_eq!(self.row.len(), a.n_rows, "scaling: row factors do not fit");
261 assert_eq!(
262 self.col.len(),
263 a.n_cols(),
264 "scaling: column factors do not fit"
265 );
266 }
267}
268
269/// `⌊x⌉₂ = 2^{round(log₂ x)}` for a finite `x > 0`.
270fn round_pow2(x: f64) -> f64 {
271 x.log2().round().exp2()
272}
273
274/// Algorithm G.
275fn geometric<T: Real>(
276 a: &CscMatrix<T>,
277 max_iters: usize,
278 power_of_two: bool,
279) -> (Vec<f64>, Vec<f64>) {
280 let (m, n) = (a.n_rows, a.n_cols());
281 // G1.
282 let mut row = vec![1.0_f64; m];
283 let mut col = vec![1.0_f64; n];
284 let mut rmax = vec![0.0_f64; m];
285 let mut rmin = vec![f64::INFINITY; m];
286 for _ in 0..max_iters {
287 // G2 (a): row extremes of |a_ij| c_j, gathered column by column.
288 rmax.fill(0.0);
289 rmin.fill(f64::INFINITY);
290 for (j, &cj) in col.iter().enumerate() {
291 for p in a.col_ptr[j]..a.col_ptr[j + 1] {
292 let i = a.row_idx[p] as usize;
293 let v = a.val[p].to_f64().abs() * cj;
294 rmax[i] = rmax[i].max(v);
295 rmin[i] = rmin[i].min(v);
296 }
297 }
298 for i in 0..m {
299 if lt(0.0, rmax[i]) {
300 row[i] = (rmax[i] * rmin[i]).sqrt().recip();
301 }
302 }
303 // G2 (b).
304 for (j, cj) in col.iter_mut().enumerate() {
305 let (mut big, mut small) = (0.0_f64, f64::INFINITY);
306 for p in a.col_ptr[j]..a.col_ptr[j + 1] {
307 let v = row[a.row_idx[p] as usize] * a.val[p].to_f64().abs();
308 big = big.max(v);
309 small = small.min(v);
310 }
311 if lt(0.0, big) {
312 *cj = (big * small).sqrt().recip();
313 }
314 }
315 }
316 // G3.
317 if power_of_two {
318 for f in row.iter_mut().chain(col.iter_mut()) {
319 *f = round_pow2(*f);
320 }
321 }
322 (row, col)
323}
324
325/// Algorithm R: preconditioned conjugate gradients on the normal
326/// equations of the Curtis–Reid least-squares problem.
327#[allow(clippy::cast_precision_loss)] // counts of nonzeros, far below 2⁵³
328fn curtis_reid<T: Real>(a: &CscMatrix<T>, max_iters: usize) -> (Vec<f64>, Vec<f64>) {
329 let (m, n) = (a.n_rows, a.n_cols());
330 // R1.
331 let mut cnt = vec![0.0_f64; m + n];
332 let mut g = vec![0.0_f64; m + n];
333 for j in 0..n {
334 for p in a.col_ptr[j]..a.col_ptr[j + 1] {
335 let i = a.row_idx[p] as usize;
336 let v = a.val[p].to_f64().abs().log2();
337 g[i] += v;
338 g[m + j] += v;
339 cnt[i] += 1.0;
340 cnt[m + j] += 1.0;
341 }
342 }
343 // The operator z ↦ M z of the normal equations.
344 let apply_m = |z: &[f64], out: &mut [f64]| {
345 for (o, (&c, &zk)) in out.iter_mut().zip(cnt.iter().zip(z)) {
346 *o = c * zk;
347 }
348 for j in 0..n {
349 for &i in &a.row_idx[a.col_ptr[j]..a.col_ptr[j + 1]] {
350 let i = i as usize;
351 out[i] += z[m + j];
352 out[m + j] += z[i];
353 }
354 }
355 };
356 // Diagonal preconditioner; empty rows/columns are excluded (zero).
357 let pinv: Vec<f64> = cnt
358 .iter()
359 .map(|&c| if lt(0.0, c) { c.recip() } else { 0.0 })
360 .collect();
361 let dot = |x: &[f64], y: &[f64]| -> f64 { x.iter().zip(y).map(|(a, b)| a * b).sum() };
362 // R2. z = 0, residual = rhs = −g.
363 let mut z = vec![0.0_f64; m + n];
364 let mut res: Vec<f64> = g.iter().map(|&v| -v).collect();
365 let mut s: Vec<f64> = res.iter().zip(&pinv).map(|(r, p)| r * p).collect();
366 let mut dir = s.clone();
367 let mut q = vec![0.0_f64; m + n];
368 let mut rs = dot(&res, &s);
369 let stop = rs * f64::EPSILON;
370 for _ in 0..max_iters {
371 if le_exact(rs, stop) {
372 break;
373 }
374 apply_m(&dir, &mut q);
375 let dq = dot(&dir, &q);
376 if !lt(0.0, dq) {
377 break;
378 }
379 let alpha = rs / dq;
380 for k in 0..m + n {
381 z[k] += alpha * dir[k];
382 res[k] -= alpha * q[k];
383 s[k] = res[k] * pinv[k];
384 }
385 let rs_new = dot(&res, &s);
386 let beta = rs_new / rs;
387 for k in 0..m + n {
388 dir[k] = s[k] + beta * dir[k];
389 }
390 rs = rs_new;
391 }
392 // R3.
393 let row = z[..m].iter().map(|&x| x.round().exp2()).collect();
394 let col = z[m..].iter().map(|&x| x.round().exp2()).collect();
395 (row, col)
396}
397
398/// Algorithm I.
399fn infinity_norm<T: Real>(a: &CscMatrix<T>) -> (Vec<f64>, Vec<f64>) {
400 let (m, n) = (a.n_rows, a.n_cols());
401 let mut rmax = vec![0.0_f64; m];
402 for j in 0..n {
403 for p in a.col_ptr[j]..a.col_ptr[j + 1] {
404 let i = a.row_idx[p] as usize;
405 rmax[i] = rmax[i].max(a.val[p].to_f64().abs());
406 }
407 }
408 // I1.
409 let row: Vec<f64> = rmax
410 .iter()
411 .map(|&v| if lt(0.0, v) { v.recip() } else { 1.0 })
412 .collect();
413 // I2.
414 let col = (0..n)
415 .map(|j| {
416 let big = (a.col_ptr[j]..a.col_ptr[j + 1])
417 .map(|p| row[a.row_idx[p] as usize] * a.val[p].to_f64().abs())
418 .fold(0.0_f64, f64::max);
419 if lt(0.0, big) { big.recip() } else { 1.0 }
420 })
421 .collect();
422 (row, col)
423}
424
425#[cfg(test)]
426mod tests {
427 use super::*;
428 use crate::{Col, Row};
429 use proptest::prelude::*;
430
431 fn wide() -> CscMatrix {
432 CscMatrix::from_triplets(
433 3,
434 3,
435 &[
436 (Row(0), Col(0), 1e-4),
437 (Row(0), Col(2), 3e2),
438 (Row(1), Col(0), 2.0),
439 (Row(1), Col(1), -7e5),
440 (Row(2), Col(1), 5e-3),
441 (Row(2), Col(2), 1.5),
442 ],
443 )
444 .unwrap()
445 }
446
447 const POLICIES: [Equilibration; 4] = [
448 Equilibration::Geometric {
449 max_iters: 6,
450 power_of_two: true,
451 },
452 Equilibration::Geometric {
453 max_iters: 6,
454 power_of_two: false,
455 },
456 Equilibration::CurtisReid { max_iters: 50 },
457 Equilibration::InfinityNorm,
458 ];
459
460 #[test]
461 fn every_policy_reduces_the_spread() {
462 let a = wide();
463 let unit = Scaling {
464 row: vec![1.0; 3],
465 col: vec![1.0; 3],
466 };
467 let before = unit.spread(&a);
468 for policy in POLICIES {
469 let s = Scaling::compute(&a, policy);
470 assert_eq!(s.check_invariants(), Ok(()));
471 assert!(
472 lt(s.spread(&a), before),
473 "{policy:?}: {} vs {before}",
474 s.spread(&a)
475 );
476 }
477 }
478
479 #[test]
480 fn s8_round_trip() {
481 let a = wide();
482 for policy in POLICIES {
483 let s = Scaling::compute(&a, policy);
484 let mut b = a.clone();
485 s.apply(&mut b);
486 s.unapply(&mut b);
487 if s.is_power_of_two() {
488 assert_eq!(a, b, "{policy:?}");
489 } else {
490 for (x, y) in a.val.iter().zip(&b.val) {
491 assert!(approx_eq(*x, *y, 4.0 * f64::EPSILON), "{policy:?}");
492 }
493 }
494 }
495 }
496
497 #[test]
498 fn infinity_norm_makes_columns_unit() {
499 let a = wide();
500 let s = Scaling::compute(&a, Equilibration::InfinityNorm);
501 let mut b = a.clone();
502 s.apply(&mut b);
503 for j in 0..3 {
504 let (_, v) = b.col(Col::from_usize(j));
505 let big = v.iter().fold(0.0_f64, |m, x| m.max(x.abs()));
506 assert!(approx_eq(big, 1.0, 4.0 * f64::EPSILON));
507 }
508 }
509
510 #[test]
511 fn empty_rows_and_columns_keep_unit_factors() {
512 let a = CscMatrix::from_triplets(3, 3, &[(Row(0), Col(0), 8.0)]).unwrap();
513 for policy in POLICIES {
514 let s = Scaling::compute(&a, policy);
515 assert!(approx_eq(s.row[1], 1.0, 0.0) && approx_eq(s.col[2], 1.0, 0.0));
516 assert!(approx_eq(s.spread(&a), 1.0, 0.0));
517 }
518 let e = CscMatrix::<f64>::zeros(2, 2);
519 assert!(approx_eq(
520 Scaling::compute(&e, POLICIES[0]).spread(&e),
521 1.0,
522 0.0
523 ));
524 }
525
526 #[test]
527 fn curtis_reid_is_exact_on_a_rank_one_magnitude_pattern() {
528 // |a_ij| = 2^{p_i + q_j}: the least-squares optimum makes every
529 // scaled entry ±1.
530 let p = [3, -5, 0];
531 let q = [-2, 7, 1];
532 let mut t = Vec::new();
533 for (i, &pi) in p.iter().enumerate() {
534 for (j, &qj) in q.iter().enumerate() {
535 let sign = if (i + j) % 2 == 0 { 1.0 } else { -1.0 };
536 t.push((
537 Row::from_usize(i),
538 Col::from_usize(j),
539 sign * f64::from(pi + qj).exp2(),
540 ));
541 }
542 }
543 let a = CscMatrix::from_triplets(3, 3, &t).unwrap();
544 let s = Scaling::compute(&a, Equilibration::CurtisReid { max_iters: 20 });
545 assert!(approx_eq(s.spread(&a), 1.0, 0.0));
546 }
547
548 proptest! {
549 #![proptest_config(ProptestConfig::with_cases(64))]
550 /// (S8) on random matrices whose magnitudes span 2^±40.
551 #[test]
552 fn s8_round_trip_is_exact_for_powers_of_two(
553 m in 1_usize..12, n in 1_usize..12,
554 entries in proptest::collection::vec((0_usize..12, 0_usize..12, -40_i32..40, 0.5_f64..1.0), 1..60),
555 ) {
556 let t: Vec<_> = entries
557 .iter()
558 .filter(|e| e.0 < m && e.1 < n)
559 .map(|&(i, j, e, f)| (Row::from_usize(i), Col::from_usize(j), f * f64::from(e).exp2()))
560 .collect();
561 let a = CscMatrix::from_triplets(m, n, &t).unwrap();
562 for policy in POLICIES {
563 let s = Scaling::compute(&a, policy);
564 let mut b = a.clone();
565 s.apply(&mut b);
566 // Algorithm I makes every column's largest entry one.
567 if policy == Equilibration::InfinityNorm {
568 for j in 0..n {
569 let big = b.col(Col::from_usize(j)).1.iter().fold(0.0_f64, |m, x| m.max(x.abs()));
570 prop_assert!(is_exact_zero(big) || approx_eq(big, 1.0, 4.0 * f64::EPSILON));
571 }
572 }
573 s.unapply(&mut b);
574 if s.is_power_of_two() {
575 prop_assert_eq!(&a, &b);
576 }
577 }
578 }
579 }
580}