Skip to main content

tensor4all_core/
matrixlu.rs

1//! Rank-Revealing LU decomposition (rrLU) implementation.
2//!
3//! Provides [`RrLU`], a full-pivoting LU decomposition that reveals the
4//! numerical rank of a matrix. The decomposition is:
5//!
6//! ```text
7//! P_row * A * P_col = L * U
8//! ```
9//!
10//! where `P_row`, `P_col` are permutation matrices. The rank is determined
11//! by the number of pivots exceeding the tolerance thresholds in
12//! [`RrLUOptions`].
13//!
14//! # Examples
15//!
16//! ```
17//! use tensor4all_core::matrixlu::rrlu;
18//! use tensor4all_tensorbackend::from_vec2d;
19//!
20//! let m = from_vec2d(vec![
21//!     vec![1.0_f64, 2.0],
22//!     vec![3.0, 4.0],
23//! ]);
24//! let lu = rrlu(&m, None).unwrap();
25//! assert_eq!(lu.npivots(), 2);
26//! ```
27
28use crate::error::{MatrixCIError, Result};
29use crate::scalar::Scalar;
30use tensor4all_tensorbackend::{transpose, Matrix};
31
32/// Rank-Revealing LU decomposition.
33///
34/// Represents a matrix `A` as `P_row * A * P_col = L * U`, where `P_row`
35/// and `P_col` are permutation matrices, `L` is lower-triangular, and `U`
36/// is upper-triangular. One of `L` or `U` has unit diagonal, controlled by
37/// the `left_orthogonal` option.
38///
39/// # Examples
40///
41/// ```
42/// use tensor4all_core::matrixlu::rrlu;
43/// use tensor4all_tensorbackend::{from_vec2d, mat_mul};
44///
45/// let m = from_vec2d(vec![
46///     vec![1.0_f64, 2.0, 3.0],
47///     vec![4.0, 5.0, 6.0],
48///     vec![7.0, 8.0, 10.0],
49/// ]);
50///
51/// let lu = rrlu(&m, None).unwrap();
52/// assert_eq!(lu.npivots(), 3);
53///
54/// // Verify L * U reconstructs the permuted matrix
55/// let l = lu.left(false);
56/// let u = lu.right(false);
57/// let reconstructed = mat_mul(&l, &u).unwrap();
58///
59/// // Check reconstruction matches the permuted matrix
60/// for i in 0..3 {
61///     for j in 0..3 {
62///         let orig_row = lu.row_permutation()[i];
63///         let orig_col = lu.col_permutation()[j];
64///         assert!((reconstructed[[i, j]] - m[[orig_row, orig_col]]).abs() < 1e-10);
65///     }
66/// }
67/// ```
68#[derive(Debug, Clone)]
69pub struct RrLU<T: Scalar> {
70    /// Row permutation
71    row_permutation: Vec<usize>,
72    /// Column permutation
73    col_permutation: Vec<usize>,
74    /// Lower triangular matrix L
75    l: Matrix<T>,
76    /// Upper triangular matrix U
77    u: Matrix<T>,
78    /// Whether L is left-orthogonal (L has 1s on diagonal) or U is (U has 1s on diagonal)
79    left_orthogonal: bool,
80    /// Number of pivots
81    n_pivot: usize,
82    /// Last pivot error
83    error: f64,
84}
85
86impl<T: Scalar> RrLU<T> {
87    /// Create an empty rrLU for a matrix of given size.
88    ///
89    /// Used internally. Most users should call [`rrlu`] or [`rrlu_mut`]
90    /// instead.
91    ///
92    /// # Examples
93    ///
94    /// ```
95    /// use tensor4all_core::RrLU;
96    ///
97    /// let lu = RrLU::<f64>::new(3, 4, true);
98    /// assert_eq!(lu.nrows(), 3);
99    /// assert_eq!(lu.ncols(), 4);
100    /// assert_eq!(lu.npivots(), 0);
101    /// assert!(lu.is_left_orthogonal());
102    /// ```
103    pub fn new(nr: usize, nc: usize, left_orthogonal: bool) -> Self {
104        Self {
105            row_permutation: (0..nr).collect(),
106            col_permutation: (0..nc).collect(),
107            l: Matrix::zeros(nr, 0),
108            u: Matrix::zeros(0, nc),
109            left_orthogonal,
110            n_pivot: 0,
111            error: f64::NAN,
112        }
113    }
114
115    /// Number of rows
116    ///
117    /// # Examples
118    ///
119    /// ```
120    /// use tensor4all_core::matrixlu::rrlu;
121    /// use tensor4all_tensorbackend::from_vec2d;
122    ///
123    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0], vec![5.0, 6.0]]);
124    /// let lu = rrlu(&m, None).unwrap();
125    /// assert_eq!(lu.nrows(), 3);
126    /// ```
127    pub fn nrows(&self) -> usize {
128        self.l.nrows()
129    }
130
131    /// Number of columns
132    ///
133    /// # Examples
134    ///
135    /// ```
136    /// use tensor4all_core::matrixlu::rrlu;
137    /// use tensor4all_tensorbackend::from_vec2d;
138    ///
139    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0, 3.0], vec![4.0, 5.0, 6.0]]);
140    /// let lu = rrlu(&m, None).unwrap();
141    /// assert_eq!(lu.ncols(), 3);
142    /// ```
143    pub fn ncols(&self) -> usize {
144        self.u.ncols()
145    }
146
147    /// Number of pivots
148    ///
149    /// # Examples
150    ///
151    /// ```
152    /// use tensor4all_core::matrixlu::rrlu;
153    /// use tensor4all_tensorbackend::from_vec2d;
154    ///
155    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
156    /// let lu = rrlu(&m, None).unwrap();
157    /// assert_eq!(lu.npivots(), 2);
158    /// ```
159    pub fn npivots(&self) -> usize {
160        self.n_pivot
161    }
162
163    /// Row permutation
164    ///
165    /// # Examples
166    ///
167    /// ```
168    /// use tensor4all_core::matrixlu::rrlu;
169    /// use tensor4all_tensorbackend::from_vec2d;
170    ///
171    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
172    /// let lu = rrlu(&m, None).unwrap();
173    /// let perm = lu.row_permutation();
174    /// assert_eq!(perm.len(), 2);
175    /// // Permutation is a rearrangement of 0..nrows
176    /// let mut sorted = perm.to_vec();
177    /// sorted.sort();
178    /// assert_eq!(sorted, vec![0, 1]);
179    /// ```
180    pub fn row_permutation(&self) -> &[usize] {
181        &self.row_permutation
182    }
183
184    /// Column permutation
185    ///
186    /// # Examples
187    ///
188    /// ```
189    /// use tensor4all_core::matrixlu::rrlu;
190    /// use tensor4all_tensorbackend::from_vec2d;
191    ///
192    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
193    /// let lu = rrlu(&m, None).unwrap();
194    /// let perm = lu.col_permutation();
195    /// assert_eq!(perm.len(), 2);
196    /// let mut sorted = perm.to_vec();
197    /// sorted.sort();
198    /// assert_eq!(sorted, vec![0, 1]);
199    /// ```
200    pub fn col_permutation(&self) -> &[usize] {
201        &self.col_permutation
202    }
203
204    /// Get row indices (selected pivots)
205    ///
206    /// # Examples
207    ///
208    /// ```
209    /// use tensor4all_core::{matrixlu::rrlu, RrLUOptions};
210    /// use tensor4all_tensorbackend::from_vec2d;
211    ///
212    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
213    /// let lu = rrlu(&m, Some(RrLUOptions { max_bond_dim: 1, ..Default::default() })).unwrap();
214    /// let rows = lu.row_indices();
215    /// assert_eq!(rows.len(), 1);
216    /// assert!(rows[0] < 2);
217    /// ```
218    pub fn row_indices(&self) -> Vec<usize> {
219        self.row_permutation[0..self.n_pivot].to_vec()
220    }
221
222    /// Get column indices (selected pivots)
223    ///
224    /// # Examples
225    ///
226    /// ```
227    /// use tensor4all_core::{matrixlu::rrlu, RrLUOptions};
228    /// use tensor4all_tensorbackend::from_vec2d;
229    ///
230    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
231    /// let lu = rrlu(&m, Some(RrLUOptions { max_bond_dim: 1, ..Default::default() })).unwrap();
232    /// let cols = lu.col_indices();
233    /// assert_eq!(cols.len(), 1);
234    /// assert!(cols[0] < 2);
235    /// ```
236    pub fn col_indices(&self) -> Vec<usize> {
237        self.col_permutation[0..self.n_pivot].to_vec()
238    }
239
240    /// Get left matrix (optionally permuted)
241    ///
242    /// # Examples
243    ///
244    /// ```
245    /// use tensor4all_core::matrixlu::rrlu;
246    /// use tensor4all_tensorbackend::{from_vec2d, mat_mul};
247    ///
248    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
249    /// let lu = rrlu(&m, None).unwrap();
250    ///
251    /// // Unpermuted: L * U reconstructs the row/col-permuted matrix
252    /// let l = lu.left(false);
253    /// let u = lu.right(false);
254    /// let prod = mat_mul(&l, &u).unwrap();
255    /// for i in 0..2 {
256    ///     for j in 0..2 {
257    ///         let ri = lu.row_permutation()[i];
258    ///         let cj = lu.col_permutation()[j];
259    ///         assert!((prod[[i, j]] - m[[ri, cj]]).abs() < 1e-10);
260    ///     }
261    /// }
262    /// ```
263    pub fn left(&self, permute: bool) -> Matrix<T> {
264        if permute {
265            let mut result = Matrix::zeros(self.l.nrows(), self.l.ncols());
266            for j in 0..self.l.ncols() {
267                for (new_i, &old_i) in self.row_permutation.iter().enumerate() {
268                    result[[old_i, j]] = self.l[[new_i, j]];
269                }
270            }
271            result
272        } else {
273            self.l.clone()
274        }
275    }
276
277    /// Get right matrix (optionally permuted)
278    ///
279    /// # Examples
280    ///
281    /// ```
282    /// use tensor4all_core::matrixlu::rrlu;
283    /// use tensor4all_tensorbackend::{from_vec2d, mat_mul};
284    ///
285    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
286    /// let lu = rrlu(&m, None).unwrap();
287    /// let l = lu.left(false);
288    /// let u = lu.right(false);
289    /// assert_eq!(u.nrows(), lu.npivots());
290    /// assert_eq!(u.ncols(), lu.ncols());
291    /// // L * U reconstructs the permuted matrix
292    /// let prod = mat_mul(&l, &u).unwrap();
293    /// assert!((prod[[0, 0]] - m[[lu.row_permutation()[0], lu.col_permutation()[0]]]).abs() < 1e-10);
294    /// ```
295    pub fn right(&self, permute: bool) -> Matrix<T> {
296        if permute {
297            let mut result = Matrix::zeros(self.u.nrows(), self.u.ncols());
298            for (new_j, &old_j) in self.col_permutation.iter().enumerate() {
299                for i in 0..self.u.nrows() {
300                    result[[i, old_j]] = self.u[[i, new_j]];
301                }
302            }
303            result
304        } else {
305            self.u.clone()
306        }
307    }
308
309    /// Keep only the first `rank` pivots of the decomposition.
310    ///
311    /// Full pivoting fixes the first `rank` columns of `L` and rows of `U`
312    /// once their pivots are chosen: later steps only swap their trailing
313    /// rows or columns. The result is therefore the decomposition a search
314    /// stopped by `max_bond_dim = rank` would return, and the residual
315    /// diagnostic becomes the magnitude of the next pivot, which full pivoting
316    /// chose as the largest entry of that Schur complement. A `rank` of at
317    /// least [`npivots`](Self::npivots) leaves the decomposition unchanged.
318    pub(crate) fn truncate(&mut self, rank: usize) {
319        if rank >= self.n_pivot {
320            return;
321        }
322        self.error = self.diag()[rank].abs_val();
323        let nrows = self.l.nrows();
324        let l = self.l.as_col_major_slice()[..nrows * rank].to_vec();
325        self.l = Matrix::from_col_major_vec(nrows, rank, l);
326        let ncols = self.u.ncols();
327        let mut u = Vec::with_capacity(rank * ncols);
328        for col in 0..ncols {
329            u.extend((0..rank).map(|row| self.u[[row, col]]));
330        }
331        self.u = Matrix::from_col_major_vec(rank, ncols, u);
332        self.n_pivot = rank;
333    }
334
335    pub(crate) fn left_unpermuted(&self) -> &Matrix<T> {
336        &self.l
337    }
338
339    pub(crate) fn right_unpermuted(&self) -> &Matrix<T> {
340        &self.u
341    }
342
343    /// Get diagonal elements
344    ///
345    /// # Examples
346    ///
347    /// ```
348    /// use tensor4all_core::matrixlu::rrlu;
349    /// use tensor4all_tensorbackend::from_vec2d;
350    ///
351    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
352    /// let lu = rrlu(&m, None).unwrap();
353    /// let d = lu.diag();
354    /// assert_eq!(d.len(), lu.npivots());
355    /// // Diagonal elements are non-zero for full-rank matrices
356    /// for &val in &d {
357    ///     assert!(val.abs() > 1e-14);
358    /// }
359    /// ```
360    pub fn diag(&self) -> Vec<T> {
361        let n = self.n_pivot;
362        if self.left_orthogonal {
363            (0..n).map(|i| self.u[[i, i]]).collect()
364        } else {
365            (0..n).map(|i| self.l[[i, i]]).collect()
366        }
367    }
368
369    /// Get pivot errors
370    ///
371    /// # Examples
372    ///
373    /// ```
374    /// use tensor4all_core::matrixlu::rrlu;
375    /// use tensor4all_tensorbackend::from_vec2d;
376    ///
377    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
378    /// let lu = rrlu(&m, None).unwrap();
379    /// let errs = lu.pivot_errors();
380    /// // One entry per pivot plus the final residual
381    /// assert_eq!(errs.len(), lu.npivots() + 1);
382    /// // Errors are non-negative
383    /// for &e in &errs {
384    ///     assert!(e >= 0.0);
385    /// }
386    /// ```
387    pub fn pivot_errors(&self) -> Vec<f64> {
388        let mut errors: Vec<f64> = self.diag().iter().map(|d| d.abs_val()).collect();
389        errors.push(self.error);
390        errors
391    }
392
393    /// Get last pivot error
394    ///
395    /// # Examples
396    ///
397    /// ```
398    /// use tensor4all_core::matrixlu::rrlu;
399    /// use tensor4all_tensorbackend::from_vec2d;
400    ///
401    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
402    /// let lu = rrlu(&m, None).unwrap();
403    /// // Full-rank decomposition has zero residual
404    /// assert_eq!(lu.last_pivot_error(), 0.0);
405    /// ```
406    pub fn last_pivot_error(&self) -> f64 {
407        self.error
408    }
409
410    /// Transpose the decomposition
411    ///
412    /// # Examples
413    ///
414    /// ```
415    /// use tensor4all_core::matrixlu::rrlu;
416    /// use tensor4all_tensorbackend::from_vec2d;
417    ///
418    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
419    /// let lu = rrlu(&m, None).unwrap();
420    /// let lu_t = lu.transpose();
421    /// assert_eq!(lu_t.nrows(), lu.ncols());
422    /// assert_eq!(lu_t.ncols(), lu.nrows());
423    /// assert_eq!(lu_t.npivots(), lu.npivots());
424    /// assert_eq!(lu_t.is_left_orthogonal(), !lu.is_left_orthogonal());
425    /// ```
426    pub fn transpose(&self) -> RrLU<T> {
427        RrLU {
428            row_permutation: self.col_permutation.clone(),
429            col_permutation: self.row_permutation.clone(),
430            l: transpose(&self.u),
431            u: transpose(&self.l),
432            left_orthogonal: !self.left_orthogonal,
433            n_pivot: self.n_pivot,
434            error: self.error,
435        }
436    }
437
438    /// Check if left-orthogonal (L has 1s on diagonal)
439    ///
440    /// # Examples
441    ///
442    /// ```
443    /// use tensor4all_core::{matrixlu::rrlu, RrLUOptions};
444    /// use tensor4all_tensorbackend::from_vec2d;
445    ///
446    /// let m = from_vec2d(vec![vec![1.0_f64, 2.0], vec![3.0, 4.0]]);
447    ///
448    /// let lu = rrlu(&m, None).unwrap();
449    /// assert!(lu.is_left_orthogonal()); // default
450    ///
451    /// let lu2 = rrlu(&m, Some(RrLUOptions {
452    ///     left_orthogonal: false, ..Default::default()
453    /// })).unwrap();
454    /// assert!(!lu2.is_left_orthogonal());
455    /// ```
456    pub fn is_left_orthogonal(&self) -> bool {
457        self.left_orthogonal
458    }
459}
460
461pub(crate) fn validate_col_major_matrix_len(
462    nrows: usize,
463    ncols: usize,
464    actual_len: usize,
465) -> crate::Result<()> {
466    let expected = nrows
467        .checked_mul(ncols)
468        .ok_or_else(|| MatrixCIError::InvalidArgument {
469            message: format!("matrix shape {nrows} x {ncols} overflows usize"),
470        })?;
471    if actual_len != expected {
472        return Err(MatrixCIError::InvalidArgument {
473            message: format!(
474                "column-major matrix length mismatch: expected {expected}, got {actual_len}"
475            ),
476        });
477    }
478    Ok(())
479}
480
481/// Validate [`RrLUOptions`] before a factorization.
482///
483/// Negative or non-finite tolerances return [`MatrixCIError::InvalidArgument`].
484/// Shared by the dense, lazy, and selection-only entry points.
485pub(crate) fn validate_luci_options(options: &RrLUOptions) -> Result<()> {
486    for (name, value) in [("rel_tol", options.rel_tol), ("abs_tol", options.abs_tol)] {
487        if !value.is_finite() || value < 0.0 {
488            return Err(MatrixCIError::InvalidArgument {
489                message: format!("{name} must be finite and nonnegative"),
490            });
491        }
492    }
493    Ok(())
494}
495
496/// Whether `|value|` is finite, decided without a `hypot` per entry.
497///
498/// `abs_sq` is a multiply-add. When it is finite, so is `|value|`. Only a
499/// non-finite `abs_sq` (NaN, infinity, or a square that overflows) falls back
500/// to the exact `abs_val` test, so the decision equals `abs_val().is_finite()`
501/// for every input.
502#[inline]
503fn magnitude_is_finite<T: Scalar>(value: T) -> bool {
504    value.abs_sq().is_finite() || value.abs_val().is_finite()
505}
506
507/// Whether every entry of `data` has a finite magnitude (one pass).
508fn all_magnitudes_finite<T: Scalar>(data: &[T]) -> bool {
509    data.iter().all(|&value| magnitude_is_finite(value))
510}
511
512/// Validate the entries of a column-major matrix before a factorization.
513///
514/// NaN input returns [`MatrixCIError::NaNEncountered`]; infinite input
515/// magnitudes return [`MatrixCIError::InvalidArgument`]. An accepted matrix
516/// costs one pass; a rejected one a second pass to tell NaN from infinity.
517pub(crate) fn validate_luci_matrix<T: Scalar>(a: &Matrix<T>) -> Result<()> {
518    let data = a.as_col_major_slice();
519    if all_magnitudes_finite(data) {
520        return Ok(());
521    }
522    if data.iter().any(|&value| value.is_nan()) {
523        return Err(MatrixCIError::NaNEncountered {
524            matrix: "input".into(),
525        });
526    }
527    Err(MatrixCIError::InvalidArgument {
528        message: "input matrix magnitudes must be finite".into(),
529    })
530}
531
532/// Validate a column-major matrix and its [`RrLUOptions`] before a factorization.
533///
534/// Shared by the full-factor and selection-only entry points so both reject the
535/// same inputs with the same error: negative or non-finite tolerances and
536/// infinite input magnitudes return [`MatrixCIError::InvalidArgument`]; NaN
537/// input returns [`MatrixCIError::NaNEncountered`].
538pub(crate) fn validate_owned_luci_input<T: Scalar>(
539    a: &Matrix<T>,
540    options: &RrLUOptions,
541) -> Result<()> {
542    validate_luci_options(options)?;
543    validate_luci_matrix(a)
544}
545
546#[inline]
547fn col_major_offset(nrows: usize, row: usize, col: usize) -> usize {
548    row + nrows * col
549}
550
551#[inline]
552fn col_major_get<T: Copy>(data: &[T], nrows: usize, row: usize, col: usize) -> T {
553    let offset = col_major_offset(nrows, row, col);
554    debug_assert!(row < nrows);
555    debug_assert!(offset < data.len());
556    // SAFETY: callers pass matrix-derived dimensions and prechecked ranges.
557    unsafe { *data.get_unchecked(offset) }
558}
559
560#[inline]
561fn col_major_set<T>(data: &mut [T], nrows: usize, row: usize, col: usize, value: T) {
562    let offset = col_major_offset(nrows, row, col);
563    debug_assert!(row < nrows);
564    debug_assert!(offset < data.len());
565    // SAFETY: callers pass matrix-derived dimensions and prechecked ranges.
566    unsafe {
567        *data.get_unchecked_mut(offset) = value;
568    }
569}
570
571fn submatrix_argmax_col_major<T: Scalar>(
572    data: &[T],
573    nrows: usize,
574    ncols: usize,
575    row_start: usize,
576    row_end: usize,
577    col_start: usize,
578    col_end: usize,
579) -> (usize, usize, T) {
580    debug_assert!(row_start < row_end);
581    debug_assert!(col_start < col_end);
582    debug_assert!(row_end <= nrows);
583    debug_assert!(col_end <= ncols);
584    debug_assert_eq!(data.len(), nrows * ncols);
585
586    let first = col_major_get(data, nrows, row_start, col_start);
587    let mut max_val = first.abs_sq();
588    let mut max_row = row_start;
589    let mut max_col = col_start;
590
591    for col in col_start..col_end {
592        let col_start_offset = col_major_offset(nrows, row_start, col);
593        for (offset, row) in (col_start_offset..).zip(row_start..row_end) {
594            // SAFETY: row and column loops stay within the prechecked region.
595            let value = unsafe { *data.get_unchecked(offset) };
596            let value_abs = value.abs_sq();
597            if value_abs > max_val {
598                max_val = value_abs;
599                max_row = row;
600                max_col = col;
601            }
602        }
603    }
604
605    // Preserve the normal-scale squared-magnitude fast path and its tie order.
606    // Outside the component type's normal range, compare robust magnitudes.
607    if !max_val.is_finite() || max_val < T::min_positive() {
608        let mut max_abs = first.abs_val();
609        max_row = row_start;
610        max_col = col_start;
611        for col in col_start..col_end {
612            let start = col_major_offset(nrows, row_start, col);
613            for (&value, row) in data[start..start + row_end - row_start]
614                .iter()
615                .zip(row_start..row_end)
616            {
617                let magnitude = value.abs_val();
618                if magnitude > max_abs {
619                    max_abs = magnitude;
620                    max_row = row;
621                    max_col = col;
622                }
623            }
624        }
625    }
626
627    (
628        max_row,
629        max_col,
630        col_major_get(data, nrows, max_row, max_col),
631    )
632}
633
634fn swap_rows_col_major<T>(data: &mut [T], nrows: usize, ncols: usize, row_a: usize, row_b: usize) {
635    debug_assert!(row_a < nrows);
636    debug_assert!(row_b < nrows);
637    debug_assert_eq!(data.len(), nrows * ncols);
638    if row_a == row_b {
639        return;
640    }
641
642    let ptr = data.as_mut_ptr();
643    for col in 0..ncols {
644        let offset_a = col_major_offset(nrows, row_a, col);
645        let offset_b = col_major_offset(nrows, row_b, col);
646        // SAFETY: row_a/row_b are in range, and each column offset is within
647        // the matrix-sized backing slice.
648        unsafe {
649            std::ptr::swap(ptr.add(offset_a), ptr.add(offset_b));
650        }
651    }
652}
653
654fn swap_cols_col_major<T>(data: &mut [T], nrows: usize, ncols: usize, col_a: usize, col_b: usize) {
655    debug_assert!(col_a < ncols);
656    debug_assert!(col_b < ncols);
657    debug_assert_eq!(data.len(), nrows * ncols);
658    if col_a == col_b || nrows == 0 {
659        return;
660    }
661
662    let start_a = col_major_offset(nrows, 0, col_a);
663    let start_b = col_major_offset(nrows, 0, col_b);
664    // SAFETY: distinct columns are non-overlapping contiguous ranges of
665    // length nrows in column-major storage.
666    unsafe {
667        std::ptr::swap_nonoverlapping(
668            data.as_mut_ptr().add(start_a),
669            data.as_mut_ptr().add(start_b),
670            nrows,
671        );
672    }
673}
674
675/// Select division once per pivot, preserving ordinary-scale arithmetic.
676/// Reciprocal multiplication avoids squaring an extreme complex divisor.
677enum PivotDivisor<T> {
678    Direct(T),
679    Reciprocal(T),
680}
681
682impl<T: Scalar> PivotDivisor<T> {
683    fn new(pivot: T) -> Self {
684        let squared = pivot.abs_sq();
685        if squared >= T::min_positive() && squared.is_finite() {
686            Self::Direct(pivot)
687        } else {
688            let inverse = T::from_f64(1.0 / pivot.abs_val());
689            Self::Reciprocal((pivot * inverse).conj() * inverse)
690        }
691    }
692}
693
694/// Stop only for an exact zero or an unrepresentable reciprocal in T.
695pub(crate) fn pivot_is_undividable<T: Scalar>(magnitude: f64) -> bool {
696    magnitude == 0.0
697        || (magnitude.is_finite() && !T::from_f64(1.0 / magnitude).abs_val().is_finite())
698}
699
700fn scale_column_by<T: Scalar, F: Fn(T) -> T>(
701    data: &mut [T],
702    nrows: usize,
703    col: usize,
704    row_start: usize,
705    divide: F,
706) {
707    let start = col_major_offset(nrows, row_start, col);
708    for value in &mut data[start..nrows * (col + 1)] {
709        *value = divide(*value);
710    }
711}
712
713fn scale_column_tail<T: Scalar>(
714    data: &mut [T],
715    nrows: usize,
716    col: usize,
717    row_start: usize,
718    pivot: T,
719) {
720    if row_start >= nrows {
721        return;
722    }
723    match PivotDivisor::new(pivot) {
724        PivotDivisor::Direct(p) => scale_column_by(data, nrows, col, row_start, |v| v / p),
725        PivotDivisor::Reciprocal(p) => scale_column_by(data, nrows, col, row_start, |v| v * p),
726    }
727}
728
729fn scale_row_by<T: Scalar, F: Fn(T) -> T>(
730    data: &mut [T],
731    nrows: usize,
732    ncols: usize,
733    row: usize,
734    col_start: usize,
735    divide: F,
736) {
737    for col in col_start..ncols {
738        let value = divide(col_major_get(data, nrows, row, col));
739        col_major_set(data, nrows, row, col, value);
740    }
741}
742
743fn scale_row_tail<T: Scalar>(
744    data: &mut [T],
745    nrows: usize,
746    ncols: usize,
747    row: usize,
748    col_start: usize,
749    pivot: T,
750) {
751    match PivotDivisor::new(pivot) {
752        PivotDivisor::Direct(p) => scale_row_by(data, nrows, ncols, row, col_start, |v| v / p),
753        PivotDivisor::Reciprocal(p) => scale_row_by(data, nrows, ncols, row, col_start, |v| v * p),
754    }
755}
756
757/// Lanes of the fused update-and-argmax loop; eight `f64` fill one AVX-512
758/// register or two AVX2 registers.
759const ARGMAX_LANES: usize = 8;
760
761/// Apply the rank-1 update of pivot step `pivot` to the trailing block and return
762/// the argmax of the updated block, as [`submatrix_argmax_col_major`] would find it
763/// on rows and columns `pivot + 1..`.
764///
765/// One pass over the block instead of an update pass followed by an argmax pass:
766/// the block is usually larger than the caches, so both passes were bound by memory
767/// traffic. Each column's largest squared magnitude is reduced over independent
768/// lanes (vectorizable), then the first column whose maximum strictly exceeds the
769/// running maximum wins, and its first row holding that value is returned. That is
770/// exactly the column-major first strict maximum of the sequential scan, so the
771/// selected pivot, and every result downstream, is bitwise unchanged.
772///
773/// Returns `None` when the trailing block is empty, or when its largest squared
774/// magnitude is non-finite or below the normal range: the caller then runs
775/// [`submatrix_argmax_col_major`], whose robust-magnitude path owns those cases.
776fn update_trailing_submatrix_with_argmax<T: Scalar>(
777    data: &mut [T],
778    nrows: usize,
779    ncols: usize,
780    pivot: usize,
781) -> Option<(usize, usize, T)> {
782    let tail_start = pivot + 1;
783    if tail_start >= nrows || tail_start >= ncols {
784        return None;
785    }
786
787    // Columns 0..=pivot stay untouched; the pivot column's tail is the update's `x`.
788    let (head, trailing) = data.split_at_mut(tail_start * nrows);
789    let x = &head[pivot * nrows + tail_start..];
790    let mut columns = trailing.chunks_exact_mut(nrows);
791
792    // The sequential scan starts from the block's first entry, so a NaN there
793    // stays the maximum (nothing compares greater) and the fallback takes over.
794    let first = columns.next()?;
795    let first_max = update_column_tail(first, x, pivot, tail_start);
796    let (max_col, max_val) = columns.enumerate().fold(
797        (0, strict_max(first[tail_start].abs_sq(), first_max)),
798        |(best_col, best), (col, column)| {
799            let col_max = update_column_tail(column, x, pivot, tail_start);
800            if col_max > best {
801                (col + 1, col_max)
802            } else {
803                (best_col, best)
804            }
805        },
806    );
807
808    if !max_val.is_finite() || max_val < T::min_positive() {
809        return None;
810    }
811    let max_col = tail_start + max_col;
812    let column = &data[max_col * nrows..(max_col + 1) * nrows];
813    let max_row = tail_start
814        + column[tail_start..]
815            .iter()
816            .position(|value| value.abs_sq() == max_val)?;
817    Some((max_row, max_col, column[max_row]))
818}
819
820/// `column[tail_start..] -= x * column[pivot]`, returning the largest squared
821/// magnitude written (`-inf` for an empty tail; NaNs never win).
822///
823/// The maximum is reduced over [`ARGMAX_LANES`] independent lanes so the loop
824/// vectorizes; a maximum does not depend on the reduction order.
825fn update_column_tail<T: Scalar>(
826    column: &mut [T],
827    x: &[T],
828    pivot: usize,
829    tail_start: usize,
830) -> f64 {
831    let y = column[pivot];
832    let target = &mut column[tail_start..];
833    let mut lanes = [f64::NEG_INFINITY; ARGMAX_LANES];
834    let (target_chunks, target_rest) = target.as_chunks_mut::<ARGMAX_LANES>();
835    let (x_chunks, x_rest) = x.as_chunks::<ARGMAX_LANES>();
836    for (target, x) in target_chunks.iter_mut().zip(x_chunks) {
837        for ((lane, t), &x) in lanes.iter_mut().zip(target).zip(x) {
838            *t = *t - x * y;
839            *lane = strict_max(*lane, t.abs_sq());
840        }
841    }
842    let remainder = target_rest
843        .iter_mut()
844        .zip(x_rest)
845        .fold(f64::NEG_INFINITY, |max, (t, &x)| {
846            *t = *t - x * y;
847            strict_max(max, t.abs_sq())
848        });
849    lanes.into_iter().fold(remainder, strict_max)
850}
851
852/// `candidate` if it is strictly greater than `current`, else `current`: the
853/// comparison of the sequential argmax scan (a NaN candidate never wins).
854#[inline]
855fn strict_max(current: f64, candidate: f64) -> f64 {
856    if candidate > current {
857        candidate
858    } else {
859        current
860    }
861}
862
863fn extract_l_from_factorized<T: Scalar>(
864    data: &[T],
865    nrows: usize,
866    rank: usize,
867    left_orthogonal: bool,
868) -> Result<Matrix<T>> {
869    debug_assert!(rank <= nrows);
870
871    let mut l_data = vec![T::zero(); nrows * rank];
872    for col in 0..rank {
873        let src_start = col_major_offset(nrows, col, col);
874        let src_end = col_major_offset(nrows, nrows - 1, col) + 1;
875        let dst_start = col_major_offset(nrows, col, col);
876        l_data[dst_start..dst_start + (nrows - col)].copy_from_slice(&data[src_start..src_end]);
877    }
878
879    if left_orthogonal {
880        for i in 0..rank {
881            l_data[col_major_offset(nrows, i, i)] = T::one();
882        }
883    }
884
885    if !all_magnitudes_finite(&l_data) {
886        return Err(MatrixCIError::NaNEncountered {
887            matrix: "L".to_string(),
888        });
889    }
890
891    Ok(Matrix::from_col_major_vec(nrows, rank, l_data))
892}
893
894fn extract_u_from_factorized<T: Scalar>(
895    data: &[T],
896    nrows: usize,
897    ncols: usize,
898    rank: usize,
899    left_orthogonal: bool,
900) -> Result<Matrix<T>> {
901    debug_assert!(rank <= nrows.min(ncols));
902    debug_assert_eq!(data.len(), nrows * ncols);
903
904    let mut u_data = vec![T::zero(); rank * ncols];
905    for col in 0..ncols {
906        let rows_to_copy = rank.min(col + 1);
907        if rows_to_copy > 0 {
908            let src_start = col_major_offset(nrows, 0, col);
909            let dst_start = col_major_offset(rank, 0, col);
910            u_data[dst_start..dst_start + rows_to_copy]
911                .copy_from_slice(&data[src_start..src_start + rows_to_copy]);
912        }
913    }
914
915    if !left_orthogonal {
916        for i in 0..rank {
917            u_data[col_major_offset(rank, i, i)] = T::one();
918        }
919    }
920
921    if !all_magnitudes_finite(&u_data) {
922        return Err(MatrixCIError::NaNEncountered {
923            matrix: "U".to_string(),
924        });
925    }
926
927    Ok(Matrix::from_col_major_vec(rank, ncols, u_data))
928}
929
930fn extract_lu_from_factorized<T: Scalar>(
931    data: &[T],
932    nrows: usize,
933    ncols: usize,
934    rank: usize,
935    left_orthogonal: bool,
936) -> Result<(Matrix<T>, Matrix<T>)> {
937    let left = extract_l_from_factorized(data, nrows, rank, left_orthogonal)?;
938    let right = extract_u_from_factorized(data, nrows, ncols, rank, left_orthogonal)?;
939    Ok((left, right))
940}
941
942/// Options for rank-revealing LU decomposition.
943///
944/// # Examples
945///
946/// ```
947/// use tensor4all_core::RrLUOptions;
948///
949/// // Default: rel_tol = 1e-14, no absolute tolerance, no rank limit
950/// let opts = RrLUOptions::default();
951/// assert_eq!(opts.rel_tol, 1e-14);
952/// assert_eq!(opts.abs_tol, 0.0);
953/// assert!(opts.left_orthogonal);
954///
955/// // Limit rank to 5
956/// let opts = RrLUOptions { max_bond_dim: 5, ..Default::default() };
957/// assert_eq!(opts.max_bond_dim, 5);
958/// ```
959#[derive(Debug, Clone)]
960pub struct RrLUOptions {
961    /// Maximum rank
962    pub max_bond_dim: usize,
963    /// Relative tolerance
964    pub rel_tol: f64,
965    /// Absolute tolerance
966    pub abs_tol: f64,
967    /// Left orthogonal (L has 1s on diagonal) or right orthogonal (U has 1s)
968    pub left_orthogonal: bool,
969}
970
971struct RrLUFactorization {
972    row_permutation: Vec<usize>,
973    col_permutation: Vec<usize>,
974    n_pivot: usize,
975    error: f64,
976}
977
978/// Left factor and pivot diagnostics needed by row interpolation.
979///
980/// This avoids materializing the complementary upper factor for RSI's
981/// row-only path while sharing the same pivoting implementation as [`rrlu_mut`].
982pub(crate) struct RrLULeft<T: Scalar> {
983    pub(crate) row_permutation: Vec<usize>,
984    pub(crate) l: Matrix<T>,
985    pub(crate) n_pivot: usize,
986    pub(crate) pivot_magnitudes: Vec<f64>,
987}
988
989/// Factorize after checking that every input magnitude is finite.
990fn factorize_mut_in_place<T: Scalar>(
991    a: &mut Matrix<T>,
992    opts: RrLUOptions,
993) -> Result<RrLUFactorization> {
994    if !all_magnitudes_finite(a.as_col_major_slice()) {
995        return Err(MatrixCIError::NaNEncountered {
996            matrix: "input".to_string(),
997        });
998    }
999    factorize_validated_in_place(a, opts)
1000}
1001
1002/// Factorize a matrix whose entries the caller has validated.
1003///
1004/// INVARIANT: every input magnitude is finite (`validate_owned_luci_input`);
1005/// the elimination below still reports non-finite intermediates.
1006fn factorize_validated_in_place<T: Scalar>(
1007    a: &mut Matrix<T>,
1008    opts: RrLUOptions,
1009) -> Result<RrLUFactorization> {
1010    let nr = a.nrows();
1011    let nc = a.ncols();
1012    let data = a.as_col_major_mut_slice();
1013    validate_col_major_matrix_len(nr, nc, data.len())?;
1014
1015    let max_bond_dim = opts.max_bond_dim.min(nr).min(nc);
1016    let mut row_permutation = (0..nr).collect::<Vec<_>>();
1017    let mut col_permutation = (0..nc).collect::<Vec<_>>();
1018    let mut n_pivot = 0;
1019    let mut error = f64::NAN;
1020    let mut max_error = 0.0f64;
1021    // The argmax of the trailing block, found by the previous step's update.
1022    let mut next_argmax = None;
1023
1024    while n_pivot < max_bond_dim {
1025        let k = n_pivot;
1026        if k >= nr || k >= nc {
1027            break;
1028        }
1029
1030        let (pivot_row, pivot_col, pivot_val) = match next_argmax.take() {
1031            Some(found) => found,
1032            None => submatrix_argmax_col_major(data, nr, nc, k, nr, k, nc),
1033        };
1034        let pivot_abs = pivot_val.abs_val();
1035        error = pivot_abs;
1036        if !pivot_abs.is_finite() {
1037            return Err(MatrixCIError::NaNEncountered {
1038                matrix: "residual".to_string(),
1039            });
1040        }
1041
1042        // Check stopping criteria (but add at least 1 pivot)
1043        if n_pivot > 0 && (pivot_abs < opts.rel_tol * max_error || pivot_abs < opts.abs_tol) {
1044            break;
1045        }
1046
1047        if pivot_is_undividable::<T>(pivot_abs) {
1048            break;
1049        }
1050
1051        max_error = max_error.max(pivot_abs);
1052
1053        // Swap rows and columns
1054        if pivot_row != k {
1055            swap_rows_col_major(data, nr, nc, k, pivot_row);
1056            row_permutation.swap(k, pivot_row);
1057        }
1058        if pivot_col != k {
1059            swap_cols_col_major(data, nr, nc, k, pivot_col);
1060            col_permutation.swap(k, pivot_col);
1061        }
1062
1063        let pivot = col_major_get(data, nr, k, k);
1064
1065        // Eliminate
1066        if opts.left_orthogonal {
1067            scale_column_tail(data, nr, k, k + 1, pivot);
1068        } else {
1069            scale_row_tail(data, nr, nc, k, k + 1, pivot);
1070        }
1071
1072        next_argmax = update_trailing_submatrix_with_argmax(data, nr, nc, k);
1073        n_pivot += 1;
1074    }
1075
1076    // Preserve the full-factor API's existing diagnostic semantics.
1077    if n_pivot >= nr.min(nc) {
1078        error = 0.0;
1079    }
1080
1081    Ok(RrLUFactorization {
1082        row_permutation,
1083        col_permutation,
1084        n_pivot,
1085        error,
1086    })
1087}
1088
1089/// Pivot magnitudes and the final residual diagnostic of a factorization.
1090///
1091/// The trailing entry is `state.error` unless the search stopped exactly at a
1092/// rank cap below `min(nrows, ncols)`, in which case it is the maximum
1093/// magnitude of the remaining Schur complement. A zero cap therefore reports
1094/// the whole matrix. Shared with [`rrlu_mut`] so the selection-only path cannot
1095/// drift from the full-factor error history.
1096fn pivot_errors_from_factorization<T: Scalar>(
1097    a: &Matrix<T>,
1098    state: &RrLUFactorization,
1099    rank_cap: usize,
1100) -> Result<Vec<f64>> {
1101    let nrows = a.nrows();
1102    let ncols = a.ncols();
1103    let data = a.as_col_major_slice();
1104    let mut errors = (0..state.n_pivot)
1105        .map(|i| data[col_major_offset(nrows, i, i)].abs_val())
1106        .collect::<Vec<_>>();
1107
1108    let max_bond_dim = rank_cap.min(nrows).min(ncols);
1109    let mut error = state.error;
1110    if state.n_pivot < nrows.min(ncols) && state.n_pivot == max_bond_dim {
1111        error = 0.0;
1112        for col in state.n_pivot..ncols {
1113            for row in state.n_pivot..nrows {
1114                let residual = col_major_get(data, nrows, row, col).abs_val();
1115                if !residual.is_finite() {
1116                    return Err(MatrixCIError::NaNEncountered {
1117                        matrix: "residual".to_string(),
1118                    });
1119                }
1120                error = error.max(residual);
1121            }
1122        }
1123    }
1124    errors.push(error);
1125    Ok(errors)
1126}
1127
1128pub(crate) fn rrlu_left_mut<T: Scalar>(
1129    a: &mut Matrix<T>,
1130    options: Option<RrLUOptions>,
1131) -> Result<RrLULeft<T>> {
1132    let mut options = options.unwrap_or_default();
1133    options.left_orthogonal = true;
1134    // INVARIANT: the caller (`matrix_luci`) validated the input.
1135    let state = factorize_validated_in_place(a, options)?;
1136    let nrows = a.nrows();
1137    let data = a.as_col_major_slice();
1138    let mut pivot_magnitudes = (0..state.n_pivot)
1139        .map(|i| data[col_major_offset(nrows, i, i)].abs_val())
1140        .collect::<Vec<_>>();
1141    // The row-only API measures the remaining residual even at a rank cap.
1142    let residual = if state.n_pivot >= a.nrows().min(a.ncols()) {
1143        0.0
1144    } else {
1145        let (_, _, value) = submatrix_argmax_col_major(
1146            data,
1147            nrows,
1148            a.ncols(),
1149            state.n_pivot,
1150            nrows,
1151            state.n_pivot,
1152            a.ncols(),
1153        );
1154        value.abs_val()
1155    };
1156    if !residual.is_finite() {
1157        return Err(MatrixCIError::NaNEncountered {
1158            matrix: "residual".to_string(),
1159        });
1160    }
1161    pivot_magnitudes.push(residual);
1162    let l = extract_l_from_factorized(data, nrows, state.n_pivot, true)?;
1163    Ok(RrLULeft {
1164        row_permutation: state.row_permutation,
1165        l,
1166        n_pivot: state.n_pivot,
1167        pivot_magnitudes,
1168    })
1169}
1170
1171impl Default for RrLUOptions {
1172    fn default() -> Self {
1173        Self {
1174            max_bond_dim: usize::MAX,
1175            rel_tol: 1e-14,
1176            abs_tol: 0.0,
1177            left_orthogonal: true,
1178        }
1179    }
1180}
1181
1182/// Perform in-place rank-revealing LU decomposition.
1183///
1184/// The input matrix `a` is modified in place. Use [`rrlu`] for a
1185/// non-destructive version.
1186///
1187/// # Errors
1188///
1189/// Returns [`MatrixCIError::InvalidArgument`] if the matrix shape product
1190/// overflows `usize` or its backing storage length does not match the shape.
1191/// Returns [`MatrixCIError::NaNEncountered`] if input entries or intermediate
1192/// factors have non-finite magnitudes.
1193///
1194/// # Examples
1195///
1196/// ```
1197/// use tensor4all_core::{matrixlu::rrlu_mut, RrLUOptions};
1198/// use tensor4all_tensorbackend::from_vec2d;
1199///
1200/// let mut m = from_vec2d(vec![
1201///     vec![1.0_f64, 2.0],
1202///     vec![3.0, 4.0],
1203/// ]);
1204/// let lu = rrlu_mut(&mut m, Some(RrLUOptions { max_bond_dim: 1, ..Default::default() })).unwrap();
1205/// assert_eq!(lu.npivots(), 1);
1206/// ```
1207pub fn rrlu_mut<T: Scalar>(a: &mut Matrix<T>, options: Option<RrLUOptions>) -> Result<RrLU<T>> {
1208    let opts = options.unwrap_or_default();
1209    let left_orthogonal = opts.left_orthogonal;
1210    let rank_cap = opts.max_bond_dim;
1211    let state = factorize_mut_in_place(a, opts)?;
1212    let nrows = a.nrows();
1213    let ncols = a.ncols();
1214    let (l, u) = extract_lu_from_factorized(
1215        a.as_col_major_slice(),
1216        nrows,
1217        ncols,
1218        state.n_pivot,
1219        left_orthogonal,
1220    )?;
1221
1222    // A rank ceiling exits before the next pivot scan. The shared extraction
1223    // reports the remaining Schur complement, not the magnitude of the last
1224    // accepted pivot.
1225    let mut error = pivot_errors_from_factorization(a, &state, rank_cap)?;
1226    let error = error.pop().unwrap_or(0.0);
1227
1228    Ok(RrLU {
1229        row_permutation: state.row_permutation,
1230        col_permutation: state.col_permutation,
1231        l,
1232        u,
1233        left_orthogonal,
1234        n_pivot: state.n_pivot,
1235        error,
1236    })
1237}
1238
1239/// Pivot indices and error diagnostics from a rank-revealing LU selection.
1240///
1241/// This is the selection-only counterpart of [`RrLU`]: the same pivot search
1242/// and rank decision as [`rrlu`]/[`rrlu_mut`], but without assembling the `L`
1243/// and `U` factors. Use it when only the selected pivots and the pivot error
1244/// history are needed and the factors would be discarded.
1245///
1246/// # Examples
1247///
1248/// ```
1249/// use tensor4all_core::matrixlu::rrlu_pivots;
1250/// use tensor4all_tensorbackend::from_vec2d;
1251///
1252/// let a = from_vec2d(vec![
1253///     vec![1.0_f64, 2.0],
1254///     vec![2.0, 4.0],
1255/// ]);
1256/// let pivots = rrlu_pivots(a, None).unwrap();
1257/// assert_eq!(pivots.rank, 1);
1258/// assert_eq!(pivots.row_indices.len(), pivots.rank);
1259/// assert_eq!(pivots.col_indices.len(), pivots.rank);
1260/// // One accepted pivot plus the final residual.
1261/// assert_eq!(pivots.pivot_errors.len(), pivots.rank + 1);
1262/// ```
1263#[derive(Debug, Clone, PartialEq)]
1264pub struct RrLUPivots {
1265    /// Selected row indices, in pivot order.
1266    pub row_indices: Vec<usize>,
1267    /// Selected column indices, in pivot order.
1268    pub col_indices: Vec<usize>,
1269    /// Accepted pivot magnitudes followed by the final residual estimate.
1270    pub pivot_errors: Vec<f64>,
1271    /// Number of selected pivots.
1272    pub rank: usize,
1273}
1274
1275/// Select rrLU pivots without constructing the triangular factors.
1276///
1277/// Consumes the column-major matrix `a` (its storage is reused for the in-place
1278/// elimination) and returns the selected row and column indices plus the pivot
1279/// error history, using the same rank and tolerance rules as [`rrlu_mut`]. The
1280/// trailing `pivot_errors` entry is the maximum remaining residual after a rank
1281/// cap, so the sequence matches [`rrlu_mut`]'s `pivot_errors` exactly.
1282///
1283/// # Errors
1284///
1285/// Returns [`MatrixCIError::InvalidArgument`] if the matrix shape product
1286/// overflows `usize`, its backing storage length does not match the shape, a
1287/// tolerance is negative or non-finite, or an input entry is infinite. Returns
1288/// [`MatrixCIError::NaNEncountered`] if an input entry or the remaining
1289/// residual is NaN.
1290///
1291/// # Examples
1292///
1293/// ```
1294/// use tensor4all_core::{matrixlu::rrlu_pivots, RrLUOptions};
1295/// use tensor4all_tensorbackend::from_vec2d;
1296///
1297/// let a = from_vec2d(vec![
1298///     vec![1.0_f64, 0.0],
1299///     vec![0.0, 2.0],
1300/// ]);
1301/// // The first pivot is the largest-magnitude entry, at (1, 1).
1302/// let pivots = rrlu_pivots(a, Some(RrLUOptions::default())).unwrap();
1303/// assert_eq!(pivots.rank, 2);
1304/// assert_eq!(pivots.row_indices, vec![1, 0]);
1305/// assert_eq!(pivots.col_indices, vec![1, 0]);
1306/// assert_eq!(pivots.pivot_errors, vec![2.0, 1.0, 0.0]);
1307/// ```
1308pub fn rrlu_pivots<T: Scalar>(
1309    mut a: Matrix<T>,
1310    options: Option<RrLUOptions>,
1311) -> Result<RrLUPivots> {
1312    let opts = options.unwrap_or_default();
1313    let rank_cap = opts.max_bond_dim;
1314    validate_owned_luci_input(&a, &opts)?;
1315    let state = factorize_validated_in_place(&mut a, opts)?;
1316    let pivot_errors = pivot_errors_from_factorization(&a, &state, rank_cap)?;
1317    Ok(RrLUPivots {
1318        row_indices: state.row_permutation[..state.n_pivot].to_vec(),
1319        col_indices: state.col_permutation[..state.n_pivot].to_vec(),
1320        pivot_errors,
1321        rank: state.n_pivot,
1322    })
1323}
1324
1325/// Perform rank-revealing LU decomposition (non-destructive).
1326///
1327/// Clones the input matrix and calls [`rrlu_mut`].
1328///
1329/// # Errors
1330///
1331/// Returns [`MatrixCIError::InvalidArgument`] if the matrix shape product
1332/// overflows `usize` or its backing storage length does not match the shape.
1333/// Returns [`MatrixCIError::NaNEncountered`] if input entries or intermediate
1334/// factors have non-finite magnitudes.
1335///
1336/// # Examples
1337///
1338/// ```
1339/// use tensor4all_core::matrixlu::rrlu;
1340/// use tensor4all_tensorbackend::from_vec2d;
1341///
1342/// let m = from_vec2d(vec![
1343///     vec![1.0_f64, 0.0],
1344///     vec![0.0, 2.0],
1345/// ]);
1346/// let lu = rrlu(&m, None).unwrap();
1347/// assert_eq!(lu.npivots(), 2);
1348/// assert_eq!(lu.nrows(), 2);
1349/// assert_eq!(lu.ncols(), 2);
1350/// ```
1351pub fn rrlu<T: Scalar>(a: &Matrix<T>, options: Option<RrLUOptions>) -> Result<RrLU<T>> {
1352    let mut a_copy = a.clone();
1353    rrlu_mut(&mut a_copy, options)
1354}
1355
1356/// Convert L matrix to solve L * X = B given pivot matrix P
1357///
1358/// Modifies `c` in place so that the columns satisfy the triangular
1359/// system defined by `p`. The matrix `c` must have at least `p.nrows()`
1360/// columns.
1361///
1362/// # Errors
1363/// Returns [`MatrixCIError::InvalidArgument`] when `p` is not square or
1364/// `c` has too few columns, and [`MatrixCIError::SingularMatrix`] for a zero
1365/// diagonal pivot or one with an unrepresentable reciprocal; non-finite pivots
1366/// return [`MatrixCIError::NaNEncountered`].
1367///
1368/// # Examples
1369///
1370/// ```
1371/// use tensor4all_core::matrixlu::cols_to_l_matrix;
1372/// use tensor4all_tensorbackend::from_vec2d;
1373///
1374/// // Upper-triangular P (2x2)
1375/// let p = from_vec2d(vec![
1376///     vec![2.0_f64, 1.0],
1377///     vec![0.0, 3.0],
1378/// ]);
1379/// // c has 3 rows, 2 columns (ncols >= p.nrows())
1380/// let mut c = from_vec2d(vec![
1381///     vec![4.0_f64, 5.0],
1382///     vec![6.0, 9.0],
1383///     vec![8.0, 7.0],
1384/// ]);
1385/// cols_to_l_matrix(&mut c, &p, true).unwrap();
1386/// // After processing: c[:,0] was divided by p[0,0]=2
1387/// assert!((c[[0, 0]] - 2.0).abs() < 1e-10);
1388/// assert!((c[[1, 0]] - 3.0).abs() < 1e-10);
1389/// assert!((c[[2, 0]] - 4.0).abs() < 1e-10);
1390/// ```
1391pub fn cols_to_l_matrix<T: Scalar>(
1392    c: &mut Matrix<T>,
1393    p: &Matrix<T>,
1394    _left_orthogonal: bool,
1395) -> Result<()> {
1396    if p.nrows() != p.ncols() || c.ncols() < p.nrows() {
1397        return Err(MatrixCIError::InvalidArgument {
1398            message: format!(
1399                "cols_to_l_matrix requires square p and c.ncols() >= p.nrows(), got p=({}, {}), c.ncols()={}",
1400                p.nrows(),
1401                p.ncols(),
1402                c.ncols()
1403            ),
1404        });
1405    }
1406    let n = p.nrows();
1407    for k in 0..n {
1408        let magnitude = p[[k, k]].abs_val();
1409        if !magnitude.is_finite() {
1410            return Err(MatrixCIError::NaNEncountered {
1411                matrix: "pivot".to_string(),
1412            });
1413        }
1414        if pivot_is_undividable::<T>(magnitude) {
1415            return Err(MatrixCIError::SingularMatrix);
1416        }
1417    }
1418
1419    for k in 0..n {
1420        let pivot = p[[k, k]];
1421        let nrows = c.nrows();
1422        scale_column_tail(c.as_col_major_mut_slice(), nrows, k, 0, pivot);
1423
1424        // c[:, k+1:] -= c[:, k] * p[k, k+1:]
1425        for j in (k + 1)..c.ncols() {
1426            let p_kj = p[[k, j]];
1427            for i in 0..c.nrows() {
1428                let c_ik = c[[i, k]];
1429                let old = c[[i, j]];
1430                c[[i, j]] = old - c_ik * p_kj;
1431            }
1432        }
1433    }
1434    Ok(())
1435}
1436
1437/// Convert R matrix to solve X * U = B given pivot matrix P
1438///
1439/// Modifies `r` in place so that the rows satisfy the triangular
1440/// system defined by `p`. The matrix `r` must have at least `p.nrows()`
1441/// rows.
1442///
1443/// # Errors
1444/// Returns [`MatrixCIError::InvalidArgument`] when `p` is not square or
1445/// `r` has too few rows, and [`MatrixCIError::SingularMatrix`] for a zero
1446/// diagonal pivot or one with an unrepresentable reciprocal; non-finite pivots
1447/// return [`MatrixCIError::NaNEncountered`].
1448///
1449/// # Examples
1450///
1451/// ```
1452/// use tensor4all_core::matrixlu::rows_to_u_matrix;
1453/// use tensor4all_tensorbackend::from_vec2d;
1454///
1455/// // Lower-triangular P (2x2)
1456/// let p = from_vec2d(vec![
1457///     vec![2.0_f64, 0.0],
1458///     vec![1.0, 3.0],
1459/// ]);
1460/// // r has 2 rows (nrows >= p.nrows()), 3 columns
1461/// let mut r = from_vec2d(vec![
1462///     vec![4.0_f64, 6.0, 8.0],
1463///     vec![5.0, 9.0, 7.0],
1464/// ]);
1465/// rows_to_u_matrix(&mut r, &p, true).unwrap();
1466/// // After processing: r[0,:] was divided by p[0,0]=2
1467/// assert!((r[[0, 0]] - 2.0).abs() < 1e-10);
1468/// assert!((r[[0, 1]] - 3.0).abs() < 1e-10);
1469/// assert!((r[[0, 2]] - 4.0).abs() < 1e-10);
1470/// ```
1471pub fn rows_to_u_matrix<T: Scalar>(
1472    r: &mut Matrix<T>,
1473    p: &Matrix<T>,
1474    _left_orthogonal: bool,
1475) -> Result<()> {
1476    if p.nrows() != p.ncols() || r.nrows() < p.nrows() {
1477        return Err(MatrixCIError::InvalidArgument {
1478            message: format!(
1479                "rows_to_u_matrix requires square p and r.nrows() >= p.nrows(), got p=({}, {}), r.nrows()={}",
1480                p.nrows(),
1481                p.ncols(),
1482                r.nrows()
1483            ),
1484        });
1485    }
1486    let n = p.nrows();
1487    for k in 0..n {
1488        let magnitude = p[[k, k]].abs_val();
1489        if !magnitude.is_finite() {
1490            return Err(MatrixCIError::NaNEncountered {
1491                matrix: "pivot".to_string(),
1492            });
1493        }
1494        if pivot_is_undividable::<T>(magnitude) {
1495            return Err(MatrixCIError::SingularMatrix);
1496        }
1497    }
1498
1499    for k in 0..n {
1500        let pivot = p[[k, k]];
1501        let (nrows, ncols) = (r.nrows(), r.ncols());
1502        scale_row_tail(r.as_col_major_mut_slice(), nrows, ncols, k, 0, pivot);
1503
1504        // r[k+1:, :] -= p[k+1:, k] * r[k, :]
1505        for i in (k + 1)..r.nrows() {
1506            let p_ik = p[[i, k]];
1507            for j in 0..r.ncols() {
1508                let r_kj = r[[k, j]];
1509                let old = r[[i, j]];
1510                r[[i, j]] = old - p_ik * r_kj;
1511            }
1512        }
1513    }
1514    Ok(())
1515}
1516
1517#[cfg(test)]
1518mod tests;