Skip to main content

tpt_math_linalg_dense/
lib.rs

1#![no_std]
2#![forbid(unsafe_code)]
3// Dense numeric kernels are clearest with explicit indexing; the indexed-loop
4// lint does not fit this code.
5#![allow(clippy::needless_range_loop)]
6//! Dense linear algebra implemented entirely in-house (no external backend).
7//!
8//! This crate owns the dynamically-sized [`DVector`] and [`DMatrix`] types used
9//! as the storage backend for `tpt-math-linalg` and `tpt-math-optimize`. The
10//! matrices are stored column-major in a plain `Vec<T>`, so there is no
11//! `faer`/`nalgebra` dependency and no license exposure. The arithmetic, norms,
12//! and the partial-pivot-LU `solve`/`inverse` are all hand-rolled.
13//!
14//! Unlike the old `nalgebra`-backed path, this crate is the single storage
15//! backend for `tpt-math-linalg` and `tpt-math-optimize`, so it owns its own
16//! `DVector`/`DMatrix` types (which also resolves an orphan-rule problem for
17//! any external solver trait impls).
18//!
19//! # Features
20//!
21//! * `std` (default) — enable the allocator and the `std` support of deps.
22//! * `alloc` — signal allocator availability (dynamic vectors need it).
23//!
24//! # Examples
25//!
26//! ```
27//! use tpt_math_linalg_dense::{DMatrix, DVector};
28//!
29//! let a = DVector::from_vec(vec![1.0_f64, 2.0, 3.0]);
30//! let b = DVector::from_vec(vec![4.0_f64, 5.0, 6.0]);
31//! assert_eq!(a.dot(&b), 32.0);
32//!
33//! let m = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 3.0, 4.0]);
34//! let v = DVector::from_vec(vec![1.0_f64, 1.0]);
35//! let mv = m * v;
36//! assert_eq!(mv[0], 3.0);
37//! assert_eq!(mv[1], 7.0);
38//! ```
39
40extern crate alloc;
41
42use core::fmt;
43use core::ops::Index;
44#[cfg(feature = "alloc")]
45use core::ops::{Add, Div, Mul, Neg, Sub};
46
47use tpt_math_numeric::Scalar;
48
49// The storage types own a `Vec` whether or not the `alloc` feature is on, so the
50// import is unconditional. The feature gates the constructors and algorithms.
51use alloc::vec::Vec;
52
53#[cfg(feature = "alloc")]
54use alloc::{format, string::String, vec};
55
56#[cfg(feature = "alloc")]
57#[cfg(feature = "alloc")]
58mod diagnostics;
59#[cfg(feature = "alloc")]
60pub use diagnostics::{SolveDiagnostics, ILL_CONDITIONED_THRESHOLD};
61#[cfg(feature = "alloc")]
62mod eig;
63#[cfg(feature = "alloc")]
64pub use eig::Eigenvalue;
65#[cfg(feature = "alloc")]
66mod banded;
67#[cfg(feature = "alloc")]
68pub use banded::solve_banded;
69#[cfg(feature = "alloc")]
70mod factor;
71#[cfg(feature = "alloc")]
72pub use factor::{solve_tridiagonal, Cholesky};
73
74/// A dynamically-sized column vector of `T`, stored as a contiguous `Vec`.
75#[derive(Clone)]
76pub struct DVector<T = f64> {
77    data: Vec<T>,
78}
79
80/// A dynamically-sized matrix of `T`, stored column-major in a contiguous `Vec`
81/// (`(i, j)` lives at `i + j * nrows`).
82#[derive(Clone)]
83pub struct DMatrix<T = f64> {
84    nrows: usize,
85    ncols: usize,
86    data: Vec<T>,
87}
88
89// ---------------------------------------------------------------------------
90// Construction (allocator required)
91// ---------------------------------------------------------------------------
92
93#[cfg(feature = "alloc")]
94impl<T> DVector<T> {
95    /// A zero vector of length `n`.
96    pub fn zeros(n: usize) -> Self
97    where
98        T: Scalar,
99    {
100        DVector::from_fn(n, |_| T::zero())
101    }
102
103    /// Build from a `Vec` (elements in order).
104    pub fn from_vec(data: Vec<T>) -> Self {
105        DVector { data }
106    }
107
108    /// Build from a slice (elements in order).
109    pub fn from_row_slice(data: &[T]) -> Self
110    where
111        T: Clone,
112    {
113        DVector {
114            data: data.to_vec(),
115        }
116    }
117
118    /// Build element-by-element with `f(i)`.
119    pub fn from_fn(n: usize, f: impl FnMut(usize) -> T) -> Self {
120        DVector {
121            data: (0..n).map(f).collect(),
122        }
123    }
124}
125
126#[cfg(feature = "alloc")]
127impl<T> DMatrix<T> {
128    /// A zero matrix of the given shape.
129    pub fn zeros(nrows: usize, ncols: usize) -> Self
130    where
131        T: Scalar,
132    {
133        DMatrix::from_fn(nrows, ncols, |_, _| T::zero())
134    }
135
136    /// Build from a `Vec` laid out **column-major**: element `(i, j)` is
137    /// `data[i + j * nrows]`.
138    /// # Panics
139    ///
140    /// Panics if `data.len() != nrows * ncols`.
141    pub fn from_vec(nrows: usize, ncols: usize, data: Vec<T>) -> Self {
142        assert_eq!(
143            data.len(),
144            nrows * ncols,
145            "data length {} does not match a {nrows}x{ncols} matrix",
146            data.len()
147        );
148        DMatrix { nrows, ncols, data }
149    }
150
151    /// Build from a slice laid out **row-major**.
152    ///
153    /// # Panics
154    ///
155    /// Panics if `data.len() != nrows * ncols`.
156    pub fn from_row_slice(nrows: usize, ncols: usize, data: &[T]) -> Self
157    where
158        T: Clone,
159    {
160        assert_eq!(
161            data.len(),
162            nrows * ncols,
163            "data length {} does not match a {nrows}x{ncols} matrix",
164            data.len()
165        );
166        DMatrix {
167            nrows,
168            ncols,
169            data: (0..ncols)
170                .flat_map(|j| (0..nrows).map(move |i| data[i * ncols + j].clone()))
171                .collect(),
172        }
173    }
174
175    /// Build element-by-element with `f(i, j)`.
176    pub fn from_fn(nrows: usize, ncols: usize, mut f: impl FnMut(usize, usize) -> T) -> Self {
177        let mut data = Vec::with_capacity(nrows * ncols);
178        for j in 0..ncols {
179            for i in 0..nrows {
180                data.push(f(i, j));
181            }
182        }
183        DMatrix { nrows, ncols, data }
184    }
185
186    /// A square matrix with `v`'s elements on the diagonal, zeros elsewhere.
187    pub fn from_diagonal(v: &DVector<T>) -> Self
188    where
189        T: Scalar + Clone,
190    {
191        let n = v.len();
192        DMatrix::from_fn(n, n, |i, j| if i == j { v[i] } else { T::zero() })
193    }
194}
195
196// ---------------------------------------------------------------------------
197// Accessors
198// ---------------------------------------------------------------------------
199
200impl<T> DVector<T> {
201    /// Number of components.
202    pub fn len(&self) -> usize {
203        self.data.len()
204    }
205
206    /// True if the vector has no components.
207    pub fn is_empty(&self) -> bool {
208        self.data.is_empty()
209    }
210
211    /// Iterate over the elements (in order).
212    pub fn iter(&self) -> impl Iterator<Item = &T> {
213        self.data.iter()
214    }
215
216    /// The elements as a contiguous slice.
217    pub fn as_slice(&self) -> &[T] {
218        &self.data
219    }
220
221    /// The elements as a contiguous mutable slice.
222    pub fn as_mut_slice(&mut self) -> &mut [T] {
223        &mut self.data
224    }
225}
226
227impl<T> DMatrix<T> {
228    /// Number of rows.
229    pub fn nrows(&self) -> usize {
230        self.nrows
231    }
232
233    /// Number of columns.
234    pub fn ncols(&self) -> usize {
235        self.ncols
236    }
237
238    /// True if the matrix has no entries.
239    pub fn is_empty(&self) -> bool {
240        self.nrows == 0 || self.ncols == 0
241    }
242
243    /// Iterate over all elements in column-major order.
244    pub fn iter(&self) -> impl Iterator<Item = &T> {
245        self.data.iter()
246    }
247
248    /// The elements as a contiguous column-major slice (`(i, j)` is at
249    /// `i + j * nrows`).
250    pub fn as_slice(&self) -> &[T] {
251        &self.data
252    }
253
254    /// The elements as a contiguous mutable column-major slice.
255    pub fn as_mut_slice(&mut self) -> &mut [T] {
256        &mut self.data
257    }
258
259    /// Column-major linear index of `(i, j)`.
260    fn offset(&self, i: usize, j: usize) -> usize {
261        i + j * self.nrows
262    }
263}
264
265// ---------------------------------------------------------------------------
266// Indexing
267// ---------------------------------------------------------------------------
268
269impl<T> Index<usize> for DVector<T> {
270    type Output = T;
271    /// # Panics
272    ///
273    /// Panics if `i` is out of bounds.
274    fn index(&self, i: usize) -> &T {
275        &self.data[i]
276    }
277}
278
279impl<T> Index<(usize, usize)> for DMatrix<T> {
280    type Output = T;
281    /// # Panics
282    ///
283    /// Panics if `(i, j)` is out of bounds.
284    fn index(&self, (i, j): (usize, usize)) -> &T {
285        // Checked per axis: a row index past `nrows` would otherwise alias
286        // another element in column-major storage.
287        assert!(
288            i < self.nrows && j < self.ncols,
289            "index ({i}, {j}) out of bounds for a {}x{} matrix",
290            self.nrows,
291            self.ncols
292        );
293        &self.data[self.offset(i, j)]
294    }
295}
296
297// ---------------------------------------------------------------------------
298// Norms / dot products (allocator-free)
299// ---------------------------------------------------------------------------
300
301#[cfg(not(feature = "simd"))]
302impl<T: Scalar> DVector<T> {
303    /// The Euclidean (L2) norm.
304    pub fn norm(&self) -> T {
305        self.norm_generic()
306    }
307
308    /// Dot product with another vector of the same length.
309    pub fn dot(&self, other: &DVector<T>) -> T {
310        self.dot_generic(other)
311    }
312}
313
314/// With the `simd` feature, `f32`/`f64` vectors use `tpt-simd-blas` (reassociated
315/// sums; may differ from the scalar loop by a few ulps).
316#[cfg(feature = "simd")]
317impl<T: Scalar + 'static> DVector<T> {
318    /// The Euclidean (L2) norm.
319    pub fn norm(&self) -> T {
320        if let Some(v) = simd::as_f64(&self.data) {
321            return simd::from_f64(tpt_simd_blas::nrm2_f64(v));
322        }
323        if let Some(v) = simd::as_f32(&self.data) {
324            return simd::from_f32(tpt_simd_blas::nrm2_f32(v));
325        }
326        self.norm_generic()
327    }
328
329    /// Dot product with another vector of the same length.
330    pub fn dot(&self, other: &DVector<T>) -> T {
331        if self.len() == other.len() {
332            if let (Some(a), Some(b)) = (simd::as_f64(&self.data), simd::as_f64(&other.data)) {
333                return simd::from_f64(tpt_simd_blas::dot_f64(a, b));
334            }
335            if let (Some(a), Some(b)) = (simd::as_f32(&self.data), simd::as_f32(&other.data)) {
336                return simd::from_f32(tpt_simd_blas::dot_f32(a, b));
337            }
338        }
339        self.dot_generic(other)
340    }
341}
342
343impl<T: Scalar> DVector<T> {
344    fn norm_generic(&self) -> T {
345        // Scale by the largest magnitude so squaring cannot overflow or underflow
346        // (a plain sum of squares overflows for entries near `sqrt(T::MAX)`).
347        let scale = self.iter().fold(T::zero(), |acc, x| {
348            let a = x.abs();
349            if a > acc {
350                a
351            } else {
352                acc
353            }
354        });
355        if scale == T::zero() || !scale.is_finite() {
356            // All-zero: norm is zero. Non-finite: let inf/NaN propagate as before.
357            let s = self.iter().fold(T::zero(), |acc, x| acc + (*x) * (*x));
358            return s.sqrt();
359        }
360        let s = self.iter().fold(T::zero(), |acc, x| {
361            let r = *x / scale;
362            acc + r * r
363        });
364        scale * s.sqrt()
365    }
366
367    fn dot_generic(&self, other: &DVector<T>) -> T {
368        assert_eq!(
369            self.len(),
370            other.len(),
371            "dot product requires equal lengths"
372        );
373        self.iter()
374            .zip(other.iter())
375            .fold(T::zero(), |acc, (a, b)| acc + (*a) * (*b))
376    }
377}
378
379// ---------------------------------------------------------------------------
380// Transpose
381// ---------------------------------------------------------------------------
382
383#[cfg(feature = "alloc")]
384impl<T: Scalar + Clone> DVector<T> {
385    /// Transpose to a `1 x n` row matrix.
386    pub fn transpose(&self) -> DMatrix<T> {
387        let n = self.len();
388        DMatrix::from_fn(1, n, |_, j| self[j])
389    }
390}
391
392#[cfg(feature = "alloc")]
393impl<T: Scalar + Clone> DMatrix<T> {
394    /// Transpose, swapping rows and columns.
395    pub fn transpose(&self) -> DMatrix<T> {
396        let (m, n) = (self.nrows, self.ncols);
397        DMatrix::from_fn(n, m, |i, j| self[(j, i)])
398    }
399}
400
401// ---------------------------------------------------------------------------
402// Elementwise + scalar arithmetic
403// ---------------------------------------------------------------------------
404
405#[cfg(feature = "alloc")]
406impl<T: Scalar> Add for DVector<T> {
407    type Output = DVector<T>;
408    fn add(self, rhs: DVector<T>) -> DVector<T> {
409        let n = self.len();
410        DVector::from_fn(n, |i| self[i] + rhs[i])
411    }
412}
413
414#[cfg(feature = "alloc")]
415impl<T: Scalar> Sub for DVector<T> {
416    type Output = DVector<T>;
417    fn sub(self, rhs: DVector<T>) -> DVector<T> {
418        let n = self.len();
419        DVector::from_fn(n, |i| self[i] - rhs[i])
420    }
421}
422
423#[cfg(feature = "alloc")]
424impl<T: Scalar> Neg for DVector<T> {
425    type Output = DVector<T>;
426    fn neg(self) -> DVector<T> {
427        let n = self.len();
428        DVector::from_fn(n, |i| -self[i])
429    }
430}
431
432#[cfg(feature = "alloc")]
433impl<T: Scalar> Mul<T> for DVector<T> {
434    type Output = DVector<T>;
435    fn mul(self, rhs: T) -> DVector<T> {
436        let n = self.len();
437        DVector::from_fn(n, |i| self[i] * rhs)
438    }
439}
440
441#[cfg(feature = "alloc")]
442impl<T: Scalar> Div<T> for DVector<T> {
443    type Output = DVector<T>;
444    fn div(self, rhs: T) -> DVector<T> {
445        let n = self.len();
446        DVector::from_fn(n, |i| self[i] / rhs)
447    }
448}
449
450#[cfg(feature = "alloc")]
451impl<T: Scalar> Add<T> for DVector<T> {
452    type Output = DVector<T>;
453    fn add(self, rhs: T) -> DVector<T> {
454        let n = self.len();
455        DVector::from_fn(n, |i| self[i] + rhs)
456    }
457}
458
459#[cfg(feature = "alloc")]
460impl<T: Scalar> Sub<T> for DVector<T> {
461    type Output = DVector<T>;
462    fn sub(self, rhs: T) -> DVector<T> {
463        let n = self.len();
464        DVector::from_fn(n, |i| self[i] - rhs)
465    }
466}
467
468#[cfg(feature = "alloc")]
469impl<T: Scalar> Add for DMatrix<T> {
470    type Output = DMatrix<T>;
471    fn add(self, rhs: DMatrix<T>) -> DMatrix<T> {
472        let (m, n) = (self.nrows, self.ncols);
473        DMatrix::from_fn(m, n, |i, j| self[(i, j)] + rhs[(i, j)])
474    }
475}
476
477#[cfg(feature = "alloc")]
478impl<T: Scalar> Sub for DMatrix<T> {
479    type Output = DMatrix<T>;
480    fn sub(self, rhs: DMatrix<T>) -> DMatrix<T> {
481        let (m, n) = (self.nrows, self.ncols);
482        DMatrix::from_fn(m, n, |i, j| self[(i, j)] - rhs[(i, j)])
483    }
484}
485
486#[cfg(feature = "alloc")]
487impl<T: Scalar> Neg for DMatrix<T> {
488    type Output = DMatrix<T>;
489    fn neg(self) -> DMatrix<T> {
490        let (m, n) = (self.nrows, self.ncols);
491        DMatrix::from_fn(m, n, |i, j| -self[(i, j)])
492    }
493}
494
495#[cfg(feature = "alloc")]
496impl<T: Scalar> Mul<T> for DMatrix<T> {
497    type Output = DMatrix<T>;
498    fn mul(self, rhs: T) -> DMatrix<T> {
499        let (m, n) = (self.nrows, self.ncols);
500        DMatrix::from_fn(m, n, |i, j| self[(i, j)] * rhs)
501    }
502}
503
504#[cfg(feature = "alloc")]
505impl<T: Scalar> Div<T> for DMatrix<T> {
506    type Output = DMatrix<T>;
507    fn div(self, rhs: T) -> DMatrix<T> {
508        let (m, n) = (self.nrows, self.ncols);
509        DMatrix::from_fn(m, n, |i, j| self[(i, j)] / rhs)
510    }
511}
512
513#[cfg(feature = "alloc")]
514impl<T: Scalar> Add<T> for DMatrix<T> {
515    type Output = DMatrix<T>;
516    fn add(self, rhs: T) -> DMatrix<T> {
517        let (m, n) = (self.nrows, self.ncols);
518        DMatrix::from_fn(m, n, |i, j| self[(i, j)] + rhs)
519    }
520}
521
522#[cfg(feature = "alloc")]
523impl<T: Scalar> Sub<T> for DMatrix<T> {
524    type Output = DMatrix<T>;
525    fn sub(self, rhs: T) -> DMatrix<T> {
526        let (m, n) = (self.nrows, self.ncols);
527        DMatrix::from_fn(m, n, |i, j| self[(i, j)] - rhs)
528    }
529}
530
531// ---------------------------------------------------------------------------
532// In-place operators and `*_into` products (no allocation)
533// ---------------------------------------------------------------------------
534
535impl<T: Scalar> DVector<T> {
536    /// `self ← self + α·x` in place.
537    ///
538    /// # Panics
539    ///
540    /// Panics if the lengths differ.
541    pub fn axpy(&mut self, alpha: T, x: &DVector<T>) {
542        assert_eq!(self.len(), x.len(), "axpy: length mismatch");
543        for (s, &xi) in self.data.iter_mut().zip(&x.data) {
544            *s = *s + alpha * xi;
545        }
546    }
547}
548
549impl<T: Scalar> DMatrix<T> {
550    /// `self ← self + α·x` in place.
551    ///
552    /// # Panics
553    ///
554    /// Panics if the shapes differ.
555    pub fn axpy(&mut self, alpha: T, x: &DMatrix<T>) {
556        assert_eq!(
557            (self.nrows, self.ncols),
558            (x.nrows, x.ncols),
559            "axpy: shape mismatch"
560        );
561        for (s, &xi) in self.data.iter_mut().zip(&x.data) {
562            *s = *s + alpha * xi;
563        }
564    }
565
566    /// `y ← self · x`, written into the caller's buffer `y`.
567    ///
568    /// # Panics
569    ///
570    /// Panics if `x.len() != self.ncols()` or `y.len() != self.nrows()`.
571    pub fn mul_vector_into(&self, x: &DVector<T>, y: &mut DVector<T>) {
572        assert_eq!(
573            self.ncols,
574            x.len(),
575            "mul_vector_into: column/vector mismatch"
576        );
577        assert_eq!(
578            self.nrows,
579            y.len(),
580            "mul_vector_into: output length mismatch"
581        );
582        // Column-oriented accumulation: each column of `self` is contiguous.
583        for o in y.data.iter_mut() {
584            *o = T::zero();
585        }
586        for (k, &xk) in x.data.iter().enumerate() {
587            let col = &self.data[k * self.nrows..(k + 1) * self.nrows];
588            for (o, &aik) in y.data.iter_mut().zip(col) {
589                *o = *o + aik * xk;
590            }
591        }
592    }
593
594    /// `out ← self · rhs`, written into the caller's buffer `out`.
595    ///
596    /// # Panics
597    ///
598    /// Panics if the inner dimensions do not match or `out` is not
599    /// `self.nrows() × rhs.ncols()`.
600    pub fn mul_matrix_into(&self, rhs: &DMatrix<T>, out: &mut DMatrix<T>) {
601        assert_eq!(
602            self.ncols, rhs.nrows,
603            "mul_matrix_into: inner dimension mismatch"
604        );
605        assert_eq!(
606            (out.nrows, out.ncols),
607            (self.nrows, rhs.ncols),
608            "mul_matrix_into: output shape mismatch"
609        );
610        let m = self.nrows;
611        for j in 0..rhs.ncols {
612            let out_col = &mut out.data[j * m..(j + 1) * m];
613            for o in out_col.iter_mut() {
614                *o = T::zero();
615            }
616            for kk in 0..self.ncols {
617                let bkj = rhs.data[j * rhs.nrows + kk];
618                let a_col = &self.data[kk * m..(kk + 1) * m];
619                for (o, &aik) in out_col.iter_mut().zip(a_col) {
620                    *o = *o + aik * bkj;
621                }
622            }
623        }
624    }
625}
626
627macro_rules! impl_assign_ops {
628    ($type:ident) => {
629        impl<T: Scalar> core::ops::AddAssign<&$type<T>> for $type<T> {
630            /// # Panics
631            ///
632            /// Panics on a shape mismatch.
633            fn add_assign(&mut self, rhs: &$type<T>) {
634                self.axpy(T::one(), rhs);
635            }
636        }
637
638        impl<T: Scalar> core::ops::SubAssign<&$type<T>> for $type<T> {
639            /// # Panics
640            ///
641            /// Panics on a shape mismatch.
642            fn sub_assign(&mut self, rhs: &$type<T>) {
643                self.axpy(-T::one(), rhs);
644            }
645        }
646
647        impl<T: Scalar> core::ops::MulAssign<T> for $type<T> {
648            fn mul_assign(&mut self, rhs: T) {
649                for s in self.data.iter_mut() {
650                    *s = *s * rhs;
651                }
652            }
653        }
654
655        impl<T: Scalar> core::ops::DivAssign<T> for $type<T> {
656            fn div_assign(&mut self, rhs: T) {
657                for s in self.data.iter_mut() {
658                    *s = *s / rhs;
659                }
660            }
661        }
662    };
663}
664impl_assign_ops!(DVector);
665impl_assign_ops!(DMatrix);
666
667#[cfg(feature = "rayon")]
668impl DMatrix<f64> {
669    /// Matrix product `self · rhs`, with output columns computed in parallel.
670    ///
671    /// Each column is accumulated in the same order as the serial product, so
672    /// the result is bitwise equal to the serial scalar product. Without the `simd`
673    /// feature that is `self * rhs`; with it, `*` uses a BLAS kernel that
674    /// reassociates sums, so the two can differ by a few ulps. Only `f64` is
675    /// parallelised: the generic `Mul` impls cannot require `Send + Sync`
676    /// without breaking existing callers.
677    ///
678    /// # Panics
679    ///
680    /// Panics if the inner dimensions do not match.
681    pub fn par_mul(&self, rhs: &DMatrix<f64>) -> DMatrix<f64> {
682        use rayon::prelude::*;
683
684        assert_eq!(
685            self.ncols, rhs.nrows,
686            "inner dimensions do not match: {}x{} * {}x{}",
687            self.nrows, self.ncols, rhs.nrows, rhs.ncols
688        );
689        let (m, k, n) = (self.nrows, self.ncols, rhs.ncols);
690        let mut data = vec![0.0; m * n];
691        if m > 0 {
692            data.par_chunks_mut(m).enumerate().for_each(|(j, out_col)| {
693                for kk in 0..k {
694                    let bkj = rhs.data[j * rhs.nrows + kk];
695                    let a_col = &self.data[kk * m..(kk + 1) * m];
696                    for (o, &aik) in out_col.iter_mut().zip(a_col) {
697                        *o += aik * bkj;
698                    }
699                }
700            });
701        }
702        DMatrix {
703            nrows: m,
704            ncols: n,
705            data,
706        }
707    }
708}
709
710// ---------------------------------------------------------------------------
711// Matrix * matrix and matrix * vector
712// ---------------------------------------------------------------------------
713
714#[cfg(all(feature = "alloc", not(feature = "simd")))]
715impl<T: Scalar> Mul<DMatrix<T>> for DMatrix<T> {
716    type Output = DMatrix<T>;
717    /// # Panics
718    ///
719    /// Panics if the inner dimensions do not match.
720    fn mul(self, rhs: DMatrix<T>) -> DMatrix<T> {
721        mul_matrix_generic(&self, &rhs)
722    }
723}
724
725#[cfg(all(feature = "alloc", not(feature = "simd")))]
726impl<T: Scalar> Mul<DVector<T>> for DMatrix<T> {
727    type Output = DVector<T>;
728    /// # Panics
729    ///
730    /// Panics if the matrix column count does not match the vector length.
731    fn mul(self, rhs: DVector<T>) -> DVector<T> {
732        mul_vector_generic(&self, &rhs)
733    }
734}
735
736/// With the `simd` feature, `f32`/`f64` products use `tpt-simd-blas` (blocked
737/// FMA `gemm`; sums reassociate, so results can differ from the scalar loop by a
738/// few ulps). Other scalar types use the generic loop.
739#[cfg(feature = "simd")]
740impl<T: Scalar + 'static> Mul<DMatrix<T>> for DMatrix<T> {
741    type Output = DMatrix<T>;
742    /// # Panics
743    ///
744    /// Panics if the inner dimensions do not match.
745    fn mul(self, rhs: DMatrix<T>) -> DMatrix<T> {
746        assert_eq!(
747            self.ncols, rhs.nrows,
748            "inner dimensions do not match: {}x{} * {}x{}",
749            self.nrows, self.ncols, rhs.nrows, rhs.ncols
750        );
751        let (m, k, n) = (self.nrows, self.ncols, rhs.ncols);
752        if let (Some(a), Some(b)) = (simd::as_f64(&self.data), simd::as_f64(&rhs.data)) {
753            let mut c = vec![0.0f64; m * n];
754            tpt_simd_blas::gemm_f64(
755                m,
756                n,
757                k,
758                1.0,
759                a,
760                m.max(1),
761                b,
762                k.max(1),
763                0.0,
764                &mut c,
765                m.max(1),
766            );
767            return DMatrix {
768                nrows: m,
769                ncols: n,
770                data: simd::vec_from_f64(c),
771            };
772        }
773        if let (Some(a), Some(b)) = (simd::as_f32(&self.data), simd::as_f32(&rhs.data)) {
774            let mut c = vec![0.0f32; m * n];
775            tpt_simd_blas::gemm_f32(
776                m,
777                n,
778                k,
779                1.0,
780                a,
781                m.max(1),
782                b,
783                k.max(1),
784                0.0,
785                &mut c,
786                m.max(1),
787            );
788            return DMatrix {
789                nrows: m,
790                ncols: n,
791                data: simd::vec_from_f32(c),
792            };
793        }
794        mul_matrix_generic(&self, &rhs)
795    }
796}
797
798#[cfg(feature = "simd")]
799impl<T: Scalar + 'static> Mul<DVector<T>> for DMatrix<T> {
800    type Output = DVector<T>;
801    /// # Panics
802    ///
803    /// Panics if the matrix column count does not match the vector length.
804    fn mul(self, rhs: DVector<T>) -> DVector<T> {
805        assert_eq!(
806            self.ncols,
807            rhs.len(),
808            "matrix has {} columns but vector has length {}",
809            self.ncols,
810            rhs.len()
811        );
812        let (m, n) = (self.nrows, self.ncols);
813        if let (Some(a), Some(x)) = (simd::as_f64(&self.data), simd::as_f64(&rhs.data)) {
814            let mut y = vec![0.0f64; m];
815            tpt_simd_blas::gemv_f64(m, n, 1.0, a, m.max(1), x, 0.0, &mut y);
816            return DVector {
817                data: simd::vec_from_f64(y),
818            };
819        }
820        if let (Some(a), Some(x)) = (simd::as_f32(&self.data), simd::as_f32(&rhs.data)) {
821            let mut y = vec![0.0f32; m];
822            tpt_simd_blas::gemv_f32(m, n, 1.0, a, m.max(1), x, 0.0, &mut y);
823            return DVector {
824                data: simd::vec_from_f32(y),
825            };
826        }
827        mul_vector_generic(&self, &rhs)
828    }
829}
830
831#[cfg(feature = "alloc")]
832fn mul_matrix_generic<T: Scalar>(a: &DMatrix<T>, b: &DMatrix<T>) -> DMatrix<T> {
833    assert_eq!(
834        a.ncols, b.nrows,
835        "inner dimensions do not match: {}x{} * {}x{}",
836        a.nrows, a.ncols, b.nrows, b.ncols
837    );
838    let m = a.nrows;
839    let k = a.ncols;
840    let n = b.ncols;
841    // j-k-i order: column-major storage means the inner loop walks contiguous
842    // columns of `a` and of the output.
843    let mut data = vec![T::zero(); m * n];
844    for j in 0..n {
845        let out_col = &mut data[j * m..(j + 1) * m];
846        for kk in 0..k {
847            let bkj = b[(kk, j)];
848            let a_col = &a.data[kk * m..(kk + 1) * m];
849            for (o, &aik) in out_col.iter_mut().zip(a_col) {
850                *o = *o + aik * bkj;
851            }
852        }
853    }
854    DMatrix {
855        nrows: m,
856        ncols: n,
857        data,
858    }
859}
860
861#[cfg(feature = "alloc")]
862fn mul_vector_generic<T: Scalar>(a: &DMatrix<T>, x: &DVector<T>) -> DVector<T> {
863    assert_eq!(
864        a.ncols,
865        x.len(),
866        "matrix has {} columns but vector has length {}",
867        a.ncols,
868        x.len()
869    );
870    let m = a.nrows;
871    let k = a.ncols;
872    DVector::from_fn(m, |i| {
873        let mut s = T::zero();
874        for kk in 0..k {
875            s = s + a[(i, kk)] * x[kk];
876        }
877        s
878    })
879}
880
881/// `Any`-based `f32`/`f64` detection (safe; no `unsafe` needed).
882#[cfg(feature = "simd")]
883mod simd {
884    use alloc::boxed::Box;
885    use alloc::vec::Vec;
886    use core::any::Any;
887    use tpt_math_numeric::Scalar;
888
889    #[allow(clippy::ptr_arg)] // `Any` downcasting needs the concrete `Vec<T>`
890    pub(crate) fn as_f64<T: 'static>(v: &Vec<T>) -> Option<&[f64]> {
891        (v as &dyn Any)
892            .downcast_ref::<Vec<f64>>()
893            .map(|v| v.as_slice())
894    }
895    #[allow(clippy::ptr_arg)]
896    pub(crate) fn as_f32<T: 'static>(v: &Vec<T>) -> Option<&[f32]> {
897        (v as &dyn Any)
898            .downcast_ref::<Vec<f32>>()
899            .map(|v| v.as_slice())
900    }
901    pub(crate) fn vec_from_f64<T: 'static>(v: Vec<f64>) -> Vec<T> {
902        *(Box::new(v) as Box<dyn Any>)
903            .downcast::<Vec<T>>()
904            .unwrap_or_else(|_| unreachable!("checked by as_f64"))
905    }
906    pub(crate) fn vec_from_f32<T: 'static>(v: Vec<f32>) -> Vec<T> {
907        *(Box::new(v) as Box<dyn Any>)
908            .downcast::<Vec<T>>()
909            .unwrap_or_else(|_| unreachable!("checked by as_f32"))
910    }
911    pub(crate) fn from_f64<T: Scalar + 'static>(x: f64) -> T {
912        *(Box::new(x) as Box<dyn Any>)
913            .downcast::<T>()
914            .unwrap_or_else(|_| unreachable!("checked by as_f64"))
915    }
916    pub(crate) fn from_f32<T: Scalar + 'static>(x: f32) -> T {
917        *(Box::new(x) as Box<dyn Any>)
918            .downcast::<T>()
919            .unwrap_or_else(|_| unreachable!("checked by as_f32"))
920    }
921}
922
923// ---------------------------------------------------------------------------
924// Equality + Debug
925// ---------------------------------------------------------------------------
926
927impl<T: PartialEq> PartialEq for DVector<T> {
928    fn eq(&self, other: &Self) -> bool {
929        self.data == other.data
930    }
931}
932
933impl<T: PartialEq> PartialEq for DMatrix<T> {
934    fn eq(&self, other: &Self) -> bool {
935        self.nrows == other.nrows && self.ncols == other.ncols && self.data == other.data
936    }
937}
938
939impl<T: fmt::Debug> fmt::Debug for DVector<T> {
940    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
941        f.debug_list().entries(self.iter()).finish()
942    }
943}
944
945impl<T: fmt::Debug> fmt::Debug for DMatrix<T> {
946    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
947        f.debug_struct("DMatrix")
948            .field("nrows", &self.nrows)
949            .field("ncols", &self.ncols)
950            .finish()
951    }
952}
953
954// ---------------------------------------------------------------------------
955// Fallible dense solve / inverse (partial-pivot LU over the in-house storage)
956// ---------------------------------------------------------------------------
957
958/// Errors returned by the fallible dense linear-algebra routines.
959#[cfg(feature = "alloc")]
960#[derive(Debug, Clone, PartialEq)]
961#[non_exhaustive]
962pub enum DenseError {
963    /// The matrix is (numerically) singular and cannot be inverted/solved.
964    Singular {
965        /// Which routine detected the singular matrix.
966        what: &'static str,
967    },
968    /// A dimension mismatch between operands.
969    DimensionMismatch {
970        /// Human-readable description of the conflict.
971        what: String,
972    },
973    /// An iterative routine hit its sweep budget before converging, for example
974    /// because the input contains NaN or infinity.
975    NoConvergence {
976        /// Which routine failed to converge.
977        what: &'static str,
978    },
979}
980
981#[cfg(feature = "alloc")]
982impl fmt::Display for DenseError {
983    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
984        match self {
985            DenseError::Singular { what } => write!(f, "singular matrix in {what}"),
986            DenseError::DimensionMismatch { what } => write!(f, "dimension mismatch: {what}"),
987            DenseError::NoConvergence { what } => write!(f, "{what} did not converge"),
988        }
989    }
990}
991
992#[cfg(feature = "alloc")]
993impl core::error::Error for DenseError {}
994
995#[cfg(feature = "alloc")]
996impl DMatrix<f64> {
997    /// Solve `A x = b` for `x`, where `A` is `self`. Errors if `A` is singular
998    /// or the dimensions do not match.
999    pub fn solve(&self, b: &DVector<f64>) -> Result<DVector<f64>, DenseError> {
1000        let n = self.nrows;
1001        if self.ncols != n {
1002            return Err(DenseError::DimensionMismatch {
1003                what: format!("matrix is {}x{}, expected square", n, self.ncols),
1004            });
1005        }
1006        if b.len() != n {
1007            return Err(DenseError::DimensionMismatch {
1008                what: format!("rhs has length {}, expected {n}", b.len()),
1009            });
1010        }
1011
1012        let (lu, piv) = partial_pivot_lu(self)?;
1013        let x = solve_with_lu(&lu, &piv, b);
1014        Ok(DVector::from_vec(x))
1015    }
1016
1017    /// Compute the inverse of `self`. Errors if `self` is singular.
1018    pub fn inverse(&self) -> Result<DMatrix<f64>, DenseError> {
1019        let n = self.nrows;
1020        if self.ncols != n {
1021            return Err(DenseError::DimensionMismatch {
1022                what: format!("matrix is {}x{}, expected square", n, self.ncols),
1023            });
1024        }
1025        let factor = Lu::new(self)?;
1026        let identity = DMatrix::from_fn(n, n, |i, j| if i == j { 1.0 } else { 0.0 });
1027        factor.solve_matrix(&identity)
1028    }
1029}
1030
1031/// A reusable LU factorisation `P A = L U` of a square matrix.
1032///
1033/// Factor once with [`Lu::new`], then solve any number of right-hand sides with
1034/// [`Lu::solve`] at O(n²) per solve instead of refactoring at O(n³) each time.
1035#[cfg(feature = "alloc")]
1036#[derive(Clone, Debug)]
1037pub struct Lu {
1038    /// Flat row-major `n × n` factors; see [`partial_pivot_lu_with`].
1039    lu: Vec<f64>,
1040    piv: Vec<usize>,
1041}
1042
1043#[cfg(feature = "alloc")]
1044impl Lu {
1045    /// Factor the square matrix `m`.
1046    ///
1047    /// A pivot is treated as zero when it is below `1e-12` times the largest
1048    /// entry magnitude of `m`, so the test is scale-invariant. This is also the
1049    /// threshold used by [`DMatrix::solve`], [`DMatrix::inverse`] and
1050    /// [`DMatrix::det`].
1051    ///
1052    /// # Errors
1053    ///
1054    /// Returns [`DenseError::DimensionMismatch`] if `m` is not square, and
1055    /// [`DenseError::Singular`] if it is numerically singular.
1056    pub fn new(m: &DMatrix<f64>) -> Result<Self, DenseError> {
1057        if m.nrows != m.ncols {
1058            return Err(DenseError::DimensionMismatch {
1059                what: format!("matrix is {}x{}, expected square", m.nrows, m.ncols),
1060            });
1061        }
1062        let (lu, piv) = partial_pivot_lu(m)?;
1063        Ok(Lu { lu, piv })
1064    }
1065
1066    /// Factor `m`, treating a pivot as singular when its magnitude is below
1067    /// `tol` (an absolute threshold).
1068    ///
1069    /// Use this to pin the threshold explicitly, for example to keep the absolute
1070    /// `1e-12` that [`Lu::new`] used before it became relative. `tol = 0.0`
1071    /// accepts any non-zero finite pivot.
1072    ///
1073    /// # Errors
1074    ///
1075    /// Returns [`DenseError::DimensionMismatch`] if `m` is not square, and
1076    /// [`DenseError::Singular`] if a pivot falls below `tol`.
1077    pub fn with_pivot_tolerance(m: &DMatrix<f64>, tol: f64) -> Result<Self, DenseError> {
1078        if m.nrows != m.ncols {
1079            return Err(DenseError::DimensionMismatch {
1080                what: format!("matrix is {}x{}, expected square", m.nrows, m.ncols),
1081            });
1082        }
1083        let (lu, piv) = partial_pivot_lu_with(m, tol)?;
1084        Ok(Lu { lu, piv })
1085    }
1086
1087    /// Factor `m`, treating a pivot as singular when it is below `rel` times the
1088    /// largest entry magnitude of `m`.
1089    ///
1090    /// This makes the singularity test scale-invariant: `A` and `1e-14 · A` are
1091    /// accepted or rejected together. A zero matrix is always singular.
1092    ///
1093    /// # Errors
1094    ///
1095    /// As [`Lu::with_pivot_tolerance`].
1096    pub fn with_relative_tolerance(m: &DMatrix<f64>, rel: f64) -> Result<Self, DenseError> {
1097        let scale = m.iter().fold(0.0_f64, |acc, v| acc.max(v.abs()));
1098        Self::with_pivot_tolerance(m, rel * scale)
1099    }
1100
1101    /// The dimension `n` of the factored `n × n` matrix.
1102    pub fn dim(&self) -> usize {
1103        self.piv.len()
1104    }
1105
1106    /// Solve `A x = b` using the stored factorisation.
1107    ///
1108    /// # Errors
1109    ///
1110    /// Returns [`DenseError::DimensionMismatch`] if `b.len() != dim()`.
1111    pub fn solve(&self, b: &DVector<f64>) -> Result<DVector<f64>, DenseError> {
1112        let n = self.dim();
1113        if b.len() != n {
1114            return Err(DenseError::DimensionMismatch {
1115                what: format!("rhs has length {}, expected {n}", b.len()),
1116            });
1117        }
1118        Ok(DVector::from_vec(solve_with_lu(&self.lu, &self.piv, b)))
1119    }
1120
1121    /// Solve `A X = B` for every column of `b` with the stored factorisation.
1122    ///
1123    /// The factors are reused across columns, so this costs O(n²) per column
1124    /// rather than a fresh factorisation per column.
1125    ///
1126    /// # Errors
1127    ///
1128    /// Returns [`DenseError::DimensionMismatch`] if `b` does not have `dim()` rows.
1129    pub fn solve_matrix(&self, b: &DMatrix<f64>) -> Result<DMatrix<f64>, DenseError> {
1130        let n = self.dim();
1131        if b.nrows() != n {
1132            return Err(DenseError::DimensionMismatch {
1133                what: format!("rhs has {} rows, expected {n}", b.nrows()),
1134            });
1135        }
1136        #[cfg(feature = "simd-runtime")]
1137        {
1138            if n >= SIMD_DENSE_CUTOFF {
1139                return simd_lu::solve_matrix(&self.lu, &self.piv, b);
1140            }
1141        }
1142        let mut out = Vec::with_capacity(n * b.ncols());
1143        for col in 0..b.ncols() {
1144            let column = DVector::from_fn(n, |i| b[(i, col)]);
1145            out.extend(solve_with_lu(&self.lu, &self.piv, &column));
1146        }
1147        // Column-major output, matching `DMatrix::from_vec`.
1148        Ok(DMatrix::from_vec(n, b.ncols(), out))
1149    }
1150}
1151
1152/// A Householder QR factorisation `A = Q R` of a tall (`m ≥ n`) matrix, used
1153/// for least-squares solves. `Q` is kept implicitly as its reflectors.
1154#[cfg(feature = "alloc")]
1155#[derive(Clone, Debug)]
1156pub struct Qr {
1157    m: usize,
1158    n: usize,
1159    /// Upper-triangular `R`, flat and row-major: entry `(i, j)` is `r[i*n + j]`.
1160    r: Vec<f64>,
1161    /// Reflectors `(k, v, vᵀv)` acting on rows `k..m`, in application order.
1162    reflectors: Vec<(usize, Vec<f64>, f64)>,
1163}
1164
1165#[cfg(feature = "alloc")]
1166impl Qr {
1167    /// Factor `a` (with `nrows ≥ ncols`).
1168    ///
1169    /// # Errors
1170    ///
1171    /// Returns [`DenseError::DimensionMismatch`] if `a` has fewer rows than
1172    /// columns, and [`DenseError::Singular`] if `a` is rank deficient.
1173    pub fn new(a: &DMatrix<f64>) -> Result<Self, DenseError> {
1174        let (m, n) = (a.nrows, a.ncols);
1175        if m < n {
1176            return Err(DenseError::DimensionMismatch {
1177                what: format!("QR needs nrows >= ncols, got {m}x{n}"),
1178            });
1179        }
1180        // Flat row-major working copy: entry (i, j) is `w[i*n + j]`.
1181        let mut w: Vec<f64> = (0..m * n).map(|idx| a[(idx / n, idx % n)]).collect();
1182        let mut reflectors = Vec::with_capacity(n);
1183        for k in 0..n {
1184            let norm = (k..m).map(|i| w[i * n + k] * w[i * n + k]).sum::<f64>();
1185            let norm = sqrt_f64(norm);
1186            if norm == 0.0 {
1187                continue;
1188            }
1189            // Choose the sign that avoids cancellation in v = x - alpha e1.
1190            let alpha = if w[k * n + k] > 0.0 { -norm } else { norm };
1191            let mut v: Vec<f64> = (k..m).map(|i| w[i * n + k]).collect();
1192            v[0] -= alpha;
1193            let vtv: f64 = v.iter().map(|x| x * x).sum();
1194            if vtv == 0.0 {
1195                continue;
1196            }
1197            for j in k..n {
1198                let dot: f64 = v
1199                    .iter()
1200                    .enumerate()
1201                    .map(|(t, vt)| vt * w[(k + t) * n + j])
1202                    .sum();
1203                let f = 2.0 * dot / vtv;
1204                for (t, vt) in v.iter().enumerate() {
1205                    w[(k + t) * n + j] -= f * vt;
1206                }
1207            }
1208            reflectors.push((k, v, vtv));
1209        }
1210        let r: Vec<f64> = (0..n * n)
1211            .map(|idx| {
1212                let (i, j) = (idx / n, idx % n);
1213                if j >= i {
1214                    w[i * n + j]
1215                } else {
1216                    0.0
1217                }
1218            })
1219            .collect();
1220        let scale = r.iter().fold(0.0_f64, |acc, x| acc.max(x.abs()));
1221        let tol = (n as f64) * f64::EPSILON * scale;
1222        if (0..n).any(|i| {
1223            let d = r[i * n + i].abs();
1224            d.is_nan() || d <= tol
1225        }) {
1226            return Err(DenseError::Singular { what: "Qr::new" });
1227        }
1228        Ok(Qr {
1229            m,
1230            n,
1231            r,
1232            reflectors,
1233        })
1234    }
1235
1236    /// Solve the least-squares problem `min ‖A x − b‖₂`.
1237    ///
1238    /// # Errors
1239    ///
1240    /// Returns [`DenseError::DimensionMismatch`] if `b.len() != nrows`.
1241    pub fn solve_least_squares(&self, b: &DVector<f64>) -> Result<DVector<f64>, DenseError> {
1242        if b.len() != self.m {
1243            return Err(DenseError::DimensionMismatch {
1244                what: format!("rhs has length {}, expected {}", b.len(), self.m),
1245            });
1246        }
1247        // y = Qᵀ b by applying the reflectors in order.
1248        let mut y: Vec<f64> = b.iter().copied().collect();
1249        for (k, v, vtv) in &self.reflectors {
1250            let dot: f64 = v.iter().enumerate().map(|(t, vt)| vt * y[k + t]).sum();
1251            let f = 2.0 * dot / vtv;
1252            for (t, vt) in v.iter().enumerate() {
1253                y[k + t] -= f * vt;
1254            }
1255        }
1256        // Back-substitute R x = y[..n].
1257        let n = self.n;
1258        let mut x = vec![0.0_f64; n];
1259        for i in (0..n).rev() {
1260            let mut s = y[i];
1261            for j in (i + 1)..n {
1262                s -= self.r[i * n + j] * x[j];
1263            }
1264            x[i] = s / self.r[i * n + i];
1265        }
1266        Ok(DVector::from_vec(x))
1267    }
1268}
1269
1270#[cfg(feature = "alloc")]
1271impl DMatrix<f64> {
1272    /// Determinant, from the LU factorisation.
1273    ///
1274    /// Singularity is judged relative to the largest entry (see
1275    /// [`Lu::new`]), so a well-conditioned matrix of small scale such as
1276    /// `1e-13 · I` has its true determinant. A numerically singular matrix
1277    /// has determinant `0.0`.
1278    ///
1279    /// # Errors
1280    ///
1281    /// Returns [`DenseError::DimensionMismatch`] if the matrix is not square.
1282    pub fn det(&self) -> Result<f64, DenseError> {
1283        if self.nrows != self.ncols {
1284            return Err(DenseError::DimensionMismatch {
1285                what: format!("matrix is {}x{}, expected square", self.nrows, self.ncols),
1286            });
1287        }
1288        match partial_pivot_lu(self) {
1289            Ok((lu, piv)) => {
1290                // Sign of the row permutation, from its cycle count.
1291                let n = piv.len();
1292                let mut seen = vec![false; n];
1293                let mut cycles = 0;
1294                for start in 0..n {
1295                    if !seen[start] {
1296                        cycles += 1;
1297                        let mut k = start;
1298                        while !seen[k] {
1299                            seen[k] = true;
1300                            k = piv[k];
1301                        }
1302                    }
1303                }
1304                let sign = if (n - cycles) % 2 == 0 { 1.0 } else { -1.0 };
1305                Ok(sign * (0..n).map(|i| lu[i * n + i]).product::<f64>())
1306            }
1307            Err(DenseError::Singular { .. }) => Ok(0.0),
1308            Err(e) => Err(e),
1309        }
1310    }
1311
1312    /// Cholesky factorisation `A = L Lᵀ` of a symmetric positive-definite
1313    /// matrix, returning the lower-triangular `L`. Only the lower triangle of
1314    /// `self` is read.
1315    ///
1316    /// # Errors
1317    ///
1318    /// Returns [`DenseError::DimensionMismatch`] if the matrix is not square, and
1319    /// [`DenseError::Singular`] if it is not positive definite.
1320    pub fn cholesky(&self) -> Result<DMatrix<f64>, DenseError> {
1321        let n = self.nrows;
1322        if self.ncols != n {
1323            return Err(DenseError::DimensionMismatch {
1324                what: format!("matrix is {}x{}, expected square", n, self.ncols),
1325            });
1326        }
1327        #[cfg(feature = "simd-runtime")]
1328        {
1329            if n >= SIMD_DENSE_CUTOFF {
1330                return simd_chol::factor(self);
1331            }
1332        }
1333        scalar_cholesky(self)
1334    }
1335}
1336
1337/// The portable Cholesky kernel behind [`DMatrix::cholesky`].
1338#[cfg(feature = "alloc")]
1339fn scalar_cholesky(a: &DMatrix<f64>) -> Result<DMatrix<f64>, DenseError> {
1340    let n = a.nrows;
1341    // Flat row-major factor. Row i of `L` is `l[i*n..i*n + n]`, so each inner
1342    // sum is a dot product of two contiguous slices.
1343    let mut l = vec![0.0_f64; n * n];
1344    for j in 0..n {
1345        let row_j_head: f64 = l[j * n..j * n + j].iter().map(|x| x * x).sum();
1346        let d = a[(j, j)] - row_j_head;
1347        if d.is_nan() || d <= 0.0 {
1348            return Err(DenseError::Singular {
1349                what: "cholesky (not positive definite)",
1350            });
1351        }
1352        let ljj = sqrt_f64(d);
1353        l[j * n + j] = ljj;
1354        let (upto_i, from_i) = l.split_at_mut((j + 1) * n);
1355        let row_j = &upto_i[j * n..j * n + j];
1356        for (r, row_i) in from_i.chunks_exact_mut(n).enumerate() {
1357            let i = j + 1 + r;
1358            let dot: f64 = row_i[..j].iter().zip(row_j).map(|(a, b)| a * b).sum();
1359            row_i[j] = (a[(i, j)] - dot) / ljj;
1360        }
1361    }
1362    Ok(DMatrix::from_fn(n, n, |i, j| l[i * n + j]))
1363}
1364
1365#[cfg(feature = "alloc")]
1366impl DMatrix<f64> {
1367    /// Eigendecomposition of a symmetric matrix by the cyclic Jacobi method.
1368    ///
1369    /// Returns `(values, vectors)` with the eigenvalues in ascending order and
1370    /// the orthonormal eigenvectors as the columns of `vectors`, so that
1371    /// `A v_k = λ_k v_k`.
1372    ///
1373    /// # Errors
1374    ///
1375    /// Returns [`DenseError::DimensionMismatch`] if the matrix is not square or
1376    /// not symmetric (to a relative tolerance of `1e-12`).
1377    pub fn symmetric_eigen(&self) -> Result<(DVector<f64>, DMatrix<f64>), DenseError> {
1378        let n = self.nrows;
1379        if self.ncols != n {
1380            return Err(DenseError::DimensionMismatch {
1381                what: format!("matrix is {}x{}, expected square", n, self.ncols),
1382            });
1383        }
1384        let scale = self.iter().fold(0.0_f64, |acc, v| acc.max(v.abs()));
1385        let frob_sq: f64 = self.iter().map(|v| v * v).sum();
1386        for i in 0..n {
1387            for j in 0..i {
1388                if (self[(i, j)] - self[(j, i)]).abs() > 1e-12 * scale {
1389                    return Err(DenseError::DimensionMismatch {
1390                        what: "matrix is not symmetric".into(),
1391                    });
1392                }
1393            }
1394        }
1395        let mut a: Vec<Vec<f64>> = (0..n)
1396            .map(|i| (0..n).map(|j| self[(i, j)]).collect())
1397            .collect();
1398        let mut v: Vec<Vec<f64>> = (0..n)
1399            .map(|i| (0..n).map(|j| if i == j { 1.0 } else { 0.0 }).collect())
1400            .collect();
1401
1402        for _sweep in 0..100 {
1403            let off: f64 = (0..n)
1404                .flat_map(|p| ((p + 1)..n).map(move |q| (p, q)))
1405                .map(|(p, q)| a[p][q] * a[p][q])
1406                .sum();
1407            // Stop once the off-diagonal part is at rounding level relative to
1408            // ‖A‖_F, so tiny matrices such as [[0, 1e-16], [1e-16, 0]] still rotate.
1409            if off <= f64::EPSILON * f64::EPSILON * frob_sq {
1410                break;
1411            }
1412            for p in 0..n {
1413                for q in (p + 1)..n {
1414                    if a[p][q] == 0.0 {
1415                        continue;
1416                    }
1417                    // Rotation angle that annihilates a[p][q].
1418                    let theta = (a[q][q] - a[p][p]) / (2.0 * a[p][q]);
1419                    let t = theta.signum() / (theta.abs() + sqrt_f64(theta * theta + 1.0));
1420                    let t = if theta == 0.0 { 1.0 } else { t };
1421                    let c = 1.0 / sqrt_f64(t * t + 1.0);
1422                    let s = t * c;
1423                    // A ← Pᵀ A P, with P the Givens rotation in the (p, q) plane.
1424                    for k in 0..n {
1425                        let (akp, akq) = (a[k][p], a[k][q]);
1426                        a[k][p] = c * akp - s * akq;
1427                        a[k][q] = s * akp + c * akq;
1428                    }
1429                    for k in 0..n {
1430                        let (apk, aqk) = (a[p][k], a[q][k]);
1431                        a[p][k] = c * apk - s * aqk;
1432                        a[q][k] = s * apk + c * aqk;
1433                    }
1434                    for row in v.iter_mut() {
1435                        let (vkp, vkq) = (row[p], row[q]);
1436                        row[p] = c * vkp - s * vkq;
1437                        row[q] = s * vkp + c * vkq;
1438                    }
1439                }
1440            }
1441        }
1442
1443        let mut order: Vec<usize> = (0..n).collect();
1444        order.sort_by(|&i, &j| a[i][i].total_cmp(&a[j][j]));
1445        let values = DVector::from_vec(order.iter().map(|&k| a[k][k]).collect());
1446        let vectors = DMatrix::from_fn(n, n, |i, j| v[i][order[j]]);
1447        Ok((values, vectors))
1448    }
1449
1450    /// Least-squares solution of `min ‖self · x − b‖₂` via Householder QR.
1451    ///
1452    /// # Errors
1453    ///
1454    /// As [`Qr::new`] and [`Qr::solve_least_squares`].
1455    pub fn least_squares(&self, b: &DVector<f64>) -> Result<DVector<f64>, DenseError> {
1456        Qr::new(self)?.solve_least_squares(b)
1457    }
1458}
1459
1460/// Square root for `f64` that also works without `std`. The inherent
1461/// `f64::sqrt` is unavailable there, so this goes through `num-traits`, which
1462/// uses `libm` in that configuration.
1463#[cfg(feature = "alloc")]
1464fn sqrt_f64(x: f64) -> f64 {
1465    tpt_math_numeric::prelude::Float::sqrt(x)
1466}
1467
1468/// The factors `(U, σ, V)` of a thin singular value decomposition.
1469#[cfg(feature = "alloc")]
1470pub type SvdFactors = (DMatrix<f64>, DVector<f64>, DMatrix<f64>);
1471
1472/// Sweep budget for the one-sided Jacobi SVD. Each sweep is a full pass over
1473/// all column pairs; convergence is quadratic, so this is far more than needed.
1474#[cfg(feature = "alloc")]
1475const SVD_MAX_SWEEPS: usize = 60;
1476
1477/// Largest 1-norm for which the degree-13 Padé approximant meets unit-roundoff
1478/// accuracy without scaling (Higham 2005, θ₁₃). Above it the matrix is halved
1479/// until it is below.
1480#[cfg(feature = "alloc")]
1481const PADE13_THETA: f64 = 5.371_920_351_148_152;
1482
1483/// Rotates columns `p` and `q` of `cols` by the plane rotation `(c, s)`.
1484#[cfg(feature = "alloc")]
1485fn rotate_columns(cols: &mut [Vec<f64>], p: usize, q: usize, c: f64, s: f64) {
1486    let (lo, hi) = cols.split_at_mut(q);
1487    for (x, y) in lo[p].iter_mut().zip(hi[0].iter_mut()) {
1488        let (up, uq) = (*x, *y);
1489        *x = c * up - s * uq;
1490        *y = s * up + c * uq;
1491    }
1492}
1493
1494/// Dense matrix product for square operands of equal size.
1495#[cfg(feature = "alloc")]
1496fn matmul_square(a: &DMatrix<f64>, b: &DMatrix<f64>) -> DMatrix<f64> {
1497    let n = a.nrows();
1498    // The flat j-k-i kernel, rather than an indexed triple loop.
1499    let mut out = DMatrix::zeros(n, n);
1500    a.mul_matrix_into(b, &mut out);
1501    out
1502}
1503
1504#[cfg(feature = "alloc")]
1505impl DMatrix<f64> {
1506    /// Thin singular value decomposition `A = U · diag(σ) · Vᵀ`.
1507    ///
1508    /// For an `m × n` matrix with `k = min(m, n)`, returns `U` (`m × k`), the
1509    /// singular values `σ` (length `k`, sorted in descending order) and `V`
1510    /// (`n × k`), whose columns are orthonormal. Columns of `U` belonging to
1511    /// zero singular values are zero.
1512    ///
1513    /// Uses one-sided Jacobi rotations, which give high relative accuracy for
1514    /// small singular values. Works for any shape.
1515    ///
1516    /// # Errors
1517    ///
1518    /// Returns [`DenseError::NoConvergence`] if the rotations do not settle
1519    /// within the sweep budget, for example on NaN or infinite input.
1520    ///
1521    /// # Examples
1522    ///
1523    /// ```
1524    /// use tpt_math_linalg_dense::DMatrix;
1525    ///
1526    /// let a = DMatrix::from_row_slice(2, 2, &[3.0, 0.0, 0.0, -4.0]);
1527    /// let (_, s, _) = a.svd().unwrap();
1528    /// assert!((s[0] - 4.0).abs() < 1e-12 && (s[1] - 3.0).abs() < 1e-12);
1529    /// ```
1530    pub fn svd(&self) -> Result<SvdFactors, DenseError> {
1531        let (m, n) = (self.nrows(), self.ncols());
1532        if m < n {
1533            // A = (Aᵀ)ᵀ: decompose the transpose and swap the factors.
1534            let (u, s, v) = self.transpose().svd()?;
1535            return Ok((v, s, u));
1536        }
1537
1538        // Work column-wise: rotate pairs of columns of U = A until they are
1539        // mutually orthogonal, accumulating the rotations in V.
1540        let mut u: Vec<Vec<f64>> = (0..n)
1541            .map(|j| (0..m).map(|i| self[(i, j)]).collect())
1542            .collect();
1543        let mut v: Vec<Vec<f64>> = (0..n)
1544            .map(|j| (0..n).map(|i| if i == j { 1.0 } else { 0.0 }).collect())
1545            .collect();
1546        let mut converged = false;
1547        // Squared column norms. They are recomputed exactly at the start of each
1548        // sweep and then carried through the rotations, which costs one dot
1549        // product per pair (the cross term) instead of three.
1550        let mut norms: Vec<f64> = vec![0.0; n];
1551        for _ in 0..SVD_MAX_SWEEPS {
1552            for (j, col) in u.iter().enumerate() {
1553                norms[j] = col.iter().map(|x| x * x).sum();
1554            }
1555            let mut rotated = false;
1556            for p in 0..n {
1557                for q in (p + 1)..n {
1558                    let (alpha, beta) = (norms[p], norms[q]);
1559                    let gamma: f64 = u[p].iter().zip(&u[q]).map(|(x, y)| x * y).sum();
1560                    if gamma == 0.0 || gamma.abs() <= f64::EPSILON * sqrt_f64(alpha * beta) {
1561                        continue;
1562                    }
1563                    rotated = true;
1564                    let zeta = (beta - alpha) / (2.0 * gamma);
1565                    let t = zeta.signum() / (zeta.abs() + sqrt_f64(1.0 + zeta * zeta));
1566                    let c = 1.0 / sqrt_f64(1.0 + t * t);
1567                    let s = c * t;
1568                    rotate_columns(&mut u, p, q, c, s);
1569                    rotate_columns(&mut v, p, q, c, s);
1570                    // With the rotation chosen to annihilate the cross term, the new
1571                    // squared norms are α − tγ and β + tγ.
1572                    norms[p] = alpha - t * gamma;
1573                    norms[q] = beta + t * gamma;
1574                }
1575            }
1576            if !rotated {
1577                converged = true;
1578                break;
1579            }
1580        }
1581        if !converged {
1582            return Err(DenseError::NoConvergence { what: "svd" });
1583        }
1584
1585        // The column norms of the orthogonalised U are the singular values.
1586        let sigma: Vec<f64> = u
1587            .iter()
1588            .map(|col| {
1589                let sum: f64 = col.iter().map(|x| x * x).sum();
1590                sqrt_f64(sum)
1591            })
1592            .collect();
1593        let mut order: Vec<usize> = (0..n).collect();
1594        order.sort_by(|&a, &b| {
1595            sigma[b]
1596                .partial_cmp(&sigma[a])
1597                .unwrap_or(core::cmp::Ordering::Equal)
1598        });
1599
1600        let u_out = DMatrix::from_fn(m, n, |i, j| {
1601            let col = order[j];
1602            if sigma[col] > 0.0 {
1603                u[col][i] / sigma[col]
1604            } else {
1605                0.0
1606            }
1607        });
1608        let s_out = DVector::from_fn(n, |j| sigma[order[j]]);
1609        let v_out = DMatrix::from_fn(n, n, |i, j| v[order[j]][i]);
1610        Ok((u_out, s_out, v_out))
1611    }
1612
1613    /// The singular values, sorted in descending order.
1614    ///
1615    /// # Errors
1616    ///
1617    /// As [`DMatrix::svd`].
1618    pub fn singular_values(&self) -> Result<DVector<f64>, DenseError> {
1619        Ok(self.svd()?.1)
1620    }
1621
1622    /// Numerical rank: the number of singular values above
1623    /// `max(m, n) · σ_max · ε`, the usual tolerance for floating-point input.
1624    ///
1625    /// # Errors
1626    ///
1627    /// As [`DMatrix::svd`].
1628    pub fn rank(&self) -> Result<usize, DenseError> {
1629        let s = self.singular_values()?;
1630        let tol = self.rank_tolerance(&s);
1631        Ok(s.iter().filter(|&&x| x > tol).count())
1632    }
1633
1634    /// The 2-norm condition number `σ_max / σ_min`.
1635    ///
1636    /// Returns `∞` when the matrix is rank-deficient (`σ_min` is within the
1637    /// [`DMatrix::rank`] tolerance) and `1` for an empty matrix.
1638    ///
1639    /// # Errors
1640    ///
1641    /// As [`DMatrix::svd`].
1642    pub fn cond(&self) -> Result<f64, DenseError> {
1643        let s = self.singular_values()?;
1644        if s.is_empty() {
1645            return Ok(1.0);
1646        }
1647        let s_min = s[s.len() - 1];
1648        if s_min <= self.rank_tolerance(&s) {
1649            return Ok(f64::INFINITY);
1650        }
1651        Ok(s[0] / s_min)
1652    }
1653
1654    /// Moore–Penrose pseudo-inverse `A⁺ = V Σ⁺ Uᵀ`, from the thin SVD.
1655    ///
1656    /// Singular values at or below the [`DMatrix::rank`] tolerance are treated
1657    /// as zero, so rank-deficient and non-square matrices are handled. The
1658    /// result is `n × m` for an `m × n` input.
1659    ///
1660    /// # Errors
1661    ///
1662    /// As [`DMatrix::svd`].
1663    pub fn pseudo_inverse(&self) -> Result<DMatrix<f64>, DenseError> {
1664        let (m, n) = (self.nrows(), self.ncols());
1665        let (u, s, v) = self.svd()?;
1666        let tol = self.rank_tolerance(&s);
1667        let kept: Vec<usize> = (0..s.len()).filter(|&r| s[r] > tol).collect();
1668        Ok(DMatrix::from_fn(n, m, |i, j| {
1669            kept.iter().map(|&r| v[(i, r)] * u[(j, r)] / s[r]).sum()
1670        }))
1671    }
1672
1673    /// Minimum-norm least-squares solution of `min ‖A x − b‖₂`, which is
1674    /// `A⁺ b`. Unlike [`Qr::solve_least_squares`] it accepts rank-deficient
1675    /// and wide matrices, and among the minimisers it returns the one of least
1676    /// norm.
1677    ///
1678    /// # Errors
1679    ///
1680    /// Returns [`DenseError::DimensionMismatch`] if `b` does not have one entry
1681    /// per row, and as [`DMatrix::svd`] otherwise.
1682    pub fn solve_min_norm(&self, b: &DVector<f64>) -> Result<DVector<f64>, DenseError> {
1683        if b.len() != self.nrows() {
1684            return Err(DenseError::DimensionMismatch {
1685                what: format!("rhs has length {}, expected {}", b.len(), self.nrows()),
1686            });
1687        }
1688        let pinv = self.pseudo_inverse()?;
1689        Ok(DVector::from_fn(self.ncols(), |i| {
1690            (0..self.nrows()).map(|j| pinv[(i, j)] * b[j]).sum()
1691        }))
1692    }
1693
1694    fn rank_tolerance(&self, s: &DVector<f64>) -> f64 {
1695        let sigma_max = s.iter().copied().fold(0.0, f64::max);
1696        self.nrows().max(self.ncols()) as f64 * sigma_max * f64::EPSILON
1697    }
1698
1699    /// The matrix exponential `e^A`, by scaling and squaring.
1700    ///
1701    /// `A` is scaled by `2^-s` until its infinity norm is at most `1/2`, the
1702    /// Taylor series is summed on the scaled matrix, and the result is squared
1703    /// `s` times.
1704    ///
1705    /// # Errors
1706    ///
1707    /// A matrix with a NaN or infinite entry has no finite exponential, so the
1708    /// result is a matrix of NaNs.
1709    ///
1710    /// # Errors
1711    ///
1712    /// Returns [`DenseError::DimensionMismatch`] if the matrix is not square.
1713    pub fn matrix_exp(&self) -> Result<DMatrix<f64>, DenseError> {
1714        let n = self.nrows();
1715        if self.ncols() != n {
1716            return Err(DenseError::DimensionMismatch {
1717                what: format!("matrix_exp needs a square matrix, got {n}x{}", self.ncols()),
1718            });
1719        }
1720        if self.iter().any(|v| !v.is_finite()) {
1721            // Without this guard, an infinite norm makes the squaring loop below
1722            // run forever.
1723            return Ok(DMatrix::from_fn(n, n, |_, _| f64::NAN));
1724        }
1725        // Higham (2005), Padé approximant of degree 13 with scaling and squaring.
1726        // The 1-norm (largest absolute column sum) decides how far to scale.
1727        let norm = (0..n)
1728            .map(|j| (0..n).map(|i| self[(i, j)].abs()).sum::<f64>())
1729            .fold(0.0, f64::max);
1730        // Halve until the norm is at most θ₁₃: the count is ⌈log₂(norm/θ₁₃)⌉, found
1731        // without log2 or powi, which the no_std build does not have.
1732        let mut squarings = 0i32;
1733        let mut scaled_norm = norm;
1734        let mut scale = 1.0_f64;
1735        while scaled_norm > PADE13_THETA {
1736            scaled_norm *= 0.5;
1737            scale *= 0.5;
1738            squarings += 1;
1739        }
1740        let a = DMatrix::from_fn(n, n, |i, j| self[(i, j)] * scale);
1741
1742        let identity = DMatrix::from_fn(n, n, |i, j| if i == j { 1.0 } else { 0.0 });
1743        let a2 = matmul_square(&a, &a);
1744        let a4 = matmul_square(&a2, &a2);
1745        let a6 = matmul_square(&a4, &a2);
1746        let lin = |terms: &[(f64, &DMatrix<f64>)]| {
1747            DMatrix::from_fn(n, n, |i, j| terms.iter().map(|(c, m)| c * m[(i, j)]).sum())
1748        };
1749        const B: [f64; 14] = [
1750            64_764_752_532_480_000.0,
1751            32_382_376_266_240_000.0,
1752            7_771_770_303_897_600.0,
1753            1_187_353_796_428_800.0,
1754            129_060_195_264_000.0,
1755            10_559_470_521_600.0,
1756            670_442_572_800.0,
1757            33_522_128_640.0,
1758            1_323_241_920.0,
1759            40_840_800.0,
1760            960_960.0,
1761            16_380.0,
1762            182.0,
1763            1.0,
1764        ];
1765        // U = A [A⁶(b₁₃A⁶ + b₁₁A⁴ + b₉A²) + b₇A⁶ + b₅A⁴ + b₃A² + b₁I]
1766        let inner_u = lin(&[(B[13], &a6), (B[11], &a4), (B[9], &a2)]);
1767        // One scratch buffer serves every intermediate product, not a new matrix each time.
1768        let mut scratch = DMatrix::zeros(n, n);
1769        a6.mul_matrix_into(&inner_u, &mut scratch);
1770        let u_poly = lin(&[
1771            (1.0, &scratch),
1772            (B[7], &a6),
1773            (B[5], &a4),
1774            (B[3], &a2),
1775            (B[1], &identity),
1776        ]);
1777        let u = matmul_square(&a, &u_poly);
1778        // V = A⁶(b₁₂A⁶ + b₁₀A⁴ + b₈A²) + b₆A⁶ + b₄A⁴ + b₂A² + b₀I
1779        let inner_v = lin(&[(B[12], &a6), (B[10], &a4), (B[8], &a2)]);
1780        a6.mul_matrix_into(&inner_v, &mut scratch);
1781        let v = lin(&[
1782            (1.0, &scratch),
1783            (B[6], &a6),
1784            (B[4], &a4),
1785            (B[2], &a2),
1786            (B[0], &identity),
1787        ]);
1788        // exp(A) ≈ (V − U)⁻¹ (V + U)
1789        let p = lin(&[(1.0, &v), (1.0, &u)]);
1790        let q = lin(&[(1.0, &v), (-1.0, &u)]);
1791        let mut result = Lu::new(&q)?.solve_matrix(&p)?;
1792        for _ in 0..squarings {
1793            result.mul_matrix_into(&result, &mut scratch);
1794            core::mem::swap(&mut result, &mut scratch);
1795        }
1796        Ok(result)
1797    }
1798}
1799
1800/// Default singularity threshold, relative to the largest entry magnitude of the
1801/// matrix being factored. A pivot below `DEFAULT_PIVOT_RELATIVE · max|a_ij|` is
1802/// treated as zero.
1803#[cfg(feature = "alloc")]
1804const DEFAULT_PIVOT_RELATIVE: f64 = 1e-12;
1805
1806/// Returns the LU factorization (in place) and the row permutation, using the
1807/// default relative pivot tolerance.
1808#[cfg(feature = "alloc")]
1809fn partial_pivot_lu(m: &DMatrix<f64>) -> Result<(Vec<f64>, Vec<usize>), DenseError> {
1810    let scale = m.iter().fold(0.0_f64, |acc, v| acc.max(v.abs()));
1811    partial_pivot_lu_with(m, DEFAULT_PIVOT_RELATIVE * scale)
1812}
1813
1814/// [`partial_pivot_lu`] with an explicit absolute pivot tolerance.
1815///
1816/// The factors are returned as one flat row-major buffer of `n × n` entries,
1817/// with `L` below the diagonal (unit diagonal implied) and `U` on and above it.
1818/// Elimination works on whole row slices, so the inner loop is contiguous and
1819/// vectorises.
1820#[cfg(feature = "alloc")]
1821fn partial_pivot_lu_with(m: &DMatrix<f64>, tol: f64) -> Result<(Vec<f64>, Vec<usize>), DenseError> {
1822    #[cfg(feature = "simd-runtime")]
1823    {
1824        if m.nrows >= SIMD_DENSE_CUTOFF {
1825            return simd_lu::factor(m, tol);
1826        }
1827    }
1828    scalar_lu(m, tol)
1829}
1830
1831/// Dimension from which the `simd` feature factors with `tpt-simd-blas`. Below
1832/// this the scalar loop is as fast, and the conversion overhead is not repaid.
1833#[cfg(feature = "simd-runtime")]
1834const SIMD_DENSE_CUTOFF: usize = 64;
1835
1836/// The portable LU kernel behind [`partial_pivot_lu_with`].
1837#[cfg(feature = "alloc")]
1838fn scalar_lu(m: &DMatrix<f64>, tol: f64) -> Result<(Vec<f64>, Vec<usize>), DenseError> {
1839    let n = m.nrows;
1840    let mut a: Vec<f64> = Vec::with_capacity(n * n);
1841    for i in 0..n {
1842        for j in 0..n {
1843            a.push(m[(i, j)]);
1844        }
1845    }
1846    let mut piv: Vec<usize> = (0..n).collect();
1847
1848    for k in 0..n {
1849        let mut p = k;
1850        let mut max = a[k * n + k].abs();
1851        for i in (k + 1)..n {
1852            let v = a[i * n + k].abs();
1853            if v > max {
1854                max = v;
1855                p = i;
1856            }
1857        }
1858        if !max.is_finite() || max == 0.0 || max < tol {
1859            return Err(DenseError::Singular {
1860                what: "partial_pivot_lu",
1861            });
1862        }
1863        if p != k {
1864            for j in 0..n {
1865                a.swap(k * n + j, p * n + j);
1866            }
1867            piv.swap(k, p);
1868        }
1869        let (top, bottom) = a.split_at_mut((k + 1) * n);
1870        let row_k = &top[k * n..];
1871        let pivot = row_k[k];
1872        for row_i in bottom.chunks_exact_mut(n) {
1873            let factor = row_i[k] / pivot;
1874            row_i[k] = factor;
1875            for (x, &u) in row_i[k + 1..].iter_mut().zip(&row_k[k + 1..]) {
1876                *x -= factor * u;
1877            }
1878        }
1879    }
1880    Ok((a, piv))
1881}
1882
1883/// Solve `A x = b` given an already-computed partial-pivot LU factorization.
1884#[cfg(feature = "alloc")]
1885fn solve_with_lu(lu: &[f64], piv: &[usize], b: &DVector<f64>) -> Vec<f64> {
1886    let n = piv.len();
1887    // Forward solve L y = P b. Row i of the flat buffer holds L[i][..i] first.
1888    let mut y = vec![0.0_f64; n];
1889    for i in 0..n {
1890        let row = &lu[i * n..i * n + i];
1891        let dot: f64 = row.iter().zip(&y[..i]).map(|(l, yj)| l * yj).sum();
1892        y[i] = b[piv[i]] - dot;
1893    }
1894    // Back solve U x = y.
1895    let mut x = vec![0.0_f64; n];
1896    for i in (0..n).rev() {
1897        let row = &lu[i * n + i + 1..i * n + n];
1898        let dot: f64 = row.iter().zip(&x[i + 1..]).map(|(u, xj)| u * xj).sum();
1899        x[i] = (y[i] - dot) / lu[i * n + i];
1900    }
1901    x
1902}
1903
1904#[cfg(all(test, feature = "alloc"))]
1905mod tests {
1906    use super::*;
1907
1908    #[test]
1909    fn vector_construction_and_index() {
1910        let v = DVector::from_vec(vec![3.0_f64, 1.0, 4.0]);
1911        assert_eq!(v.len(), 3);
1912        assert_eq!(v[0], 3.0);
1913        assert_eq!(v[2], 4.0);
1914    }
1915
1916    #[test]
1917    fn vector_add_sub_neg_scalar() {
1918        let a = DVector::from_vec(vec![1.0_f64, 2.0, 3.0]);
1919        let b = DVector::from_vec(vec![4.0_f64, 5.0, 6.0]);
1920        let s = a.clone() + b.clone();
1921        assert_eq!(s, DVector::from_vec(vec![5.0, 7.0, 9.0]));
1922        let d = b.clone() - a.clone();
1923        assert_eq!(d, DVector::from_vec(vec![3.0, 3.0, 3.0]));
1924        let n = -a.clone();
1925        assert_eq!(n, DVector::from_vec(vec![-1.0, -2.0, -3.0]));
1926        let sc = a * 2.0;
1927        assert_eq!(sc, DVector::from_vec(vec![2.0, 4.0, 6.0]));
1928    }
1929
1930    #[test]
1931    fn vector_dot_and_norm() {
1932        let a = DVector::from_vec(vec![1.0_f64, 2.0, 3.0]);
1933        let b = DVector::from_vec(vec![4.0_f64, 5.0, 6.0]);
1934        assert!((a.dot(&b) - 32.0).abs() < 1e-12);
1935        assert!((a.norm() - 14.0_f64.sqrt()).abs() < 1e-12);
1936    }
1937
1938    #[test]
1939    fn matrix_construction_and_arithmetic() {
1940        let m = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 3.0, 4.0]);
1941        assert_eq!(m.nrows(), 2);
1942        assert_eq!(m.ncols(), 2);
1943        assert_eq!(m[(0, 0)], 1.0);
1944        assert_eq!(m[(1, 1)], 4.0);
1945        let z = DMatrix::zeros(2, 2);
1946        assert_eq!(m.clone() - m.clone(), z);
1947    }
1948
1949    #[test]
1950    fn matrix_vector_and_matrix_matrix() {
1951        let m = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 3.0, 4.0]);
1952        let v = DVector::from_vec(vec![1.0_f64, 1.0]);
1953        let mv = m.clone() * v;
1954        assert_eq!(mv, DVector::from_vec(vec![3.0, 7.0]));
1955
1956        let n = DMatrix::from_row_slice(2, 2, &[0.0_f64, 1.0, 1.0, 0.0]);
1957        let mm = m.clone() * n;
1958        assert_eq!(mm, DMatrix::from_row_slice(2, 2, &[2.0_f64, 1.0, 4.0, 3.0]));
1959    }
1960
1961    #[test]
1962    fn transpose_swaps_dimensions() {
1963        let m = DMatrix::from_row_slice(2, 3, &[1.0_f64, 2.0, 3.0, 4.0, 5.0, 6.0]);
1964        let t = m.transpose();
1965        assert_eq!(t.nrows(), 3);
1966        assert_eq!(t.ncols(), 2);
1967        assert_eq!(t[(0, 1)], 4.0);
1968    }
1969
1970    #[test]
1971    fn solve_and_inverse() {
1972        // A = [[2, 0], [0, 2]] -> inverse [[0.5, 0], [0, 0.5]]
1973        let a = DMatrix::from_row_slice(2, 2, &[2.0_f64, 0.0, 0.0, 2.0]);
1974        let inv = a.inverse().unwrap();
1975        assert!((inv[(0, 0)] - 0.5).abs() < 1e-12);
1976        assert!((inv[(1, 1)] - 0.5).abs() < 1e-12);
1977
1978        let b = DVector::from_vec(vec![4.0_f64, 6.0]);
1979        let x = a.solve(&b).unwrap();
1980        assert_eq!(x, DVector::from_vec(vec![2.0, 3.0]));
1981    }
1982
1983    #[test]
1984    fn determinant_known_values() {
1985        let a = DMatrix::from_row_slice(2, 2, &[4.0_f64, 1.0, 2.0, 3.0]);
1986        assert!((a.det().unwrap() - 10.0).abs() < 1e-12);
1987        let b = DMatrix::from_row_slice(3, 3, &[0.0_f64, 2.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 3.0]);
1988        // Row swap (sign −1) times 2·1·3.
1989        assert!((b.det().unwrap() + 6.0).abs() < 1e-12);
1990        let singular = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 2.0, 4.0]);
1991        assert_eq!(singular.det().unwrap(), 0.0);
1992        assert!(DMatrix::<f64>::zeros(2, 3).det().is_err());
1993    }
1994
1995    #[test]
1996    fn cholesky_reconstructs_and_rejects_indefinite() {
1997        let a = DMatrix::from_row_slice(2, 2, &[4.0_f64, 2.0, 2.0, 3.0]);
1998        let l = a.cholesky().unwrap();
1999        assert!((l[(0, 0)] - 2.0).abs() < 1e-12);
2000        assert!((l[(1, 0)] - 1.0).abs() < 1e-12);
2001        assert!((l[(1, 1)] - 2.0_f64.sqrt()).abs() < 1e-12);
2002        assert_eq!(l[(0, 1)], 0.0);
2003        let indefinite = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 2.0, 1.0]);
2004        assert!(indefinite.cholesky().is_err());
2005    }
2006
2007    #[test]
2008    fn symmetric_eigen_residuals_and_orthonormality() {
2009        let a = DMatrix::from_row_slice(3, 3, &[2.0_f64, 1.0, 0.5, 1.0, 3.0, -1.0, 0.5, -1.0, 1.0]);
2010        let (vals, vecs) = a.symmetric_eigen().unwrap();
2011        // Ascending order.
2012        assert!(vals[0] <= vals[1] && vals[1] <= vals[2]);
2013        for k in 0..3 {
2014            for i in 0..3 {
2015                let av: f64 = (0..3).map(|j| a[(i, j)] * vecs[(j, k)]).sum();
2016                assert!(
2017                    (av - vals[k] * vecs[(i, k)]).abs() < 1e-10,
2018                    "pair {k}, row {i}"
2019                );
2020            }
2021        }
2022        for p in 0..3 {
2023            for q in 0..3 {
2024                let dot: f64 = (0..3).map(|i| vecs[(i, p)] * vecs[(i, q)]).sum();
2025                let want = if p == q { 1.0 } else { 0.0 };
2026                assert!((dot - want).abs() < 1e-10);
2027            }
2028        }
2029        // The trace is the sum of the eigenvalues.
2030        assert!((vals.iter().sum::<f64>() - 6.0).abs() < 1e-10);
2031        let nonsym = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 0.0, 1.0]);
2032        assert!(nonsym.symmetric_eigen().is_err());
2033    }
2034
2035    #[test]
2036    fn least_squares_recovers_exact_line() {
2037        // y = 2x + 1 sampled exactly: the fit must be exact.
2038        let xs = [0.0_f64, 1.0, 2.0, 3.0, 4.0];
2039        let mut data = Vec::new();
2040        for &x in &xs {
2041            data.push(1.0);
2042            data.push(x);
2043        }
2044        let a = DMatrix::from_row_slice(5, 2, &data);
2045        let b = DVector::from_vec(xs.iter().map(|x| 2.0 * x + 1.0).collect());
2046        let coef = a.least_squares(&b).unwrap();
2047        assert!((coef[0] - 1.0).abs() < 1e-12, "intercept {}", coef[0]);
2048        assert!((coef[1] - 2.0).abs() < 1e-12, "slope {}", coef[1]);
2049    }
2050
2051    #[test]
2052    fn least_squares_satisfies_normal_equations() {
2053        // Noisy, overdetermined: the residual must be orthogonal to the columns,
2054        // i.e. Aᵀ(A x − b) = 0.
2055        let rows = 6;
2056        let a = DMatrix::from_fn(rows, 2, |i, j| if j == 0 { 1.0 } else { i as f64 });
2057        let b = DVector::from_vec(vec![1.1, 2.9, 5.2, 6.8, 9.1, 11.0]);
2058        let x = a.least_squares(&b).unwrap();
2059        for j in 0..2 {
2060            let mut g = 0.0;
2061            for i in 0..rows {
2062                let mut ri = -b[i];
2063                for k in 0..2 {
2064                    ri += a[(i, k)] * x[k];
2065                }
2066                g += a[(i, j)] * ri;
2067            }
2068            assert!(g.abs() < 1e-10, "column {j}: Aᵀr = {g}");
2069        }
2070    }
2071
2072    #[test]
2073    fn least_squares_rejects_rank_deficient_and_wide_systems() {
2074        // Two identical columns: rank 1.
2075        let a = DMatrix::from_row_slice(3, 2, &[1.0_f64, 1.0, 2.0, 2.0, 3.0, 3.0]);
2076        assert!(a
2077            .least_squares(&DVector::from_vec(vec![1.0, 2.0, 3.0]))
2078            .is_err());
2079        // More unknowns than equations.
2080        let wide = DMatrix::<f64>::zeros(2, 3);
2081        assert!(wide
2082            .least_squares(&DVector::from_vec(vec![1.0, 2.0]))
2083            .is_err());
2084    }
2085
2086    #[test]
2087    fn lu_factors_once_and_solves_many_right_hand_sides() {
2088        let a = DMatrix::from_row_slice(3, 3, &[4.0_f64, 1.0, 0.0, 1.0, 3.0, 1.0, 0.0, 1.0, 2.0]);
2089        let lu = Lu::new(&a).unwrap();
2090        for k in 0..4 {
2091            let b = DVector::from_vec(vec![1.0 + k as f64, 2.0, -1.0]);
2092            let x = lu.solve(&b).unwrap();
2093            let want = a.solve(&b).unwrap();
2094            for i in 0..3 {
2095                assert!((x[i] - want[i]).abs() < 1e-12, "rhs {k}, component {i}");
2096            }
2097        }
2098    }
2099
2100    #[test]
2101    fn lu_rejects_singular_and_mismatched_inputs() {
2102        let singular = DMatrix::from_row_slice(2, 2, &[1.0_f64, 1.0, 1.0, 1.0]);
2103        assert!(Lu::new(&singular).is_err());
2104        let a = DMatrix::from_row_slice(2, 2, &[2.0_f64, 0.0, 0.0, 2.0]);
2105        let lu = Lu::new(&a).unwrap();
2106        assert!(lu.solve(&DVector::from_vec(vec![1.0, 2.0, 3.0])).is_err());
2107        assert!(Lu::new(&DMatrix::<f64>::zeros(2, 3)).is_err());
2108    }
2109
2110    #[test]
2111    fn singular_matrix_is_rejected() {
2112        let a = DMatrix::from_row_slice(2, 2, &[1.0_f64, 1.0, 1.0, 1.0]);
2113        assert!(a.inverse().is_err());
2114        assert!(a.solve(&DVector::from_vec(vec![1.0, 1.0])).is_err());
2115    }
2116
2117    #[test]
2118    fn from_diagonal() {
2119        let d = DMatrix::from_diagonal(&DVector::from_vec(vec![2.0_f64, 3.0, 4.0]));
2120        assert_eq!(d[(0, 0)], 2.0);
2121        assert_eq!(d[(1, 1)], 3.0);
2122        assert_eq!(d[(2, 2)], 4.0);
2123        assert_eq!(d[(0, 1)], 0.0);
2124    }
2125}
2126
2127/// Checks the kernel-routed paths against the generic loops. These also run
2128/// (trivially) without the `simd` feature, where both sides are the same code.
2129#[cfg(all(test, feature = "alloc"))]
2130mod simd_tests {
2131    use super::*;
2132
2133    fn a_f64(i: usize, j: usize) -> f64 {
2134        ((i * 7 + j * 3) % 17) as f64 * 0.25 - 2.0
2135    }
2136    fn b_f64(i: usize, j: usize) -> f64 {
2137        ((i * 5 + j * 11) % 13) as f64 * 0.25 - 1.5
2138    }
2139
2140    #[test]
2141    fn matmul_f64_matches_generic() {
2142        for &(m, k, n) in &[
2143            (1, 1, 1),
2144            (3, 5, 2),
2145            (17, 9, 33),
2146            (64, 64, 64),
2147            (70, 130, 65),
2148        ] {
2149            let a = DMatrix::from_fn(m, k, a_f64);
2150            let b = DMatrix::from_fn(k, n, b_f64);
2151            let want = mul_matrix_generic(&a, &b);
2152            let got = a * b;
2153            assert_eq!((got.nrows(), got.ncols()), (m, n));
2154            for (g, w) in got.iter().zip(want.iter()) {
2155                assert!((g - w).abs() <= 1e-9 * (1.0 + w.abs()), "{g} vs {w}");
2156            }
2157        }
2158    }
2159
2160    #[test]
2161    fn matmul_f32_matches_generic() {
2162        let a = DMatrix::from_fn(33, 21, |i, j| a_f64(i, j) as f32);
2163        let b = DMatrix::from_fn(21, 40, |i, j| b_f64(i, j) as f32);
2164        let want = mul_matrix_generic(&a, &b);
2165        let got = a * b;
2166        for (g, w) in got.iter().zip(want.iter()) {
2167            assert!((g - w).abs() <= 1e-3 * (1.0 + w.abs()), "{g} vs {w}");
2168        }
2169    }
2170
2171    #[test]
2172    fn matvec_dot_norm_match_generic() {
2173        let a = DMatrix::from_fn(37, 29, a_f64);
2174        let x = DVector::from_fn(29, |i| b_f64(i, 1));
2175        let want = mul_vector_generic(&a, &x);
2176        let got = a * x.clone();
2177        for (g, w) in got.iter().zip(want.iter()) {
2178            assert!((g - w).abs() <= 1e-9 * (1.0 + w.abs()));
2179        }
2180        let y = DVector::from_fn(29, |i| a_f64(i, 2));
2181        assert!((x.dot(&y) - x.dot_generic(&y)).abs() <= 1e-9);
2182        assert!((x.norm() - x.norm_generic()).abs() <= 1e-9);
2183    }
2184
2185    #[test]
2186    fn empty_and_degenerate_shapes() {
2187        let a = DMatrix::<f64>::zeros(0, 3);
2188        let b = DMatrix::<f64>::zeros(3, 4);
2189        let c = a * b;
2190        assert_eq!((c.nrows(), c.ncols()), (0, 4));
2191        let a = DMatrix::<f64>::zeros(2, 0);
2192        let b = DMatrix::<f64>::zeros(0, 3);
2193        let c = a * b;
2194        assert_eq!((c.nrows(), c.ncols()), (2, 3));
2195        assert!(c.iter().all(|v| *v == 0.0));
2196        assert_eq!(DVector::<f64>::from_vec(vec![]).norm(), 0.0);
2197    }
2198
2199    #[test]
2200    fn slices_expose_column_major_data() {
2201        let m = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 3.0, 4.0]);
2202        assert_eq!(m.as_slice(), &[1.0, 3.0, 2.0, 4.0]);
2203        let mut v = DVector::from_vec(vec![1.0_f64, 2.0]);
2204        v.as_mut_slice()[1] = 5.0;
2205        assert_eq!(v.as_slice(), &[1.0, 5.0]);
2206    }
2207
2208    #[cfg(feature = "simd")]
2209    #[test]
2210    #[should_panic(expected = "inner dimensions")]
2211    fn matmul_dimension_mismatch_panics() {
2212        let _ = DMatrix::<f64>::zeros(2, 3) * DMatrix::<f64>::zeros(4, 2);
2213    }
2214
2215    #[test]
2216    #[should_panic(expected = "inner dimensions")]
2217    fn generic_matmul_dimension_mismatch_panics() {
2218        let _ = mul_matrix_generic(&DMatrix::<f64>::zeros(2, 3), &DMatrix::<f64>::zeros(4, 2));
2219    }
2220
2221    #[test]
2222    #[should_panic(expected = "columns")]
2223    fn generic_matvec_dimension_mismatch_panics() {
2224        let _ = mul_vector_generic(&DMatrix::<f64>::zeros(2, 3), &DVector::zeros(2));
2225    }
2226
2227    #[test]
2228    #[should_panic(expected = "length")]
2229    fn dot_length_mismatch_panics() {
2230        let _ = DVector::from_vec(vec![1.0_f64, 2.0, 3.0]).dot(&DVector::from_vec(vec![1.0_f64]));
2231    }
2232
2233    #[test]
2234    fn norm_does_not_overflow_for_large_entries() {
2235        // Naive sum of squares would be +inf here; the true norm is 1e200 * sqrt(2).
2236        let v = DVector::from_vec(vec![1e200_f64, 1e200]);
2237        let n = v.norm_generic();
2238        assert!(n.is_finite());
2239        assert!((n / (1e200 * 2.0_f64.sqrt()) - 1.0).abs() < 1e-14);
2240    }
2241
2242    #[test]
2243    fn norm_does_not_underflow_for_tiny_entries() {
2244        let v = DVector::from_vec(vec![1e-200_f64, 1e-200]);
2245        let n = v.norm_generic();
2246        assert!(n > 0.0);
2247        assert!((n / (1e-200 * 2.0_f64.sqrt()) - 1.0).abs() < 1e-14);
2248    }
2249
2250    #[test]
2251    #[should_panic(expected = "out of bounds")]
2252    fn index_row_out_of_bounds_panics() {
2253        // (3, 0) would alias (0, 1) in column-major storage without a check.
2254        let m = DMatrix::<f64>::zeros(3, 2);
2255        let _ = m[(3, 0)];
2256    }
2257
2258    #[test]
2259    #[should_panic(expected = "length")]
2260    fn from_vec_length_mismatch_panics() {
2261        let _ = DMatrix::from_vec(2, 2, vec![1.0_f64, 2.0, 3.0]);
2262    }
2263
2264    #[test]
2265    #[should_panic(expected = "length")]
2266    fn from_row_slice_length_mismatch_panics() {
2267        let _ = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 3.0, 4.0, 5.0]);
2268    }
2269}
2270
2271#[cfg(all(test, feature = "alloc"))]
2272mod decomposition_tests {
2273    use super::*;
2274
2275    fn assert_close(a: &DMatrix<f64>, b: &DMatrix<f64>, tol: f64) {
2276        assert_eq!((a.nrows(), a.ncols()), (b.nrows(), b.ncols()));
2277        for i in 0..a.nrows() {
2278            for j in 0..a.ncols() {
2279                assert!(
2280                    (a[(i, j)] - b[(i, j)]).abs() <= tol,
2281                    "({i},{j}): {} vs {}",
2282                    a[(i, j)],
2283                    b[(i, j)]
2284                );
2285            }
2286        }
2287    }
2288
2289    /// `U · diag(σ) · Vᵀ`.
2290    fn reconstruct(u: &DMatrix<f64>, s: &DVector<f64>, v: &DMatrix<f64>) -> DMatrix<f64> {
2291        DMatrix::from_fn(u.nrows(), v.nrows(), |i, j| {
2292            (0..s.len()).map(|k| u[(i, k)] * s[k] * v[(j, k)]).sum()
2293        })
2294    }
2295
2296    #[test]
2297    fn svd_reconstructs_tall_and_wide_matrices() {
2298        let tall = DMatrix::from_row_slice(3, 2, &[1.0, 2.0, 3.0, 4.0, 5.0, 6.0]);
2299        let (u, s, v) = tall.svd().unwrap();
2300        assert_close(&reconstruct(&u, &s, &v), &tall, 1e-12);
2301        let wide = tall.transpose();
2302        let (u, s, v) = wide.svd().unwrap();
2303        assert_close(&reconstruct(&u, &s, &v), &wide, 1e-12);
2304    }
2305
2306    #[test]
2307    fn singular_values_are_sorted_and_exact_for_diagonal() {
2308        let d = DMatrix::from_row_slice(2, 2, &[3.0, 0.0, 0.0, -4.0]);
2309        let s = d.singular_values().unwrap();
2310        assert!((s[0] - 4.0).abs() < 1e-12);
2311        assert!((s[1] - 3.0).abs() < 1e-12);
2312    }
2313
2314    #[test]
2315    fn rank_detects_dependent_rows() {
2316        let a = DMatrix::from_row_slice(2, 2, &[1.0, 2.0, 2.0, 4.0]);
2317        assert_eq!(a.rank().unwrap(), 1);
2318        let eye = DMatrix::from_row_slice(3, 3, &[1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0]);
2319        assert_eq!(eye.rank().unwrap(), 3);
2320        assert_eq!(DMatrix::zeros(2, 2).rank().unwrap(), 0);
2321    }
2322
2323    #[test]
2324    fn condition_number_of_diagonal_and_singular() {
2325        let a = DMatrix::from_row_slice(2, 2, &[10.0, 0.0, 0.0, 1.0]);
2326        assert!((a.cond().unwrap() - 10.0).abs() < 1e-12);
2327        let singular = DMatrix::from_row_slice(2, 2, &[1.0, 2.0, 2.0, 4.0]);
2328        assert!(singular.cond().unwrap().is_infinite());
2329    }
2330
2331    #[test]
2332    fn matrix_exponential_known_values() {
2333        let zero = DMatrix::zeros(2, 2);
2334        let eye = DMatrix::from_row_slice(2, 2, &[1.0, 0.0, 0.0, 1.0]);
2335        assert_close(&zero.matrix_exp().unwrap(), &eye, 1e-14);
2336
2337        let e = core::f64::consts::E;
2338        let d = DMatrix::from_row_slice(2, 2, &[1.0, 0.0, 0.0, 2.0]);
2339        let want = DMatrix::from_row_slice(2, 2, &[e, 0.0, 0.0, e * e]);
2340        assert_close(&d.matrix_exp().unwrap(), &want, 1e-12);
2341
2342        // Nilpotent: exp([[0, 1], [0, 0]]) = [[1, 1], [0, 1]].
2343        let nilpotent = DMatrix::from_row_slice(2, 2, &[0.0, 1.0, 0.0, 0.0]);
2344        let want = DMatrix::from_row_slice(2, 2, &[1.0, 1.0, 0.0, 1.0]);
2345        assert_close(&nilpotent.matrix_exp().unwrap(), &want, 1e-14);
2346
2347        // Generator of rotations: exp([[0, -t], [t, 0]]) is a rotation by t.
2348        let t = 1.0_f64;
2349        let gen = DMatrix::from_row_slice(2, 2, &[0.0, -t, t, 0.0]);
2350        let want = DMatrix::from_row_slice(2, 2, &[t.cos(), -t.sin(), t.sin(), t.cos()]);
2351        assert_close(&gen.matrix_exp().unwrap(), &want, 1e-12);
2352
2353        // Large entries exercise the scaling-and-squaring path.
2354        let big = DMatrix::from_row_slice(2, 2, &[10.0, 0.0, 0.0, -10.0]);
2355        let got = big.matrix_exp().unwrap();
2356        let want = 10f64.exp();
2357        assert!(((got[(0, 0)] - want) / want).abs() < 1e-12);
2358    }
2359
2360    #[test]
2361    fn matrix_exp_requires_square() {
2362        assert!(matches!(
2363            DMatrix::zeros(2, 3).matrix_exp(),
2364            Err(DenseError::DimensionMismatch { .. })
2365        ));
2366    }
2367}
2368
2369#[cfg(feature = "alloc")]
2370impl DMatrix<f64> {
2371    /// An eigenvector of a square matrix for a given real eigenvalue `lambda`,
2372    /// by inverse iteration, returned with its residual.
2373    ///
2374    /// The vector is found by repeatedly solving `(A − σI) y = x` with a shift
2375    /// `σ = λ + δ` just off the eigenvalue, so the solves are nearly singular and
2376    /// the iterates converge to the eigenvector. Returns `(v, r)` with `‖v‖ = 1`
2377    /// and `r = ‖A v − λ v‖`.
2378    ///
2379    /// This is for a *known* eigenvalue, for example one returned by another
2380    /// routine or read from a model. The matrix does not have to be symmetric.
2381    /// A wrong `lambda` gives a large residual, which is how to detect it. The
2382    /// crate does not yet compute the eigenvalues of a general real matrix.
2383    ///
2384    /// # Errors
2385    ///
2386    /// Returns [`DenseError::DimensionMismatch`] if the matrix is not square, and
2387    /// [`DenseError::NoConvergence`] if the residual is still above `1e-8·‖A‖` after
2388    /// the iteration budget. That usually means `lambda` is not an eigenvalue.
2389    ///
2390    /// # Examples
2391    ///
2392    /// ```
2393    /// use tpt_math_linalg_dense::DMatrix;
2394    ///
2395    /// // A non-symmetric matrix with eigenvalues 1 and 3.
2396    /// let a = DMatrix::from_row_slice(2, 2, &[2.0, 1.0, 1.0, 2.0]);
2397    /// let (v, r) = a.eigenvector_for_eigenvalue(3.0).unwrap();
2398    /// assert!(r < 1e-9);
2399    /// assert!((v[0] - v[1]).abs() < 1e-9); // the eigenvector for 3 is (1, 1)/√2
2400    /// ```
2401    pub fn eigenvector_for_eigenvalue(
2402        &self,
2403        lambda: f64,
2404    ) -> Result<(DVector<f64>, f64), DenseError> {
2405        let n = self.nrows();
2406        if self.ncols() != n {
2407            return Err(DenseError::DimensionMismatch {
2408                what: format!(
2409                    "eigenvector_for_eigenvalue needs a square matrix, got {n}x{}",
2410                    self.ncols()
2411                ),
2412            });
2413        }
2414        let scale = self.iter().fold(0.0_f64, |m, v| m.max(v.abs())).max(1.0);
2415        // Shift just off the eigenvalue: singular enough to amplify the
2416        // eigenvector, but still factorable.
2417        let shift = lambda + 1e-9 * scale.max(lambda.abs());
2418        let shifted =
2419            DMatrix::from_fn(n, n, |i, j| self[(i, j)] - if i == j { shift } else { 0.0 });
2420
2421        let mut x = DVector::from_fn(n, |i| 1.0 / sqrt_f64((i + 1) as f64));
2422        let mut residual = f64::INFINITY;
2423        for _ in 0..20 {
2424            let y = shifted.solve(&x)?;
2425            let norm = sqrt_f64(y.iter().map(|v| v * v).sum::<f64>());
2426            if !norm.is_finite() || norm == 0.0 {
2427                return Err(DenseError::NoConvergence {
2428                    what: "eigenvector_for_eigenvalue",
2429                });
2430            }
2431            x = DVector::from_fn(n, |i| y[i] / norm);
2432            // Residual of A x = λ x.
2433            let ax = DVector::from_fn(n, |i| (0..n).map(|j| self[(i, j)] * x[j]).sum::<f64>());
2434            residual = sqrt_f64(
2435                (0..n)
2436                    .map(|i| {
2437                        let d = ax[i] - lambda * x[i];
2438                        d * d
2439                    })
2440                    .sum::<f64>(),
2441            );
2442            if residual <= 1e-12 * scale {
2443                break;
2444            }
2445        }
2446        if residual <= 1e-8 * scale {
2447            Ok((x, residual))
2448        } else {
2449            Err(DenseError::NoConvergence {
2450                what: "eigenvector_for_eigenvalue",
2451            })
2452        }
2453    }
2454}
2455
2456#[cfg(test)]
2457mod in_place_tests {
2458    use super::*;
2459
2460    #[test]
2461    fn vector_compound_assignments() {
2462        let mut v = DVector::from_row_slice(&[1.0_f64, 2.0, 3.0]);
2463        let w = DVector::from_row_slice(&[10.0_f64, 20.0, 30.0]);
2464        v += &w;
2465        assert_eq!(v, DVector::from_row_slice(&[11.0, 22.0, 33.0]));
2466        v -= &w;
2467        assert_eq!(v, DVector::from_row_slice(&[1.0, 2.0, 3.0]));
2468        v *= 2.0;
2469        assert_eq!(v, DVector::from_row_slice(&[2.0, 4.0, 6.0]));
2470        v /= 4.0;
2471        assert_eq!(v, DVector::from_row_slice(&[0.5, 1.0, 1.5]));
2472    }
2473
2474    #[test]
2475    fn axpy_updates_in_place() {
2476        let mut v = DVector::from_row_slice(&[1.0_f64, 1.0]);
2477        v.axpy(3.0, &DVector::from_row_slice(&[2.0, -1.0]));
2478        assert_eq!(v, DVector::from_row_slice(&[7.0, -2.0]));
2479
2480        let mut m = DMatrix::from_row_slice(2, 2, &[1.0_f64, 0.0, 0.0, 1.0]);
2481        m.axpy(-2.0, &DMatrix::from_row_slice(2, 2, &[1.0, 2.0, 3.0, 4.0]));
2482        assert_eq!(m, DMatrix::from_row_slice(2, 2, &[-1.0, -4.0, -6.0, -7.0]));
2483    }
2484
2485    #[test]
2486    fn matrix_compound_assignments() {
2487        let mut m = DMatrix::from_row_slice(2, 2, &[1.0_f64, 2.0, 3.0, 4.0]);
2488        let n = DMatrix::from_row_slice(2, 2, &[1.0_f64, 1.0, 1.0, 1.0]);
2489        m += &n;
2490        m -= &n;
2491        assert_eq!(m, DMatrix::from_row_slice(2, 2, &[1.0, 2.0, 3.0, 4.0]));
2492        m *= 0.5;
2493        assert_eq!(m, DMatrix::from_row_slice(2, 2, &[0.5, 1.0, 1.5, 2.0]));
2494    }
2495
2496    #[test]
2497    fn mul_vector_into_matches_operator_and_overwrites_buffer() {
2498        let a = DMatrix::from_row_slice(2, 3, &[1.0_f64, 2.0, 3.0, 4.0, 5.0, 6.0]);
2499        let x = DVector::from_row_slice(&[1.0, -1.0, 2.0]);
2500        let mut y = DVector::from_row_slice(&[99.0, 99.0]);
2501        a.mul_vector_into(&x, &mut y);
2502        assert_eq!(y, a.clone() * x);
2503    }
2504
2505    #[test]
2506    fn mul_matrix_into_matches_operator_and_overwrites_buffer() {
2507        let a = DMatrix::from_row_slice(2, 3, &[1.0_f64, 2.0, 3.0, 4.0, 5.0, 6.0]);
2508        let b = DMatrix::from_row_slice(3, 2, &[7.0_f64, 8.0, 9.0, 10.0, 11.0, 12.0]);
2509        let mut out = DMatrix::from_row_slice(2, 2, &[5.0_f64; 4]);
2510        a.mul_matrix_into(&b, &mut out);
2511        assert_eq!(out, a.clone() * b.clone());
2512        assert_eq!(
2513            out,
2514            DMatrix::from_row_slice(2, 2, &[58.0, 64.0, 139.0, 154.0])
2515        );
2516    }
2517
2518    #[test]
2519    #[should_panic(expected = "output shape mismatch")]
2520    fn mul_matrix_into_rejects_wrong_output_shape() {
2521        let a = DMatrix::from_row_slice(2, 2, &[1.0_f64, 0.0, 0.0, 1.0]);
2522        let mut out = DMatrix::zeros(3, 2);
2523        a.mul_matrix_into(&a.clone(), &mut out);
2524    }
2525}
2526
2527#[cfg(test)]
2528mod lu_tolerance_tests {
2529    use super::*;
2530
2531    #[test]
2532    fn default_accepts_small_scale_and_absolute_tolerance_still_rejects_it() {
2533        // Well-conditioned, but every pivot is below the old absolute 1e-12.
2534        let m = DMatrix::from_row_slice(2, 2, &[1e-13, 0.0, 0.0, 2e-13]);
2535        let lu = Lu::new(&m).unwrap();
2536        let x = lu.solve(&DVector::from_vec(vec![1e-13, 2e-13])).unwrap();
2537        assert!((x[0] - 1.0).abs() < 1e-12 && (x[1] - 1.0).abs() < 1e-12);
2538        assert!(matches!(
2539            Lu::with_pivot_tolerance(&m, 1e-12),
2540            Err(DenseError::Singular { .. })
2541        ));
2542        let lu = Lu::with_pivot_tolerance(&m, 0.0).unwrap();
2543        let x = lu.solve(&DVector::from_vec(vec![1e-13, 2e-13])).unwrap();
2544        assert!((x[0] - 1.0).abs() < 1e-12 && (x[1] - 1.0).abs() < 1e-12);
2545    }
2546
2547    #[test]
2548    fn relative_tolerance_is_scale_invariant() {
2549        let a = DMatrix::from_row_slice(2, 2, &[4.0, 1.0, 2.0, 3.0]);
2550        let scaled = a.clone() * 1e-14;
2551        assert!(Lu::with_relative_tolerance(&a, 1e-10).is_ok());
2552        assert!(Lu::with_relative_tolerance(&scaled, 1e-10).is_ok());
2553        // The default test is relative, so the scaled copy is accepted too.
2554        assert!(Lu::new(&scaled).is_ok());
2555    }
2556
2557    #[test]
2558    fn tolerance_constructors_still_reject_singular_and_zero_matrices() {
2559        let singular = DMatrix::from_row_slice(2, 2, &[1.0, 2.0, 2.0, 4.0]);
2560        assert!(Lu::with_relative_tolerance(&singular, 1e-10).is_err());
2561        assert!(Lu::with_pivot_tolerance(&singular, 0.0).is_err());
2562        let zero = DMatrix::zeros(3, 3);
2563        assert!(Lu::with_relative_tolerance(&zero, 1e-10).is_err());
2564        assert!(Lu::with_pivot_tolerance(&zero, 0.0).is_err());
2565    }
2566}
2567
2568#[cfg(all(test, feature = "rayon"))]
2569mod par_mul_tests {
2570    use super::*;
2571
2572    #[test]
2573    fn par_mul_is_bitwise_equal_to_serial_product() {
2574        // Non-square shapes, including a single column and an empty result.
2575        for &(m, k, n) in &[
2576            (1usize, 1usize, 1usize),
2577            (3, 5, 2),
2578            (17, 9, 23),
2579            (64, 64, 64),
2580        ] {
2581            let a = DMatrix::from_fn(m, k, |i, j| ((i * 7 + j * 3) as f64).sin());
2582            let b = DMatrix::from_fn(k, n, |i, j| ((i * 5 + j) as f64).cos() * 1e-3);
2583            // Serial reference in the same accumulation order as `par_mul`. Not
2584            // `*`: with the `simd` feature that goes through a reassociating BLAS kernel.
2585            // Column-major reference, accumulated in the same order as `par_mul`.
2586            let mut reference = vec![0.0; m * n];
2587            for j in 0..n {
2588                for kk in 0..k {
2589                    for i in 0..m {
2590                        reference[j * m + i] += a[(i, kk)] * b[(kk, j)];
2591                    }
2592                }
2593            }
2594            assert_eq!(
2595                a.par_mul(&b).as_slice(),
2596                reference.as_slice(),
2597                "shape {m}x{k}x{n}"
2598            );
2599        }
2600    }
2601
2602    #[test]
2603    fn par_mul_handles_empty_output() {
2604        let a = DMatrix::<f64>::zeros(0, 3);
2605        let b = DMatrix::<f64>::zeros(3, 4);
2606        assert_eq!(a.par_mul(&b).nrows(), 0);
2607    }
2608}
2609
2610#[cfg(all(test, feature = "alloc"))]
2611mod review_regression_tests {
2612    use super::*;
2613
2614    #[test]
2615    fn matrix_exp_returns_nan_for_non_finite_input() {
2616        // Used to loop forever: the infinite norm never drops below 1/2.
2617        let m = DMatrix::from_row_slice(2, 2, &[f64::INFINITY, 0.0, 0.0, 1.0]);
2618        let e = m.matrix_exp().unwrap();
2619        assert!(e.iter().all(|v| v.is_nan()));
2620        let m = DMatrix::from_row_slice(2, 2, &[f64::NAN, 0.0, 0.0, 1.0]);
2621        assert!(m.matrix_exp().unwrap().iter().all(|v| v.is_nan()));
2622    }
2623
2624    #[test]
2625    fn symmetric_eigen_resolves_values_at_rounding_scale() {
2626        // Used to return [0, 0]: the stop test had an absolute floor.
2627        let a = DMatrix::from_row_slice(2, 2, &[0.0, 1e-16, 1e-16, 0.0]);
2628        let (vals, _) = a.symmetric_eigen().unwrap();
2629        assert!((vals[0] + 1e-16).abs() < 1e-30, "got {}", vals[0]);
2630        assert!((vals[1] - 1e-16).abs() < 1e-30, "got {}", vals[1]);
2631    }
2632
2633    #[test]
2634    fn symmetric_eigen_rejects_asymmetry_at_small_scale() {
2635        // Relative asymmetry of 100%, at a scale where the old absolute slack hid it.
2636        let a = DMatrix::from_row_slice(2, 2, &[0.0, 1e-16, 0.0, 0.0]);
2637        assert!(a.symmetric_eigen().is_err());
2638    }
2639
2640    #[test]
2641    fn det_and_solve_work_for_small_scale_well_conditioned_matrices() {
2642        // Used to return Ok(0.0) and to fail with Singular.
2643        let a = DMatrix::from_row_slice(2, 2, &[1e-13, 0.0, 0.0, 1e-13]);
2644        assert!((a.det().unwrap() - 1e-26).abs() < 1e-38);
2645        let x = a.solve(&DVector::from_vec(vec![1e-13, 2e-13])).unwrap();
2646        assert!((x[0] - 1.0).abs() < 1e-12 && (x[1] - 2.0).abs() < 1e-12);
2647        let inv = a.inverse().unwrap();
2648        assert!((inv[(0, 0)] - 1e13).abs() < 1e-3);
2649    }
2650
2651    #[test]
2652    fn svd_reports_non_convergence_instead_of_unconverged_factors() {
2653        // NaN input never satisfies the rotation test, so the sweep budget runs out.
2654        let a = DMatrix::from_row_slice(2, 2, &[f64::NAN, 1.0, 1.0, 1.0]);
2655        assert!(matches!(
2656            a.svd(),
2657            Err(DenseError::NoConvergence { what: "svd" })
2658        ));
2659    }
2660
2661    #[test]
2662    fn pseudo_inverse_satisfies_penrose_identities() {
2663        // Rank-deficient 3x2, and a wide 2x3 of rank 2.
2664        let tall = DMatrix::from_row_slice(3, 2, &[1.0, 2.0, 2.0, 4.0, 3.0, 6.0]);
2665        let wide = DMatrix::from_row_slice(2, 3, &[1.0, 0.0, 2.0, 0.0, 1.0, 1.0]);
2666        for a in [tall, wide] {
2667            let p = a.pseudo_inverse().unwrap();
2668            assert_eq!((p.nrows(), p.ncols()), (a.ncols(), a.nrows()));
2669            let apa = a.clone() * p.clone() * a.clone();
2670            let pap = p.clone() * a.clone() * p.clone();
2671            for i in 0..a.nrows() {
2672                for j in 0..a.ncols() {
2673                    assert!((apa[(i, j)] - a[(i, j)]).abs() < 1e-10);
2674                }
2675            }
2676            for i in 0..p.nrows() {
2677                for j in 0..p.ncols() {
2678                    assert!((pap[(i, j)] - p[(i, j)]).abs() < 1e-10);
2679                }
2680            }
2681        }
2682    }
2683
2684    #[test]
2685    fn min_norm_solve_handles_rank_deficiency() {
2686        // Columns are dependent, so the minimisers form a line: x = (t, 1 - t) with
2687        // the minimum-norm point at t = 1/2.
2688        let a = DMatrix::from_row_slice(2, 2, &[1.0, 1.0, 1.0, 1.0]);
2689        let x = a
2690            .solve_min_norm(&DVector::from_vec(vec![1.0, 1.0]))
2691            .unwrap();
2692        assert!((x[0] - 0.5).abs() < 1e-12 && (x[1] - 0.5).abs() < 1e-12);
2693        assert!(a
2694            .solve_min_norm(&DVector::from_vec(vec![1.0, 2.0, 3.0]))
2695            .is_err());
2696    }
2697}
2698
2699#[cfg(all(test, feature = "alloc"))]
2700mod solve_matrix_tests {
2701    use super::*;
2702
2703    #[test]
2704    fn solve_matrix_matches_column_by_column_solves() {
2705        let a = DMatrix::from_fn(4, 4, |i, j| {
2706            if i == j {
2707                5.0
2708            } else {
2709                ((i + 2 * j) as f64).sin()
2710            }
2711        });
2712        let b = DMatrix::from_fn(4, 3, |i, j| (i * 3 + j) as f64 - 4.0);
2713        let lu = Lu::new(&a).unwrap();
2714        let x = lu.solve_matrix(&b).unwrap();
2715        assert_eq!((x.nrows(), x.ncols()), (4, 3));
2716        for col in 0..3 {
2717            let rhs = DVector::from_fn(4, |i| b[(i, col)]);
2718            let want = lu.solve(&rhs).unwrap();
2719            for i in 0..4 {
2720                assert!((x[(i, col)] - want[i]).abs() < 1e-12);
2721            }
2722        }
2723        assert!(lu.solve_matrix(&DMatrix::zeros(3, 1)).is_err());
2724    }
2725}
2726
2727#[cfg(all(test, feature = "alloc"))]
2728mod pade_exp_tests {
2729    use super::*;
2730
2731    #[test]
2732    fn rotation_generator_gives_a_rotation() {
2733        // exp([[0, -t], [t, 0]]) is the rotation by t.
2734        for t in [0.3_f64, 2.5, 7.0, 40.0] {
2735            let g = DMatrix::from_row_slice(2, 2, &[0.0, -t, t, 0.0]);
2736            let e = g.matrix_exp().unwrap();
2737            assert!((e[(0, 0)] - t.cos()).abs() < 1e-11, "t = {t}");
2738            assert!((e[(1, 0)] - t.sin()).abs() < 1e-11, "t = {t}");
2739            assert!((e[(0, 1)] + t.sin()).abs() < 1e-11, "t = {t}");
2740        }
2741    }
2742
2743    #[test]
2744    fn large_norm_diagonal_matches_scalar_exp() {
2745        // The 1-norm is 20, far past θ₁₃, so several squarings run.
2746        let d = DMatrix::from_row_slice(2, 2, &[20.0, 0.0, 0.0, -3.0]);
2747        let e = d.matrix_exp().unwrap();
2748        assert!(((e[(0, 0)] - 20.0_f64.exp()) / 20.0_f64.exp()).abs() < 1e-12);
2749        assert!(((e[(1, 1)] - (-3.0_f64).exp()) / (-3.0_f64).exp()).abs() < 1e-12);
2750        assert!(e[(0, 1)].abs() < 1e-30 && e[(1, 0)].abs() < 1e-30);
2751    }
2752
2753    #[test]
2754    fn exp_of_zero_is_identity_and_nilpotent_is_exact() {
2755        let z = DMatrix::<f64>::zeros(3, 3);
2756        let e = z.matrix_exp().unwrap();
2757        for i in 0..3 {
2758            for j in 0..3 {
2759                assert!((e[(i, j)] - if i == j { 1.0 } else { 0.0 }).abs() < 1e-14);
2760            }
2761        }
2762        // N = [[0, 1], [0, 0]] has exp(N) = I + N exactly.
2763        let nil = DMatrix::from_row_slice(2, 2, &[0.0, 1.0, 0.0, 0.0]);
2764        let en = nil.matrix_exp().unwrap();
2765        assert!((en[(0, 1)] - 1.0).abs() < 1e-14 && (en[(0, 0)] - 1.0).abs() < 1e-14);
2766    }
2767}
2768
2769#[cfg(all(test, feature = "alloc"))]
2770mod svd_norm_carry_tests {
2771    use super::*;
2772
2773    /// ‖A − U Σ Vᵀ‖_F for the thin factors returned by `svd`.
2774    fn residual(a: &DMatrix<f64>) -> f64 {
2775        let (u, s, v) = a.svd().unwrap();
2776        let k = s.len();
2777        let mut err = 0.0;
2778        for i in 0..a.nrows() {
2779            for j in 0..a.ncols() {
2780                let rec: f64 = (0..k).map(|r| u[(i, r)] * s[r] * v[(j, r)]).sum();
2781                err += (a[(i, j)] - rec).powi(2);
2782            }
2783        }
2784        err.sqrt()
2785    }
2786
2787    #[test]
2788    fn reconstructs_ill_conditioned_input() {
2789        // A Hilbert-like matrix has condition number about 1e10.
2790        let h = DMatrix::from_fn(8, 8, |i, j| 1.0 / (i + j + 1) as f64);
2791        let scale = h.iter().fold(0.0_f64, |m, v| m.max(v.abs()));
2792        assert!(
2793            residual(&h) < 1e-13 * scale * 8.0,
2794            "residual {}",
2795            residual(&h)
2796        );
2797        let tall = DMatrix::from_fn(10, 4, |i, j| ((i + 1) as f64).powi(j as i32));
2798        let scale = tall.iter().fold(0.0_f64, |m, v| m.max(v.abs()));
2799        assert!(residual(&tall) < 1e-12 * scale * 10.0);
2800    }
2801
2802    #[test]
2803    fn singular_values_match_known_spectrum() {
2804        // diag(3, 1) rotated by an orthogonal matrix keeps singular values 3 and 1.
2805        let (c, s) = (0.6_f64, 0.8_f64);
2806        let rot = DMatrix::from_row_slice(2, 2, &[c, -s, s, c]);
2807        let d = DMatrix::from_row_slice(2, 2, &[3.0, 0.0, 0.0, 1.0]);
2808        let a = rot.clone() * d * rot.transpose();
2809        let sv = a.singular_values().unwrap();
2810        assert!((sv[0] - 3.0).abs() < 1e-12 && (sv[1] - 1.0).abs() < 1e-12);
2811    }
2812}
2813
2814/// Cholesky through `tpt-simd-blas`'s blocked `potrf`. Only the lower triangle
2815/// of the input is read, and the result is returned with a zero upper triangle,
2816/// as the scalar path does.
2817#[cfg(feature = "simd-runtime")]
2818mod simd_chol {
2819    use super::*;
2820
2821    pub(super) fn factor(m: &DMatrix<f64>) -> Result<DMatrix<f64>, DenseError> {
2822        let n = m.nrows;
2823        let mut a = m.data.clone();
2824        if tpt_simd_blas::potrf_f64(n, &mut a, n).is_err() {
2825            return Err(DenseError::Singular {
2826                what: "cholesky (not positive definite)",
2827            });
2828        }
2829        Ok(DMatrix::from_fn(n, n, |i, j| {
2830            if i >= j {
2831                a[i + j * n]
2832            } else {
2833                0.0
2834            }
2835        }))
2836    }
2837}
2838
2839/// LU through `tpt-simd-blas`'s blocked `getrf`. The kernel works on column-major
2840/// storage and returns LAPACK-style sequential swaps, so this module converts both
2841/// ways and produces the same row-major layout and permutation as the scalar path.
2842#[cfg(feature = "simd-runtime")]
2843mod simd_lu {
2844    use super::*;
2845
2846    pub(super) fn factor(m: &DMatrix<f64>, tol: f64) -> Result<(Vec<f64>, Vec<usize>), DenseError> {
2847        let n = m.nrows;
2848        let singular = DenseError::Singular {
2849            what: "partial_pivot_lu",
2850        };
2851        // `DMatrix` is already column-major, which is the kernel's layout.
2852        let mut colmajor = m.data.clone();
2853        let mut ipiv = vec![0usize; n];
2854        if tpt_simd_blas::getrf_f64(n, n, &mut colmajor, n, &mut ipiv).is_err() {
2855            return Err(singular);
2856        }
2857        let mut a = vec![0.0_f64; n * n];
2858        for j in 0..n {
2859            for i in 0..n {
2860                a[i * n + j] = colmajor[i + j * n];
2861            }
2862        }
2863        // The same singularity test as the scalar path, on the pivots actually used.
2864        for k in 0..n {
2865            let u = a[k * n + k].abs();
2866            if !u.is_finite() || u == 0.0 || u < tol {
2867                return Err(singular);
2868            }
2869        }
2870        // Sequential swaps applied to the identity give the permutation `piv`.
2871        let mut piv: Vec<usize> = (0..n).collect();
2872        for (i, &p) in ipiv.iter().enumerate() {
2873            piv.swap(i, p);
2874        }
2875        Ok((a, piv))
2876    }
2877
2878    /// Solve `A X = B` for all right-hand sides at once with `getrs`, from the
2879    /// row-major factors and permutation that [`factor`] produces.
2880    pub(super) fn solve_matrix(
2881        lu: &[f64],
2882        piv: &[usize],
2883        b: &DMatrix<f64>,
2884    ) -> Result<DMatrix<f64>, DenseError> {
2885        let n = piv.len();
2886        let nrhs = b.ncols();
2887        // Column-major factors, as the kernel expects.
2888        let mut colmajor = vec![0.0_f64; n * n];
2889        for i in 0..n {
2890            for j in 0..n {
2891                colmajor[i + j * n] = lu[i * n + j];
2892            }
2893        }
2894        // The kernel takes LAPACK-style sequential swaps. Rebuild them from the
2895        // permutation: position k must end up holding original row `piv[k]`.
2896        let mut current: Vec<usize> = (0..n).collect();
2897        let mut ipiv = vec![0usize; n];
2898        for k in 0..n {
2899            let p = (k..n)
2900                .find(|&p| current[p] == piv[k])
2901                .ok_or(DenseError::Singular {
2902                    what: "solve_matrix",
2903                })?;
2904            current.swap(k, p);
2905            ipiv[k] = p;
2906        }
2907        // `DMatrix` is column-major, so the right-hand sides can be passed as is.
2908        let mut x = b.data.clone();
2909        tpt_simd_blas::getrs_f64(n, nrhs, &colmajor, n, &ipiv, &mut x, n);
2910        Ok(DMatrix::from_vec(n, nrhs, x))
2911    }
2912
2913    #[cfg(test)]
2914    mod tests {
2915        use super::*;
2916
2917        fn dominant(n: usize) -> DMatrix<f64> {
2918            DMatrix::from_fn(n, n, |i, j| {
2919                if i == j {
2920                    n as f64 + 1.0
2921                } else {
2922                    ((i * 3 + j * 5) as f64).sin()
2923                }
2924            })
2925        }
2926
2927        #[test]
2928        fn simd_factors_agree_with_scalar_factors() {
2929            for n in [5usize, 33, 200] {
2930                let a = dominant(n);
2931                let (s_lu, s_piv) = scalar_lu(&a, 0.0).unwrap();
2932                let (v_lu, v_piv) = factor(&a, 0.0).unwrap();
2933                assert_eq!(s_piv, v_piv, "permutation, n = {n}");
2934                for (x, y) in s_lu.iter().zip(&v_lu) {
2935                    assert!(
2936                        (x - y).abs() <= 1e-12 * (1.0 + x.abs()),
2937                        "n = {n}: {x} vs {y}"
2938                    );
2939                }
2940            }
2941        }
2942
2943        #[test]
2944        fn simd_reports_singular_like_scalar() {
2945            // Two identical rows: exactly singular.
2946            let n = 80;
2947            let a = DMatrix::from_fn(n, n, |i, j| {
2948                if i <= 1 {
2949                    ((j + 1) as f64).sin()
2950                } else {
2951                    ((i * 7 + j) as f64).cos() + if i == j { 3.0 } else { 0.0 }
2952                }
2953            });
2954            assert!(matches!(factor(&a, 0.0), Err(DenseError::Singular { .. })));
2955            assert!(matches!(
2956                scalar_lu(&a, 0.0),
2957                Err(DenseError::Singular { .. })
2958            ));
2959        }
2960    }
2961}
2962
2963#[cfg(all(test, feature = "simd-runtime"))]
2964mod simd_dense_solve_tests {
2965    use super::*;
2966
2967    fn dominant_nonsymmetric(n: usize) -> DMatrix<f64> {
2968        DMatrix::from_fn(n, n, |i, j| {
2969            if i == j {
2970                n as f64 + 1.0
2971            } else {
2972                ((i * 3 + j * 5) as f64).sin()
2973            }
2974        })
2975    }
2976
2977    fn spd(n: usize) -> DMatrix<f64> {
2978        // Symmetric, strictly diagonally dominant, so positive definite.
2979        DMatrix::from_fn(n, n, |i, j| {
2980            if i == j {
2981                n as f64 + 2.0
2982            } else {
2983                1.0 / (1.0 + i.abs_diff(j) as f64)
2984            }
2985        })
2986    }
2987
2988    #[test]
2989    fn simd_solve_matrix_agrees_with_the_scalar_solve() {
2990        for n in [5usize, 33, 200] {
2991            let a = dominant_nonsymmetric(n);
2992            let (lu, piv) = scalar_lu(&a, 0.0).unwrap();
2993            let rhs = DMatrix::from_fn(n, 3, |i, j| (i as f64 * 0.3 + j as f64).cos());
2994            let simd = simd_lu::solve_matrix(&lu, &piv, &rhs).unwrap();
2995            for col in 0..3 {
2996                let column = DVector::from_fn(n, |i| rhs[(i, col)]);
2997                let want = solve_with_lu(&lu, &piv, &column);
2998                for i in 0..n {
2999                    let got = simd[(i, col)];
3000                    assert!(
3001                        (got - want[i]).abs() <= 1e-10 * want[i].abs().max(1.0),
3002                        "n = {n}, col {col}, row {i}: {got} vs {}",
3003                        want[i]
3004                    );
3005                }
3006            }
3007        }
3008    }
3009
3010    #[test]
3011    fn simd_cholesky_agrees_with_the_scalar_cholesky() {
3012        for n in [5usize, 33, 200] {
3013            let a = spd(n);
3014            let want = scalar_cholesky(&a).unwrap();
3015            let got = simd_chol::factor(&a).unwrap();
3016            for i in 0..n {
3017                for j in 0..n {
3018                    assert!(
3019                        (got[(i, j)] - want[(i, j)]).abs() <= 1e-10 * want[(i, j)].abs().max(1.0),
3020                        "n = {n} at ({i}, {j})"
3021                    );
3022                }
3023            }
3024        }
3025    }
3026
3027    #[test]
3028    fn simd_cholesky_rejects_an_indefinite_matrix() {
3029        let n = 80;
3030        let a = DMatrix::from_fn(n, n, |i, j| {
3031            if i == j {
3032                if i == 40 {
3033                    -1.0
3034                } else {
3035                    2.0
3036                }
3037            } else {
3038                0.0
3039            }
3040        });
3041        assert!(simd_chol::factor(&a).is_err());
3042        assert!(a.cholesky().is_err());
3043    }
3044
3045    #[test]
3046    fn determinant_sign_is_right_after_many_row_swaps() {
3047        // The cyclic shift on n rows is an n-cycle, with n − 1 transpositions, so
3048        // its determinant is (−1)^(n−1). Here n = 66 is above the SIMD cutoff.
3049        let n = 66;
3050        let shift = DMatrix::from_fn(n, n, |i, j| if j == (i + 1) % n { 1.0 } else { 0.0 });
3051        let det = shift.det().unwrap();
3052        assert!((det + 1.0).abs() < 1e-12, "det = {det}");
3053    }
3054
3055    #[test]
3056    fn near_singular_inputs_are_classified_the_same_on_both_paths() {
3057        // Order 70 is above the SIMD cutoff. The last pivot sits on either side of
3058        // the relative threshold (1e-12 · max|aᵢⱼ| = 1e-12).
3059        let n = 70;
3060        for (last, singular) in [(1e-14, true), (1e-10, false)] {
3061            let a = DMatrix::from_fn(n, n, |i, j| match (i == j, i == n - 1) {
3062                (true, true) => last,
3063                (true, false) => 1.0,
3064                _ => 0.0,
3065            });
3066            let scale = 1.0;
3067            let simd = partial_pivot_lu_with(&a, DEFAULT_PIVOT_RELATIVE * scale);
3068            let scalar = scalar_lu(&a, DEFAULT_PIVOT_RELATIVE * scale);
3069            assert_eq!(simd.is_err(), singular, "simd path, last pivot {last}");
3070            assert_eq!(scalar.is_err(), singular, "scalar path, last pivot {last}");
3071            if !singular {
3072                let (lu_s, p_s) = scalar.unwrap();
3073                let (lu_v, p_v) = simd.unwrap();
3074                assert_eq!(p_s, p_v);
3075                for (x, y) in lu_s.iter().zip(&lu_v) {
3076                    assert!((x - y).abs() < 1e-12);
3077                }
3078            }
3079        }
3080    }
3081
3082    #[test]
3083    fn lu_solve_matrix_dispatch_matches_small_path() {
3084        // Above the cutoff, `Lu::solve_matrix` takes the SIMD branch; check it
3085        // against a solve column by column.
3086        let n = 70;
3087        let a = dominant_nonsymmetric(n);
3088        let lu = Lu::new(&a).unwrap();
3089        let rhs = DMatrix::from_fn(n, 2, |i, j| (i + j) as f64);
3090        let x = lu.solve_matrix(&rhs).unwrap();
3091        let back = a.clone() * x;
3092        for i in 0..n {
3093            for j in 0..2 {
3094                assert!((back[(i, j)] - rhs[(i, j)]).abs() < 1e-9);
3095            }
3096        }
3097    }
3098}