Skip to main content

section_properties/fea/solver/impls/
iccg.rs

1//! Incomplete Cholesky CG solver
2use crate::fea::SparseMatrix;
3use crate::fea::solver::{LinearSolver, SolverCapabilities, SolverError};
4
5/// Incomplete Cholesky CG solver
6pub struct IccgSolver {
7    n: usize,
8    max_iter: usize,
9    tol: f64,
10    l_diag: Vec<f64>,
11    l_lower: Vec<f64>,
12    l_row_ptr: Vec<usize>,
13    l_col_idx: Vec<usize>,
14    matrix: Option<SparseMatrix>,
15}
16
17impl IccgSolver {
18    pub fn new() -> Self {
19        Self {
20            n: 0,
21            max_iter: 10000,
22            tol: 1e-10,
23            l_diag: Vec::new(),
24            l_lower: Vec::new(),
25            l_row_ptr: Vec::new(),
26            l_col_idx: Vec::new(),
27            matrix: None,
28        }
29    }
30
31    pub fn with_params(mut self, max_iter: usize, tol: f64) -> Self {
32        self.max_iter = max_iter;
33        self.tol = tol;
34        self
35    }
36}
37
38impl LinearSolver for IccgSolver {
39    fn name(&self) -> &'static str {
40        "iccg"
41    }
42
43    fn capabilities(&self) -> SolverCapabilities {
44        SolverCapabilities::iccg()
45    }
46
47    fn factor(&mut self, matrix: &SparseMatrix) -> Result<(), SolverError> {
48        // Invalidate any previous factorization first, so a failed factor()
49        // cannot leave stale preconditioner/factors usable by a later solve().
50        self.matrix = None;
51        self.n = 0;
52
53        let n = matrix.n;
54        if n == 0 {
55            return Err(SolverError::invalid_input("Empty matrix"));
56        }
57
58        // Check symmetry
59        if !matrix.is_symmetric(1e-12) {
60            return Err(SolverError::not_symmetric());
61        }
62
63        // Incomplete Cholesky factorization (IC(0))
64        let mut l_diag = vec![0.0f64; n];
65        let mut l_lower = Vec::new();
66        let mut l_col_idx = Vec::new();
67        let mut l_row_ptr = vec![0usize; n + 1];
68
69        // Count nonzeros in lower triangle
70        for i in 0..n {
71            for k in matrix.row_ptr[i]..matrix.row_ptr[i + 1] {
72                let j = matrix.csr_cols[k];
73                if j <= i {
74                    l_row_ptr[i + 1] += 1;
75                }
76            }
77        }
78
79        for i in 1..=n {
80            l_row_ptr[i] += l_row_ptr[i - 1];
81        }
82
83        l_lower.resize(l_row_ptr[n], 0.0);
84        l_col_idx.resize(l_row_ptr[n], 0);
85
86        // Fill column indices
87        let mut pos = l_row_ptr.clone();
88        for i in 0..n {
89            for k in matrix.row_ptr[i]..matrix.row_ptr[i + 1] {
90                let j = matrix.csr_cols[k];
91                if j <= i {
92                    let idx = pos[i];
93                    l_col_idx[idx] = j;
94                    pos[i] += 1;
95                }
96            }
97        }
98
99        // IC(0) factorization (Cholesky form: L L^T ≈ A, L_ii = sqrt(d_i))
100        for i in 0..n {
101            // Compute off-diagonals FIRST (diagonal depends on them).
102            // Guard against empty rows (e.g. zero diagonal skipped by compress()).
103            if l_row_ptr[i + 1] > l_row_ptr[i] {
104                for idx in l_row_ptr[i]..l_row_ptr[i + 1] - 1 {
105                    let j = l_col_idx[idx];
106
107                    // Find A_ij
108                    let mut a_ij = 0.0;
109                    for k in matrix.row_ptr[i]..matrix.row_ptr[i + 1] {
110                        if matrix.csr_cols[k] == j {
111                            a_ij = matrix.csr_vals[k];
112                            break;
113                        }
114                    }
115                    let mut sum = a_ij;
116
117                    // Subtract contributions: sum -= Σ_{k<j} L_ik * L_jk
118                    for idx2 in l_row_ptr[j]..l_row_ptr[j + 1] {
119                        let k = l_col_idx[idx2];
120                        if k < j {
121                            // Find L_ik
122                            for idx3 in l_row_ptr[i]..l_row_ptr[i + 1] {
123                                if l_col_idx[idx3] == k {
124                                    sum -= l_lower[idx3] * l_lower[idx2];
125                                    break;
126                                }
127                            }
128                        }
129                    }
130
131                    l_lower[idx] = sum / l_diag[j];
132                }
133            }
134
135            // Compute diagonal AFTER off-diagonals.
136            let mut sum = 0.0;
137            for k in matrix.row_ptr[i]..matrix.row_ptr[i + 1] {
138                let j = matrix.csr_cols[k];
139                let val = matrix.csr_vals[k];
140                if j == i {
141                    sum += val;
142                } else if j < i {
143                    // Find L_ij in our structure
144                    for idx in l_row_ptr[i]..l_row_ptr[i + 1] {
145                        if l_col_idx[idx] == j {
146                            sum -= l_lower[idx] * l_lower[idx];
147                            break;
148                        }
149                    }
150                }
151            }
152
153            if sum <= 0.0 || !sum.is_finite() {
154                return Err(SolverError::singular(format!(
155                    "IC(0) breakdown at row {i}: non-positive diagonal ({:.2e})",
156                    sum
157                )));
158            } else {
159                l_diag[i] = sum.sqrt();
160            }
161        }
162
163        self.n = n;
164        self.l_diag = l_diag;
165        self.l_lower = l_lower;
166        self.l_row_ptr = l_row_ptr;
167        self.l_col_idx = l_col_idx;
168        self.matrix = Some(matrix.clone());
169
170        Ok(())
171    }
172
173    fn solve(&self, rhs: &[f64]) -> Result<Vec<f64>, SolverError> {
174        let matrix = self
175            .matrix
176            .as_ref()
177            .ok_or_else(|| SolverError::not_factorized())?;
178        let n = self.n;
179
180        if rhs.len() != n {
181            return Err(SolverError::dimension_mismatch(n, rhs.len()));
182        }
183
184        // Check for NaN/Inf
185        for (i, &val) in rhs.iter().enumerate() {
186            if !val.is_finite() {
187                return Err(SolverError::non_finite(i));
188            }
189        }
190
191        // Scale-aware convergence: use relative residual ||r|| / ||b|| < tol,
192        // matching the raw iccg_solve() semantics.  The previous code used the
193        // absolute preconditioned residual sqrt(r^T M^{-1} r) < tol, which is
194        // scale-dependent and uses a preconditioned quantity rather than the
195        // true residual.
196        let b_norm = rhs.iter().map(|v| v * v).sum::<f64>().sqrt();
197        if b_norm == 0.0 || !b_norm.is_finite() {
198            return Ok(vec![0.0f64; n]);
199        }
200        let conv_tol = self.tol * b_norm;
201
202        // Preconditioned CG with IC(0)
203        let mut x = vec![0.0f64; n];
204        let mut r = rhs.to_vec();
205
206        // Apply preconditioner: M = L L^T
207        let mut z = self.apply_preconditioner(&r)?;
208        let mut p = z.clone();
209
210        let mut rz_old = r.iter().zip(z.iter()).map(|(ri, zi)| ri * zi).sum::<f64>();
211
212        // Check true residual for initial convergence.
213        let r_norm_sq = r.iter().map(|v| v * v).sum::<f64>();
214        if r_norm_sq.sqrt() < conv_tol {
215            return Ok(x);
216        }
217
218        // Scale of initial preconditioned residual for relative convergence.
219        let rz_scale = rz_old.abs().sqrt();
220
221        for _iter in 0..self.max_iter {
222            // A * p
223            let mut ap = vec![0.0f64; n];
224            for i in 0..n {
225                let mut sum = 0.0;
226                for k in matrix.row_ptr[i]..matrix.row_ptr[i + 1] {
227                    let j = matrix.csr_cols[k];
228                    sum += matrix.csr_vals[k] * p[j];
229                }
230                ap[i] = sum;
231            }
232
233            let p_ap: f64 = p.iter().zip(ap.iter()).map(|(pi, api)| pi * api).sum();
234            if p_ap <= 0.0 {
235                return Err(SolverError::singular(
236                    "Matrix not positive definite (p^T A p <= 0)".to_string(),
237                ));
238            }
239
240            let alpha = rz_old / p_ap;
241
242            for i in 0..n {
243                x[i] += alpha * p[i];
244                r[i] -= alpha * ap[i];
245            }
246
247            z = self.apply_preconditioner(&r)?;
248            let rz_new = r.iter().zip(z.iter()).map(|(ri, zi)| ri * zi).sum::<f64>();
249
250            // Check true residual for convergence (not preconditioned residual).
251            // Dual criterion: (1) true relative residual ||r|| < tol * ||b||,
252            // (2) relative preconditioned residual sqrt(r^T z) < tol * sqrt(rz₀).
253            // The secondary criterion catches early convergence when the
254            // preconditioned residual is small but the true residual is
255            // temporarily inflated by cancellation — avoiding unnecessary
256            // extra iterations.  Both criteria are scale-aware (Phase 59).
257            let r_norm_sq = r.iter().map(|v| v * v).sum::<f64>();
258            if r_norm_sq.sqrt() < conv_tol || rz_new.abs().sqrt() < self.tol * rz_scale {
259                return Ok(x);
260            }
261
262            let beta = rz_new / rz_old;
263            for i in 0..n {
264                p[i] = z[i] + beta * p[i];
265            }
266
267            rz_old = rz_new;
268        }
269
270        Err(SolverError::not_converged())
271    }
272}
273
274impl IccgSolver {
275    fn apply_preconditioner(&self, r: &[f64]) -> Result<Vec<f64>, SolverError> {
276        let n = self.n;
277        let mut y = vec![0.0f64; n];
278
279        // Forward: L y = r
280        for i in 0..n {
281            let mut sum = r[i];
282            for idx in self.l_row_ptr[i]..self.l_row_ptr[i + 1] - 1 {
283                let j = self.l_col_idx[idx];
284                sum -= self.l_lower[idx] * y[j];
285            }
286            y[i] = sum / self.l_diag[i];
287        }
288
289        // Backward: L^T z = y via scattered updates.
290        let mut z = y;
291        for i in (0..n).rev() {
292            let zi = z[i] / self.l_diag[i];
293            z[i] = zi;
294            for idx in self.l_row_ptr[i]..self.l_row_ptr[i + 1] - 1 {
295                let j = self.l_col_idx[idx];
296                z[j] -= self.l_lower[idx] * zi;
297            }
298        }
299
300        Ok(z)
301    }
302}