Skip to main content

section_properties/fea/solver/impls/
dense_gaussian.rs

1//! Dense Gaussian elimination solver (for small systems)
2use crate::fea::SparseMatrix;
3use crate::fea::solver::{LinearSolver, SolverCapabilities, SolverError};
4
5/// Dense Gaussian elimination solver (for small systems)
6pub struct DenseGaussianSolver {
7    n: usize,
8    a: Vec<Vec<f64>>,
9    pivot: Vec<usize>,
10    scale: f64,
11}
12
13impl DenseGaussianSolver {
14    pub fn new() -> Self {
15        Self {
16            n: 0,
17            a: Vec::new(),
18            pivot: Vec::new(),
19            scale: 1.0,
20        }
21    }
22}
23
24impl LinearSolver for DenseGaussianSolver {
25    fn name(&self) -> &'static str {
26        "dense"
27    }
28
29    fn capabilities(&self) -> SolverCapabilities {
30        SolverCapabilities::dense()
31    }
32
33    fn factor(&mut self, matrix: &SparseMatrix) -> Result<(), SolverError> {
34        // Invalidate any previous factorization first, so a failed factor()
35        // cannot leave stale factors usable by a later solve().
36        self.n = 0;
37        self.a = Vec::new();
38        self.pivot = Vec::new();
39
40        let n = matrix.n;
41        if n == 0 {
42            return Err(SolverError::invalid_input("Empty matrix"));
43        }
44
45        // Convert to dense
46        let mut a = vec![vec![0.0f64; n]; n];
47        for i in 0..n {
48            for k in matrix.row_ptr[i]..matrix.row_ptr[i + 1] {
49                let j = matrix.csr_cols[k];
50                a[i][j] = matrix.csr_vals[k];
51            }
52        }
53
54        // Compute scale for pivot tolerance
55        let mut scale = 0.0f64;
56        for i in 0..n {
57            for j in 0..n {
58                scale = scale.max(a[i][j].abs());
59            }
60        }
61        self.scale = scale;
62
63        // Use scale for pivot tolerance; if scale is 0, use PIVOT_TOL_BASE directly
64        let pivot_scale = if scale == 0.0 { 1.0 } else { scale };
65
66        // Gaussian elimination with partial pivoting (in-place LU factorization)
67        let mut pivot = (0..n).collect::<Vec<usize>>();
68
69        for k in 0..n {
70            // Partial pivoting
71            let mut max_row = k;
72            let mut max_val = a[k][k].abs();
73            for i in (k + 1)..n {
74                let v = a[i][k].abs();
75                if v > max_val {
76                    max_val = v;
77                    max_row = i;
78                }
79            }
80
81            let pivot_tol = crate::fea::PIVOT_TOL_BASE * pivot_scale;
82            if max_val <= pivot_tol {
83                return Err(SolverError::singular(format!(
84                    "Singular or near-singular matrix at column {}: max pivot = {:.2e}, tolerance = {:.2e}",
85                    k, max_val, pivot_tol
86                )));
87            }
88
89            if max_row != k {
90                a.swap(k, max_row);
91                pivot.swap(k, max_row);
92            }
93
94            // Eliminate: store multipliers in lower triangular, upper triangular becomes U
95            for i in (k + 1)..n {
96                let factor = a[i][k] / a[k][k];
97                a[i][k] = factor; // Store L multiplier
98                for j in (k + 1)..n {
99                    a[i][j] -= factor * a[k][j];
100                }
101            }
102        }
103
104        self.n = n;
105        self.a = a;
106        self.pivot = pivot;
107
108        Ok(())
109    }
110
111    fn solve(&self, rhs: &[f64]) -> Result<Vec<f64>, SolverError> {
112        let n = self.n;
113        if n == 0 {
114            return Err(SolverError::not_factorized());
115        }
116        if rhs.len() != n {
117            return Err(SolverError::dimension_mismatch(n, rhs.len()));
118        }
119
120        // Check for NaN/Inf
121        for (i, &val) in rhs.iter().enumerate() {
122            if !val.is_finite() {
123                return Err(SolverError::non_finite(i));
124            }
125        }
126
127        // Apply permutation: Pb
128        let mut x = vec![0.0f64; n];
129        for i in 0..n {
130            x[i] = rhs[self.pivot[i]];
131        }
132
133        // Forward substitution
134        for i in 0..n {
135            let mut sum = 0.0;
136            for j in 0..i {
137                sum += self.a[i][j] * x[j];
138            }
139            x[i] -= sum;
140        }
141
142        // Backward substitution
143        for i in (0..n).rev() {
144            let mut sum = 0.0;
145            for j in (i + 1)..n {
146                sum += self.a[i][j] * x[j];
147            }
148            let pivot_val = self.a[i][i];
149            if !pivot_val.is_finite() || pivot_val == 0.0 {
150                return Err(SolverError::singular(format!(
151                    "Zero or invalid diagonal at row {}: {:.2e}",
152                    i, pivot_val
153                )));
154            }
155            x[i] = (x[i] - sum) / pivot_val;
156        }
157
158        // NOTE: `x` is already the solution in the original (un-permuted) order.
159        // The forward substitution applied the row permutation `P` to the RHS,
160        // and the elimination produced `P A = L U`; solving `L U x = P b` yields
161        // `x` directly in the original variable order. No inverse permutation is
162        // required — applying one here would scramble the solution.
163
164        Ok(x)
165    }
166}