one-indexed-vec 0.2.0

A one-based (1-indexed) wrapper around Vec<T>: element at position N is accessed via vec[N].
Documentation
//! Matrix decompositions: LU, QR, Cholesky.

use crate::linear::matrix::Matrix;

#[cfg(not(feature = "std"))]
use alloc::vec::Vec;

#[cfg(feature = "std")]
use std::vec::Vec;

// ============================================================================
// LU
// ============================================================================

impl Matrix<f64> {
    /// LU decomposition (Doolittle) with partial pivoting.
    ///
    /// Returns `(L, U, P)` such that `P · A = L · U`.
    ///
    /// ```rust
    /// use one_indexed_vec::{vec1, linear::matrix::Matrix};
    ///
    /// let a = Matrix::from_row_major(vec1![2.0, 1.0, 1.0, 3.0], 2, 2);
    /// let (l, u, p) = a.lu();
    /// let pa = p.matmul(&a);
    /// let lu = l.matmul(&u);
    /// for i in 1..=2 {
    ///     for j in 1..=2 {
    ///         assert!((pa.get(i, j) - lu.get(i, j)).abs() < 1e-10);
    ///     }
    /// }
    /// ```
    pub fn lu(&self) -> (Matrix<f64>, Matrix<f64>, Matrix<f64>) {
        let n = self.rows();
        assert_eq!(n, self.cols(), "lu: matrix must be square");

        let mut u = self.clone();
        let mut l = Matrix::identity(n, 0.0, 1.0);
        let mut p = Matrix::identity(n, 0.0, 1.0);

        for k in 1..=n {
            // Partial pivoting
            let mut max_row = k;
            let mut max_val = u.get(k, k).abs();
            for i in (k + 1)..=n {
                if u.get(i, k).abs() > max_val {
                    max_val = u.get(i, k).abs();
                    max_row = i;
                }
            }
            if max_row != k {
                for j in 1..=n {
                    let tmp = u.get(k, j);
                    u.set(k, j, u.get(max_row, j));
                    u.set(max_row, j, tmp);

                    let tmp = p.get(k, j);
                    p.set(k, j, p.get(max_row, j));
                    p.set(max_row, j, tmp);

                    if j < k {
                        let tmp = l.get(k, j);
                        l.set(k, j, l.get(max_row, j));
                        l.set(max_row, j, tmp);
                    }
                }
            }

            for i in (k + 1)..=n {
                let factor = u.get(i, k) / u.get(k, k);
                l.set(i, k, factor);
                for j in k..=n {
                    let new_val = u.get(i, j) - factor * u.get(k, j);
                    u.set(i, j, new_val);
                }
            }
        }
        (l, u, p)
    }
}

// ============================================================================
// Cholesky
// ============================================================================

impl Matrix<f64> {
    /// Cholesky decomposition of a symmetric positive-definite matrix.
    ///
    /// Returns lower-triangular `L` such that `A = L · Lᵀ`.
    ///
    /// # Panics
    ///
    /// Panics if the matrix is not positive definite.
    ///
    /// ```rust
    /// use one_indexed_vec::{vec1, linear::matrix::Matrix};
    ///
    /// // A = [[4, 2], [2, 3]]
    /// let a = Matrix::from_row_major(vec1![4.0, 2.0, 2.0, 3.0], 2, 2);
    /// let l = a.cholesky();
    /// assert!((l.get(1, 1) - 2.0).abs() < 1e-10);
    /// assert!((l.get(2, 1) - 1.0).abs() < 1e-10);
    /// ```
    pub fn cholesky(&self) -> Matrix<f64> {
        let n = self.rows();
        assert_eq!(n, self.cols(), "cholesky: matrix must be square");
        let mut l = Matrix::new(n, n, 0.0);

        for i in 1..=n {
            for j in 1..=i {
                let mut sum = 0.0;
                for k in 1..j {
                    sum += l.get(i, k) * l.get(j, k);
                }
                if i == j {
                    let val = self.get(i, i) - sum;
                    assert!(val > 0.0, "cholesky: matrix not positive definite");
                    l.set(i, j, libm::sqrt(val));
                } else {
                    l.set(i, j, (self.get(i, j) - sum) / l.get(j, j));
                }
            }
        }
        l
    }
}

