Skip to main content

tensor4all_tensorbackend/
capped_full_piv_lu.rs

1//! Complete-pivoting LU of a square dense matrix that stops at a rank cap.
2//!
3//! The factorization is faer's complete-pivoting LU, run in place on the
4//! matrix's own column-major buffer with `Par::Seq`. A rank cap is handed to the
5//! elimination itself, so a rank-`r` answer costs `O(n^2 r)` instead of the
6//! `O(n^3)` of a full factorization truncated afterwards.
7//!
8//! Only the cap is handed to faer. Which pivots a caller accepts - absolute and
9//! relative tolerances, degenerate-pivot rules - is the caller's decision, made
10//! on the diagonal this module returns: faer's own tolerance rule rejects a
11//! pivot *at* the threshold and measures it against the first pivot, which is
12//! not the rule every caller wants.
13//!
14//! Two properties of the elimination callers can rely on:
15//!
16//! - Each pivot is the trailing block's entry of largest *score*. For real
17//!   scalars the score is `|x|`. For complex scalars it depends on the SIMD path
18//!   faer dispatches to at run time from CPU detection, and both are part of
19//!   this contract:
20//!   - vector path (x86-64 with the x86-64-v3 set - AVX2, FMA, ... - or
21//!     AVX-512; aarch64 NEON; wasm32 simd128): the *larger part*,
22//!     `max(|re|, |im|)`;
23//!   - scalar path (any other CPU): the *part sum*, `|re| + |im|`.
24//!
25//!   Both are within `sqrt(2)` of the modulus, so a pivot is never smaller than
26//!   `1/sqrt(2)` of the block's largest modulus, but they rank entries
27//!   differently: capped at two, `diag(10, 3, 2.5 + 2.5i)` takes `3` second
28//!   under the larger part and `2.5 + 2.5i` under the part sum. The pivot order
29//!   is therefore whatever this call returns, not a rule a caller re-derives
30//!   from the diagonal.
31//! - A zero or subnormal Schur complement stops the elimination before the cap
32//!   does, and the trailing diagonal is left un-eliminated. Whether
33//!   [`CappedFullPivLu::rank`] reports that earlier stop depends on the cap: see
34//!   there.
35
36use anyhow::anyhow;
37use faer::dyn_stack::{MemBuffer, MemStack};
38use faer::linalg::lu::full_pivoting::factor::{self as faer_flu, FullPivLuParams};
39use faer::{Auto, Par};
40use num_complex::{Complex32, Complex64};
41
42use crate::backend::BackendLinalgError;
43use crate::matrix::Matrix;
44
45mod sealed {
46    use super::{CappedFullPivLu, Matrix};
47
48    /// The in-place factorization each supported scalar provides.
49    pub trait Factor: Copy + Sized {
50        fn factor_in_place(a: Matrix<Self>, max_rank: Option<usize>) -> CappedFullPivLu<Self>;
51    }
52}
53
54/// Scalar types accepted by [`capped_full_piv_lu`]: `f32`, `f64`, `Complex32`
55/// and `Complex64`.
56///
57/// The trait is sealed; the factorization behind it is the backend's.
58///
59/// # Examples
60///
61/// ```
62/// use tensor4all_tensorbackend::{capped_full_piv_lu, CappedFullPivLuScalar, Matrix};
63///
64/// fn leading_pivot<T: CappedFullPivLuScalar>(a: Matrix<T>) -> Option<T> {
65///     capped_full_piv_lu(a, Some(1)).ok()?.diagonal().first().copied()
66/// }
67/// let a = Matrix::from_col_major_vec(2, 2, vec![1.0_f64, 0.0, 0.0, 5.0]);
68/// assert_eq!(leading_pivot(a), Some(5.0));
69/// ```
70pub trait CappedFullPivLuScalar: sealed::Factor {}
71
72/// The pivots a [`capped_full_piv_lu`] call took, and the diagonal it left.
73///
74/// Holds no factor matrices: the row and column permutations, the in-place
75/// diagonal, and the rank count [`Self::rank`] (whose meaning depends on the
76/// cap).
77///
78/// # Examples
79///
80/// ```
81/// use tensor4all_tensorbackend::{capped_full_piv_lu, Matrix};
82///
83/// let a = Matrix::from_col_major_vec(2, 2, vec![1.0_f64, 0.0, 0.0, 5.0]);
84/// let lu = capped_full_piv_lu(a, None)?;
85/// assert_eq!(lu.rank(), 2);
86/// assert_eq!(lu.row_perm(), &[1, 0]);
87/// assert_eq!(lu.col_perm(), &[1, 0]);
88/// assert_eq!(lu.diagonal(), &[5.0, 1.0]);
89/// # Ok::<(), Box<dyn std::error::Error>>(())
90/// ```
91#[derive(Debug, Clone)]
92pub struct CappedFullPivLu<T> {
93    row_perm: Vec<usize>,
94    col_perm: Vec<usize>,
95    diagonal: Vec<T>,
96    rank: usize,
97}
98
99impl<T> CappedFullPivLu<T> {
100    /// Row permutation: `row_perm()[k]` is the input row moved to position `k`.
101    ///
102    /// Has `n` entries: the rows of the pivots taken, in order, then the rows the
103    /// elimination did not pivot on. Under a cap with finite input the pivots
104    /// taken are the first [`Self::rank`] entries; without a cap `rank()` is `n`
105    /// even when the elimination stopped earlier (see [`Self::rank`]).
106    ///
107    /// # Examples
108    ///
109    /// ```
110    /// use tensor4all_tensorbackend::{capped_full_piv_lu, Matrix};
111    ///
112    /// let a = Matrix::from_col_major_vec(2, 2, vec![0.0_f64, 3.0, 1.0, 0.0]);
113    /// let lu = capped_full_piv_lu(a, Some(1))?;
114    /// assert_eq!(lu.row_perm()[0], 1);
115    /// # Ok::<(), Box<dyn std::error::Error>>(())
116    /// ```
117    pub fn row_perm(&self) -> &[usize] {
118        &self.row_perm
119    }
120
121    /// Column permutation: `col_perm()[k]` is the input column moved to position `k`.
122    ///
123    /// Has `n` entries: the columns of the pivots taken, in order, then the
124    /// columns the elimination did not pivot on. Which leading entries are pivots
125    /// is read as for [`Self::row_perm`].
126    ///
127    /// # Examples
128    ///
129    /// ```
130    /// use tensor4all_tensorbackend::{capped_full_piv_lu, Matrix};
131    ///
132    /// let a = Matrix::from_col_major_vec(2, 2, vec![0.0_f64, 3.0, 1.0, 0.0]);
133    /// let lu = capped_full_piv_lu(a, Some(1))?;
134    /// assert_eq!(lu.col_perm()[0], 0);
135    /// # Ok::<(), Box<dyn std::error::Error>>(())
136    /// ```
137    pub fn col_perm(&self) -> &[usize] {
138        &self.col_perm
139    }
140
141    /// The diagonal of the in-place factorization, `n` entries.
142    ///
143    /// The leading entries, up to where the elimination stopped, are the pivots
144    /// taken, in order. The rest are the trailing block's diagonal as the
145    /// elimination left it: the Schur complement's diagonal after a cap, the
146    /// un-eliminated block's diagonal (under the permutations) after a zero or
147    /// subnormal stop - which is zero or subnormal. Under a cap with finite input
148    /// the stop is at [`Self::rank`]; without a cap `rank()` does not report it,
149    /// and the first zero or subnormal entry here marks it.
150    ///
151    /// # Examples
152    ///
153    /// ```
154    /// use tensor4all_tensorbackend::{capped_full_piv_lu, Matrix};
155    ///
156    /// let a = Matrix::from_col_major_vec(2, 2, vec![2.0_f64, 0.0, 0.0, -7.0]);
157    /// let lu = capped_full_piv_lu(a, None)?;
158    /// assert_eq!(lu.diagonal(), &[-7.0, 2.0]);
159    /// # Ok::<(), Box<dyn std::error::Error>>(())
160    /// ```
161    pub fn diagonal(&self) -> &[T] {
162        &self.diagonal
163    }
164
165    /// The rank count the factorization reports; what it means depends on the
166    /// `max_rank` the call was given.
167    ///
168    /// - `Some(cap)`, finite input: the number of pivots the elimination took.
169    ///   That is `min(cap, n)` when the cap stops it, and fewer when a zero or
170    ///   subnormal Schur complement stops it first (`0` for a zero matrix).
171    /// - `Some(cap)`, a NaN or infinite entry: `min(cap, n)`, whether or not the
172    ///   elimination stopped earlier.
173    /// - `None`: always `n`, also for a singular matrix whose elimination
174    ///   stopped early (a zero matrix reports `n`). No rank is revealed.
175    ///
176    /// What a caller can decide from it: under a cap with finite input, a
177    /// value `r < min(cap, n)` means the elimination found the remaining
178    /// `(n - r) x (n - r)` Schur complement zero or subnormal, so the `r` pivots
179    /// taken already reproduce the input up to rounding; `r == min(cap, n)` says
180    /// nothing about what lies past the cap. Without a
181    /// cap, the count carries no information about the matrix: read
182    /// [`Self::diagonal`], or pass `Some(n)` to have the early stop reported.
183    ///
184    /// # Examples
185    ///
186    /// ```
187    /// use tensor4all_tensorbackend::{capped_full_piv_lu, Matrix};
188    ///
189    /// let a = Matrix::from_col_major_vec(3, 3, vec![
190    ///     4.0_f64, 0.0, 0.0,
191    ///     0.0, 2.0, 0.0,
192    ///     0.0, 0.0, 1.0,
193    /// ]);
194    /// assert_eq!(capped_full_piv_lu(a.clone(), None)?.rank(), 3);
195    /// assert_eq!(capped_full_piv_lu(a, Some(2))?.rank(), 2);
196    ///
197    /// // A rank-1 matrix: only a cap reports the early stop.
198    /// let singular = Matrix::from_col_major_vec(2, 2, vec![3.0_f64, 0.0, 0.0, 0.0]);
199    /// assert_eq!(capped_full_piv_lu(singular.clone(), None)?.rank(), 2);
200    /// assert_eq!(capped_full_piv_lu(singular, Some(2))?.rank(), 1);
201    /// # Ok::<(), Box<dyn std::error::Error>>(())
202    /// ```
203    pub fn rank(&self) -> usize {
204        self.rank
205    }
206}
207
208/// Complete-pivoting LU of a square matrix, stopped after at most `max_rank` pivots.
209///
210/// The elimination runs in place on `a`'s column-major buffer, sequentially.
211/// `None` factors to full rank; `Some(r)` stops once `r` pivots are taken, so
212/// the work is `O(n^2 r)`. Either stops earlier at a zero or subnormal Schur
213/// complement, but only `Some` reports that stop in [`CappedFullPivLu::rank`].
214/// Pivot acceptance (tolerances, degenerate pivots) is left to the caller, who
215/// reads it from [`CappedFullPivLu::diagonal`]. The complex pivot score depends
216/// on the dispatched SIMD path (see the module docs).
217///
218/// Non-finite entries are not checked here: validate the input first if a
219/// non-finite value must be refused.
220///
221/// # Errors
222///
223/// Returns [`BackendLinalgError`] when `a` is not square.
224///
225/// # Examples
226///
227/// ```
228/// use tensor4all_tensorbackend::{capped_full_piv_lu, Matrix};
229///
230/// // diag(1, 4, 2): complete pivoting takes 4, then 2, then 1.
231/// let a = Matrix::from_col_major_vec(3, 3, vec![
232///     1.0_f64, 0.0, 0.0,
233///     0.0, 4.0, 0.0,
234///     0.0, 0.0, 2.0,
235/// ]);
236/// let lu = capped_full_piv_lu(a, Some(2))?;
237/// assert_eq!(lu.rank(), 2);
238/// assert_eq!(&lu.row_perm()[..2], &[1, 2]);
239/// assert_eq!(&lu.col_perm()[..2], &[1, 2]);
240/// assert_eq!(&lu.diagonal()[..2], &[4.0, 2.0]);
241/// // The trailing entry is the remaining Schur complement.
242/// assert_eq!(lu.diagonal()[2], 1.0);
243/// # Ok::<(), Box<dyn std::error::Error>>(())
244/// ```
245pub fn capped_full_piv_lu<T: CappedFullPivLuScalar>(
246    a: Matrix<T>,
247    max_rank: Option<usize>,
248) -> Result<CappedFullPivLu<T>, BackendLinalgError> {
249    if a.nrows() != a.ncols() {
250        return Err(anyhow!(
251            "capped_full_piv_lu needs a square matrix, got {}x{}",
252            a.nrows(),
253            a.ncols()
254        )
255        .into());
256    }
257    Ok(T::factor_in_place(a, max_rank))
258}
259
260fn factor_with_faer<T>(mut a: Matrix<T>, max_rank: Option<usize>) -> CappedFullPivLu<T>
261where
262    T: faer::traits::ComplexField + Copy,
263{
264    let n = a.nrows();
265    if n == 0 {
266        return CappedFullPivLu {
267            row_perm: Vec::new(),
268            col_perm: Vec::new(),
269            diagonal: Vec::new(),
270            rank: 0,
271        };
272    }
273    let params = FullPivLuParams {
274        max_rank,
275        ..<FullPivLuParams as Auto<T>>::auto()
276    };
277    let (mut row_perm, mut row_perm_inv) = (vec![0usize; n], vec![0usize; n]);
278    let (mut col_perm, mut col_perm_inv) = (vec![0usize; n], vec![0usize; n]);
279    let mut scratch = MemBuffer::new(faer_flu::lu_in_place_scratch::<usize, T>(
280        n,
281        n,
282        Par::Seq.shape(),
283        params.into(),
284    ));
285    let buffer = a.as_col_major_mut_slice();
286    let (info, _, _) = faer_flu::lu_in_place(
287        faer::MatMut::from_column_major_slice_mut(buffer, n, n),
288        &mut row_perm,
289        &mut row_perm_inv,
290        &mut col_perm,
291        &mut col_perm_inv,
292        Par::Seq,
293        MemStack::new(&mut scratch),
294        params.into(),
295    );
296    let diagonal = (0..n).map(|i| buffer[i + n * i]).collect();
297    CappedFullPivLu {
298        row_perm,
299        col_perm,
300        diagonal,
301        rank: info.rank.min(n),
302    }
303}
304
305macro_rules! impl_capped_full_piv_lu_scalar {
306    ($($t:ty),*) => {$(
307        impl sealed::Factor for $t {
308            fn factor_in_place(a: Matrix<Self>, max_rank: Option<usize>) -> CappedFullPivLu<Self> {
309                factor_with_faer(a, max_rank)
310            }
311        }
312        impl CappedFullPivLuScalar for $t {}
313    )*};
314}
315
316impl_capped_full_piv_lu_scalar!(f32, f64, Complex32, Complex64);
317
318#[cfg(test)]
319mod tests;