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;