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;