Skip to main content

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}