diffsol_la/linear_solver/nalgebra/
reusable_lu.rs

1use nalgebra::linalg::{gauss_step, gauss_step_swap};
2use nalgebra::{Dim, Dyn, Matrix as NaMatrix, StorageMut};
3
4use crate::context::broadcast_batch;
5use crate::{
6    error::LaError, linear_solver_error, matrix::dense_nalgebra_serial::NalgebraMat, Context,
7    LinearOp, LinearSolver, Matrix, NalgebraContext, NalgebraScalar, NalgebraVec,
8};
9
10// `gauss_step`/`gauss_step_swap` are `#[doc(hidden)]` in nalgebra (not officially documented,
11// though `pub fn` and re-exported at the crate root) -- they are the exact elimination steps
12// `nalgebra::linalg::LU::new` calls internally.
13
14/// LU factorization state for a (possibly batched) [NalgebraMat], factorized and solved
15/// entirely in place: `a` is written to directly by `LinearOp::matrix_inplace` in
16/// [ReusableLU::set_linearisation] (no separate scratch matrix + clone, unlike
17/// [NalgebraNativeLU](crate::NalgebraNativeLU)), then decomposed in place, batch block by
18/// batch block.
19struct BatchLu<T: NalgebraScalar> {
20    a: NalgebraMat<T>,
21    /// Row-swap history per batch (replaces nalgebra's `PermutationSequence`), reused across
22    /// `factor` calls.
23    piv: Vec<Vec<(usize, usize)>>,
24}
25
26impl<T: NalgebraScalar> BatchLu<T> {
27    fn new(a: NalgebraMat<T>) -> Self {
28        let nbatch = a.context.nbatch();
29        Self {
30            a,
31            piv: vec![Vec::new(); nbatch],
32        }
33    }
34
35    fn nbatch(&self) -> usize {
36        self.piv.len()
37    }
38
39    fn logical_ncols(&self) -> usize {
40        self.a.data.ncols() / self.nbatch()
41    }
42
43    /// Factorize `self.a` in place, one square batch block at a time. Body copied from
44    /// `nalgebra::linalg::LU::new`, run against a mutable view of each block instead of an
45    /// owned matrix.
46    fn factor(&mut self) {
47        let ncols = self.logical_ncols();
48        for batch in 0..self.nbatch() {
49            let piv = &mut self.piv[batch];
50            piv.clear();
51            let mut block = self.a.data.columns_mut(batch * ncols, ncols);
52            for i in 0..ncols {
53                let p = block.view_range(i.., i).icamax() + i;
54                let diag = block[(p, i)];
55                if diag.is_zero() {
56                    continue;
57                }
58                if p != i {
59                    piv.push((i, p));
60                    block.columns_range_mut(..i).swap_rows(i, p);
61                    gauss_step_swap(&mut block, diag, i, p);
62                } else {
63                    gauss_step(&mut block, diag, i);
64                }
65            }
66        }
67    }
68
69    /// Solve `block(batch) * x = b` in place, `b` holding the input and receiving the
70    /// solution. Body copied from `nalgebra::linalg::LU::solve_mut`.
71    fn solve_block<C2: Dim, S2: StorageMut<T, Dyn, C2>>(
72        &self,
73        batch: usize,
74        b: &mut NaMatrix<T, Dyn, C2, S2>,
75    ) -> bool {
76        let ncols = self.logical_ncols();
77        let block = self.a.data.columns(batch * ncols, ncols);
78        for &(i, p) in &self.piv[batch] {
79            b.swap_rows(i, p);
80        }
81        let _ = block.solve_lower_triangular_with_diag_mut(b, T::one());
82        block.solve_upper_triangular_mut(b)
83    }
84}
85
86/// The default nalgebra [LinearSolver], exported as [NalgebraLU](crate::NalgebraLU). Factorizes
87/// its matrix entirely in place (no per-call matrix clone + fresh permutation sequence, both of
88/// which `nalgebra::linalg::LU::new` allocates every time). See
89/// [NalgebraNativeLU](crate::NalgebraNativeLU) for the allocating equivalent, kept for
90/// comparison/benchmarking.
91pub struct ReusableLU<T>
92where
93    T: NalgebraScalar,
94{
95    lu: Option<BatchLu<T>>,
96}
97
98impl<T: NalgebraScalar> Default for ReusableLU<T> {
99    fn default() -> Self {
100        Self { lu: None }
101    }
102}
103
104impl<T: NalgebraScalar> LinearSolver<NalgebraMat<T>> for ReusableLU<T> {
105    fn solve_in_place(&self, state: &mut NalgebraVec<T>) -> Result<(), LaError> {
106        let Some(lu) = self.lu.as_ref() else {
107            return Err(linear_solver_error!(LuNotInitialized));
108        };
109        state
110            .context
111            .assert_broadcastable_into(lu.nbatch(), "lu_solve");
112        if state.context.nbatch() == 1 {
113            if lu.solve_block(0, &mut state.data) {
114                return Ok(());
115            }
116            return Err(linear_solver_error!(LuSolveFailed));
117        }
118        let nb = state.context.nbatch();
119        for batch in 0..nb {
120            let mut state_batch = state.data.column_mut(batch);
121            if !lu.solve_block(broadcast_batch(batch, lu.nbatch(), nb), &mut state_batch) {
122                return Err(linear_solver_error!(LuSolveFailed));
123            }
124        }
125        Ok(())
126    }
127
128    fn set_linearisation<
129        C: LinearOp<T = T, V = NalgebraVec<T>, M = NalgebraMat<T>, C = NalgebraContext>,
130    >(
131        &mut self,
132        op: &C,
133    ) {
134        let lu = self.lu.as_mut().expect("Matrix not set");
135        op.matrix_inplace(&mut lu.a);
136        lu.factor();
137    }
138
139    fn set_sparsity<
140        C: LinearOp<T = T, V = NalgebraVec<T>, M = NalgebraMat<T>, C = NalgebraContext>,
141    >(
142        &mut self,
143        op: &C,
144    ) {
145        let ncols = op.ncols();
146        let nrows = op.nrows();
147        let a = C::M::new_from_sparsity(nrows, ncols, op.sparsity(), *op.context());
148        self.lu = Some(BatchLu::new(a));
149    }
150}
151
152#[cfg(test)]
153mod tests {
154    use super::*;
155    use crate::{
156        linear_solver::tests::{diagonal_op, test_grouped_lu_solve, test_narrow_state_lu_solve},
157        Vector,
158    };
159
160    #[test]
161    fn test_grouped_lu() {
162        test_grouped_lu_solve::<NalgebraMat<f64>, ReusableLU<f64>>(NalgebraContext::with_nbatch(2));
163    }
164
165    #[test]
166    fn test_lu() {
167        let mut s = ReusableLU::<f64>::default();
168        let op = diagonal_op::<NalgebraMat<f64>>(2.0);
169        s.set_sparsity(&op);
170        s.set_linearisation(&op);
171        let b = NalgebraVec::from_vec(vec![2.0, 4.0], Default::default());
172        let x = s.solve(&b).unwrap();
173        x.assert_eq_st(
174            &NalgebraVec::from_vec(vec![1.0, 2.0], Default::default()),
175            1e-10,
176        );
177    }
178
179    /// A square matrix stored as a [NalgebraMat], built by direct indexing.
180    fn make_mat(n: usize, data: &[f64]) -> NalgebraMat<f64> {
181        let mut m: NalgebraMat<f64> = Matrix::new_from_sparsity(n, n, None, Default::default());
182        for i in 0..n {
183            for j in 0..n {
184                m[(i, j)] = data[i * n + j];
185            }
186        }
187        m
188    }
189
190    /// `ReusableLU` should agree with `nalgebra::linalg::LU` on the same matrices, including
191    /// across repeated `factor` calls that exercise the in-place refactor path, and including
192    /// cases that require row pivoting (first case has a zero (0,0) entry).
193    #[test]
194    fn matches_nalgebra_lu() {
195        let cases: Vec<(usize, Vec<f64>)> = vec![
196            (1, vec![2.0]),
197            (2, vec![0.0, 1.0, 1.0, 1.0]),
198            (3, vec![2.0, 1.0, 1.0, 4.0, 3.0, 3.0, 8.0, 7.0, 9.0]),
199            (
200                5,
201                vec![
202                    2.0, 0.0, 1.0, 0.0, 0.0, 1.0, 3.0, 0.0, 0.0, 1.0, 0.0, 1.0, 4.0, 1.0, 0.0, 0.0,
203                    0.0, 2.0, 5.0, 1.0, 1.0, 0.0, 0.0, 1.0, 6.0,
204                ],
205            ),
206        ];
207        for (n, data) in cases {
208            let nm = make_mat(n, &data);
209            let b = nalgebra::DMatrix::<f64>::from_fn(n, 1, |i, _| (i + 1) as f64);
210
211            let mut lu = BatchLu::new(nm.clone());
212            lu.factor();
213            let mut got = b.clone();
214            assert!(lu.solve_block(0, &mut got));
215
216            let m = nalgebra::DMatrix::from_row_slice(n, n, &data);
217            let expected_lu = m.lu();
218            let mut expected = b.clone();
219            assert!(expected_lu.solve_mut(&mut expected));
220
221            for i in 0..n {
222                assert!(
223                    (got[(i, 0)] - expected[(i, 0)]).abs() < 1e-9,
224                    "n={n} row={i}: got {} expected {}",
225                    got[(i, 0)],
226                    expected[(i, 0)]
227                );
228            }
229
230            // refactoring in place (buffer reuse path) should give the same answer again --
231            // `a` must be repopulated first, mirroring what `set_linearisation` does via
232            // `matrix_inplace` before each `factor()` call (factoring an already-factored
233            // matrix again is not a supported operation).
234            lu.a = make_mat(n, &data);
235            lu.factor();
236            let mut got2 = b.clone();
237            assert!(lu.solve_block(0, &mut got2));
238            for i in 0..n {
239                assert!((got2[(i, 0)] - expected[(i, 0)]).abs() < 1e-9);
240            }
241        }
242    }
243
244    #[test]
245    fn singular_matrix_fails_like_nalgebra_lu() {
246        let nm = make_mat(2, &[1.0, 2.0, 2.0, 4.0]);
247        let mut lu = BatchLu::new(nm);
248        lu.factor();
249        let mut b = nalgebra::DMatrix::<f64>::from_row_slice(2, 1, &[1.0, 2.0]);
250        assert!(!lu.solve_block(0, &mut b));
251    }
252
253    #[test]
254    #[should_panic(expected = "incompatible nbatch")]
255    fn test_narrow_state_lu() {
256        test_narrow_state_lu_solve::<NalgebraMat<f64>, ReusableLU<f64>>(
257            NalgebraContext::with_nbatch(2),
258        );
259    }
260}
diffsol_la/linear_solver/nalgebra/reusable_lu.rs

diffsol_la/linear_solver/nalgebra/
reusable_lu.rs
