Skip to main content

ctrl_freeq/linalg/
mat.rs

1//! A small dense row-major matrix, generic over its element type.
2//!
3//! The Hilbert spaces here are small - 2 to 81 dimensions - so plain loops over a flat `Vec` beat anything
4//! cleverer, and one generic type serves real and complex matrices over `f64` and `Dual` alike.
5
6use crate::autodiff::{C, Scalar};
7use crate::error::{Error, Result};
8
9/// A `rows × cols` matrix stored row-major.
10#[derive(Clone, Debug, PartialEq, Default)]
11pub struct Mat<E> {
12    /// Number of rows.
13    pub rows: usize,
14    /// Number of columns.
15    pub cols: usize,
16    /// Entries, row by row.
17    pub data: Vec<E>,
18}
19
20/// A real matrix.
21pub type RMat<T> = Mat<T>;
22/// A complex matrix.
23pub type CMat<T> = Mat<C<T>>;
24
25impl<E: Copy> Mat<E> {
26    /// A matrix from row-major data.  Fails if the length does not match the shape.
27    pub fn from_vec(rows: usize, cols: usize, data: Vec<E>) -> Result<Self> {
28        if data.len() != rows * cols {
29            return Err(Error::Dimension(format!(
30                "{} entries for a {rows}x{cols} matrix",
31                data.len()
32            )));
33        }
34        Ok(Mat { rows, cols, data })
35    }
36
37    /// A matrix whose entry `(r, c)` is `f(r, c)`.
38    pub fn from_fn(rows: usize, cols: usize, mut f: impl FnMut(usize, usize) -> E) -> Self {
39        let mut data = Vec::with_capacity(rows * cols);
40        for r in 0..rows {
41            for c in 0..cols {
42                data.push(f(r, c));
43            }
44        }
45        Mat { rows, cols, data }
46    }
47
48    /// A column vector.
49    pub fn column(data: Vec<E>) -> Self {
50        Mat {
51            rows: data.len(),
52            cols: 1,
53            data,
54        }
55    }
56
57    /// Entry `(r, c)`.
58    #[inline]
59    pub fn get(&self, r: usize, c: usize) -> E {
60        self.data[r * self.cols + c]
61    }
62
63    /// Set entry `(r, c)`.
64    #[inline]
65    pub fn set(&mut self, r: usize, c: usize, v: E) {
66        self.data[r * self.cols + c] = v;
67    }
68
69    /// Row `r` as a slice.
70    #[inline]
71    pub fn row(&self, r: usize) -> &[E] {
72        &self.data[r * self.cols..(r + 1) * self.cols]
73    }
74
75    /// `(rows, cols)`.
76    #[inline]
77    pub fn shape(&self) -> (usize, usize) {
78        (self.rows, self.cols)
79    }
80
81    /// Whether the matrix is square.
82    #[inline]
83    pub fn is_square(&self) -> bool {
84        self.rows == self.cols
85    }
86
87    /// Apply `f` to every entry.
88    pub fn map<F2>(&self, f: impl Fn(E) -> F2) -> Mat<F2> {
89        Mat {
90            rows: self.rows,
91            cols: self.cols,
92            data: self.data.iter().map(|&v| f(v)).collect(),
93        }
94    }
95
96    /// Column `c` as a vector.
97    pub fn col(&self, c: usize) -> Vec<E> {
98        (0..self.rows).map(|r| self.get(r, c)).collect()
99    }
100
101    /// The transpose.
102    pub fn transpose(&self) -> Self {
103        Mat::from_fn(self.cols, self.rows, |r, c| self.get(c, r))
104    }
105}
106
107impl<T: Scalar> RMat<T> {
108    /// A real matrix of zeros.
109    pub fn zeros(rows: usize, cols: usize) -> Self {
110        Mat {
111            rows,
112            cols,
113            data: vec![T::zero(); rows * cols],
114        }
115    }
116
117    /// Real matrix product.
118    pub fn matmul(&self, o: &Self) -> Result<Self> {
119        check_product(self.shape(), o.shape())?;
120        let mut out = Self::zeros(self.rows, o.cols);
121        for i in 0..self.rows {
122            for k in 0..self.cols {
123                let a = self.get(i, k);
124                if a == T::zero() {
125                    continue;
126                }
127                let orow = o.row(k);
128                let dst = &mut out.data[i * o.cols..(i + 1) * o.cols];
129                for (d, &b) in dst.iter_mut().zip(orow) {
130                    *d += a * b;
131                }
132            }
133        }
134        Ok(out)
135    }
136
137    /// Lift an `f64` real matrix to this scalar type.
138    pub fn lift(m: &RMat<f64>) -> Self {
139        m.map(T::from_f64)
140    }
141}
142
143impl<T: Scalar> CMat<T> {
144    /// A complex matrix of zeros.
145    pub fn zeros(rows: usize, cols: usize) -> Self {
146        Mat {
147            rows,
148            cols,
149            data: vec![C::new(T::zero(), T::zero()); rows * cols],
150        }
151    }
152
153    /// The `n × n` identity.
154    pub fn identity(n: usize) -> Self {
155        let mut m = Self::zeros(n, n);
156        for i in 0..n {
157            m.set(i, i, C::new(T::one(), T::zero()));
158        }
159        m
160    }
161
162    /// Lift an `f64` complex matrix to this scalar type.
163    pub fn lift(m: &CMat<f64>) -> Self {
164        m.map(|z| C::new(T::from_f64(z.re), T::from_f64(z.im)))
165    }
166
167    /// A complex matrix from a real one.
168    pub fn from_real(m: &RMat<T>) -> Self {
169        m.map(|v| C::new(v, T::zero()))
170    }
171
172    /// Complex matrix product.
173    pub fn matmul(&self, o: &Self) -> Result<Self> {
174        check_product(self.shape(), o.shape())?;
175        let mut out = Self::zeros(self.rows, o.cols);
176        let zero = C::new(T::zero(), T::zero());
177        for i in 0..self.rows {
178            for k in 0..self.cols {
179                let a = self.get(i, k);
180                if a == zero {
181                    continue;
182                }
183                let orow = o.row(k);
184                let dst = &mut out.data[i * o.cols..(i + 1) * o.cols];
185                for (d, &b) in dst.iter_mut().zip(orow) {
186                    *d += a * b;
187                }
188            }
189        }
190        Ok(out)
191    }
192
193    /// The conjugate transpose.
194    pub fn adjoint(&self) -> Self {
195        Mat::from_fn(self.cols, self.rows, |r, c| self.get(c, r).conj())
196    }
197
198    /// The entrywise conjugate.
199    pub fn conj(&self) -> Self {
200        self.map(|z| z.conj())
201    }
202
203    /// Every entry times `s`.
204    pub fn scale(&self, s: C<T>) -> Self {
205        self.map(|z| z * s)
206    }
207
208    /// Every entry times the real `s`.
209    pub fn scale_re(&self, s: T) -> Self {
210        self.map(|z| C::new(z.re * s, z.im * s))
211    }
212
213    /// `self + o`.
214    pub fn add(&self, o: &Self) -> Result<Self> {
215        check_same(self.shape(), o.shape())?;
216        Ok(Mat {
217            rows: self.rows,
218            cols: self.cols,
219            data: self.data.iter().zip(&o.data).map(|(&a, &b)| a + b).collect(),
220        })
221    }
222
223    /// `self - o`.
224    pub fn sub(&self, o: &Self) -> Result<Self> {
225        check_same(self.shape(), o.shape())?;
226        Ok(Mat {
227            rows: self.rows,
228            cols: self.cols,
229            data: self.data.iter().zip(&o.data).map(|(&a, &b)| a - b).collect(),
230        })
231    }
232
233    /// `self += s·o`, shapes assumed equal.
234    pub fn axpy(&mut self, s: C<T>, o: &Self) {
235        debug_assert_eq!(self.shape(), o.shape());
236        for (d, &b) in self.data.iter_mut().zip(&o.data) {
237            *d += s * b;
238        }
239    }
240
241    /// `self += s·o` for a real `s`, shapes assumed equal.
242    pub fn axpy_re(&mut self, s: T, o: &Self) {
243        debug_assert_eq!(self.shape(), o.shape());
244        for (d, &b) in self.data.iter_mut().zip(&o.data) {
245            d.re += s * b.re;
246            d.im += s * b.im;
247        }
248    }
249
250    /// The Kronecker product `self ⊗ o`.
251    pub fn kron(&self, o: &Self) -> Self {
252        Mat::from_fn(self.rows * o.rows, self.cols * o.cols, |r, c| {
253            self.get(r / o.rows, c / o.cols) * o.get(r % o.rows, c % o.cols)
254        })
255    }
256
257    /// The trace.
258    pub fn trace(&self) -> C<T> {
259        (0..self.rows.min(self.cols)).fold(C::new(T::zero(), T::zero()), |acc, i| acc + self.get(i, i))
260    }
261
262    /// `Σ conj(self_ij)·o_ij`, the Frobenius inner product.
263    pub fn inner(&self, o: &Self) -> C<T> {
264        self.data
265            .iter()
266            .zip(&o.data)
267            .fold(C::new(T::zero(), T::zero()), |acc, (&a, &b)| acc + a.conj() * b)
268    }
269
270    /// The 1-norm (largest column sum of magnitudes) of the value parts.
271    pub fn norm1(&self) -> f64 {
272        (0..self.cols)
273            .map(|c| {
274                (0..self.rows)
275                    .map(|r| {
276                        let z = self.get(r, c);
277                        z.re.re().hypot(z.im.re())
278                    })
279                    .sum::<f64>()
280            })
281            .fold(0.0, f64::max)
282    }
283}
284
285impl CMat<f64> {
286    /// Largest entrywise magnitude of `self - o`.
287    pub fn max_abs_diff(&self, o: &Self) -> f64 {
288        self.data
289            .iter()
290            .zip(&o.data)
291            .map(|(a, b)| (a - b).norm())
292            .fold(0.0, f64::max)
293    }
294
295    /// Whether the matrix equals its conjugate transpose to within `tol`.
296    pub fn is_hermitian(&self, tol: f64) -> bool {
297        self.is_square() && self.max_abs_diff(&self.adjoint()) <= tol
298    }
299}
300
301fn check_product(a: (usize, usize), b: (usize, usize)) -> Result<()> {
302    if a.1 != b.0 {
303        return Err(Error::Dimension(format!(
304            "cannot multiply {}x{} by {}x{}",
305            a.0, a.1, b.0, b.1
306        )));
307    }
308    Ok(())
309}
310
311fn check_same(a: (usize, usize), b: (usize, usize)) -> Result<()> {
312    if a != b {
313        return Err(Error::Dimension(format!(
314            "shapes {}x{} and {}x{} differ",
315            a.0, a.1, b.0, b.1
316        )));
317    }
318    Ok(())
319}
320
321/// Solve `A X = B` by LU decomposition with partial pivoting on the value parts.
322pub fn solve<T: Scalar>(a: &CMat<T>, b: &CMat<T>) -> Result<CMat<T>> {
323    let n = a.rows;
324    if !a.is_square() || b.rows != n {
325        return Err(Error::Dimension(format!(
326            "cannot solve a {}x{} system for {}x{}",
327            a.rows, a.cols, b.rows, b.cols
328        )));
329    }
330    let mut lu = a.clone();
331    let mut x = b.clone();
332    let m = b.cols;
333    let mag = |z: C<T>| z.re.re().hypot(z.im.re());
334    for k in 0..n {
335        let (p, best) = (k..n)
336            .map(|r| (r, mag(lu.get(r, k))))
337            .fold((k, -1.0), |acc, cur| if cur.1 > acc.1 { cur } else { acc });
338        if best == 0.0 || !best.is_finite() {
339            return Err(Error::Numerical("singular matrix in linear solve".into()));
340        }
341        if p != k {
342            for c in 0..n {
343                lu.data.swap(k * n + c, p * n + c);
344            }
345            for c in 0..m {
346                x.data.swap(k * m + c, p * m + c);
347            }
348        }
349        let pivot = lu.get(k, k);
350        for r in k + 1..n {
351            let factor = lu.get(r, k) / pivot;
352            if factor == C::new(T::zero(), T::zero()) {
353                continue;
354            }
355            for c in k..n {
356                let v = lu.get(r, c) - factor * lu.get(k, c);
357                lu.set(r, c, v);
358            }
359            for c in 0..m {
360                let v = x.get(r, c) - factor * x.get(k, c);
361                x.set(r, c, v);
362            }
363        }
364    }
365    for k in (0..n).rev() {
366        let pivot = lu.get(k, k);
367        for c in 0..m {
368            let mut v = x.get(k, c);
369            for j in k + 1..n {
370                v -= lu.get(k, j) * x.get(j, c);
371            }
372            x.set(k, c, v / pivot);
373        }
374    }
375    Ok(x)
376}
377
378#[cfg(test)]
379mod tests {
380    use super::*;
381
382    fn c(re: f64, im: f64) -> C<f64> {
383        C::new(re, im)
384    }
385
386    #[test]
387    fn solve_recovers_a_known_solution() {
388        let a = Mat::from_vec(
389            3,
390            3,
391            vec![
392                c(0.0, 1.0),
393                c(2.0, 0.0),
394                c(1.0, -1.0),
395                c(3.0, 0.0),
396                c(1.0, 1.0),
397                c(0.0, 0.0),
398                c(1.0, 0.0),
399                c(0.0, 0.0),
400                c(2.0, 2.0),
401            ],
402        )
403        .unwrap();
404        let x = Mat::from_vec(
405            3,
406            2,
407            vec![
408                c(1.0, 0.0),
409                c(0.0, 1.0),
410                c(-2.0, 0.5),
411                c(1.0, 1.0),
412                c(0.3, 0.0),
413                c(2.0, -1.0),
414            ],
415        )
416        .unwrap();
417        let b = a.matmul(&x).unwrap();
418        let got = solve(&a, &b).unwrap();
419        assert!(got.max_abs_diff(&x) < 1e-13);
420    }
421
422    #[test]
423    fn singular_systems_are_reported() {
424        let a = CMat::<f64>::zeros(2, 2);
425        assert!(matches!(solve(&a, &CMat::identity(2)), Err(Error::Numerical(_))));
426    }
427
428    #[test]
429    fn kron_orders_the_first_factor_as_most_significant() {
430        let x = Mat::from_vec(2, 2, vec![c(0.0, 0.0), c(1.0, 0.0), c(1.0, 0.0), c(0.0, 0.0)]).unwrap();
431        let id = CMat::<f64>::identity(2);
432        let k = x.kron(&id);
433        // X ⊗ I maps |00> (index 0) to |10> (index 2).
434        assert_eq!(k.get(2, 0), c(1.0, 0.0));
435        assert_eq!(k.get(1, 0), c(0.0, 0.0));
436    }
437
438    #[test]
439    fn shape_mismatches_are_errors() {
440        let a = CMat::<f64>::zeros(2, 3);
441        assert!(matches!(a.matmul(&a), Err(Error::Dimension(_))));
442        assert!(matches!(Mat::from_vec(2, 2, vec![1.0; 3]), Err(Error::Dimension(_))));
443    }
444}