// ============================================================================
// QR
// ============================================================================

impl Matrix<f64> {
    /// QR decomposition via modified Gram-Schmidt.
    ///
    /// Returns `(Q, R)` such that `A = Q · R`.
    ///
    /// ```rust
    /// use one_indexed_vec::{vec1, linear::matrix::Matrix};
    ///
    /// // Identity QR is identity.
    /// let a = Matrix::from_row_major(vec1![1.0, 0.0, 0.0, 1.0], 2, 2);
    /// let (q, r) = a.qr();
    /// assert!((q.get(1, 1) - 1.0).abs() < 1e-10);
    /// assert!((r.get(1, 1) - 1.0).abs() < 1e-10);
    /// ```
    pub fn qr(&self) -> (Matrix<f64>, Matrix<f64>) {
        let m = self.rows();
        let n = self.cols();
        let mut q = Matrix::new(m, n, 0.0);
        let mut r = Matrix::new(n, n, 0.0);

        for j in 1..=n {
            // Start with column j of self
            let mut v: Vec<f64> = (1..=m).map(|i| self.get(i, j)).collect();

            for i in 1..j {
                // Projection coefficient <q_i, v>
                let mut dot = 0.0;
                for (k, &vk) in v.iter().enumerate() {
                    dot += q.get(k + 1, i) * vk;
                }
                r.set(i, j, dot);
                for (k, vk) in v.iter_mut().enumerate() {
                    *vk -= dot * q.get(k + 1, i);
                }
            }

            // Norm of v
            let mut norm = 0.0;
            for &x in &v {
                norm += x * x;
            }
            norm = libm::sqrt(norm);
            r.set(j, j, norm);
            for (k, &vk) in v.iter().enumerate() {
                q.set(k + 1, j, vk / norm);
            }
        }
        (q, r)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::vec1;

    #[test]
    fn lu_basic() {
        let a = Matrix::from_row_major(vec1![2.0, 1.0, 1.0, 3.0], 2, 2);
        let (l, u, p) = a.lu();
        let pa = p.matmul(&a);
        let lu = l.matmul(&u);
        for i in 1..=2 {
            for j in 1..=2 {
                assert!((pa.get(i, j) - lu.get(i, j)).abs() < 1e-10);
            }
        }
    }

    #[test]
    fn lu_3x3() {
        let a = Matrix::from_row_major(vec1![4.0, 3.0, 2.0, 1.0, 5.0, 6.0, 7.0, 8.0, 9.0], 3, 3);
        let (l, u, p) = a.lu();
        let pa = p.matmul(&a);
        let lu = l.matmul(&u);
        for i in 1..=3 {
            for j in 1..=3 {
                assert!((pa.get(i, j) - lu.get(i, j)).abs() < 1e-10);
            }
        }
    }

    #[test]
    fn cholesky_spd() {
        let a = Matrix::from_row_major(vec1![4.0, 2.0, 2.0, 3.0], 2, 2);
        let l = a.cholesky();
        assert!((l.get(1, 1) - 2.0).abs() < 1e-10);
        assert!((l.get(2, 1) - 1.0).abs() < 1e-10);
        assert!((l.get(2, 2) - 2.0_f64.sqrt()).abs() < 1e-10);

        // Verify L · Lᵀ = A
        let lt = l.transpose();
        let m = l.matmul(&lt);
        for i in 1..=2 {
            for j in 1..=2 {
                assert!((m.get(i, j) - a.get(i, j)).abs() < 1e-10);
            }
        }
    }

    #[test]
    #[should_panic(expected = "not positive definite")]
    fn cholesky_non_pd_panics() {
        let a = Matrix::from_row_major(vec1![1.0, 2.0, 2.0, 1.0], 2, 2);
        let _ = a.cholesky();
    }

    #[test]
    fn qr_identity() {
        let a = Matrix::from_row_major(vec1![1.0, 0.0, 0.0, 1.0], 2, 2);
        let (q, r) = a.qr();
        for i in 1..=2 {
            for j in 1..=2 {
                let expected = if i == j { 1.0 } else { 0.0 };
                assert!((q.get(i, j) - expected).abs() < 1e-10);
                assert!((r.get(i, j) - expected).abs() < 1e-10);
            }
        }
    }
}