Skip to main content

section_properties/fea/
solvers.rs

1//! Solver backends. See module docs in [`crate::fea`].
2
3use super::{CgResult, CgStatus, SkylineLdlt, SparseMatrix, cg_solve};
4use crate::fea::solver::SolverError;
5
6/// Selectable solver backend.
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8pub enum SolverKind {
9    /// General sparse LU with partial pivoting.
10    SparseLu,
11    /// Profile LDL^T (symmetric systems).
12    SkylineLdlt,
13    /// Jacobi-preconditioned conjugate gradient.
14    PcG,
15    /// Incomplete-Cholesky (IC(0)) preconditioned conjugate gradient.
16    Iccg,
17    /// Intel MKL PARDISO via FFI (requires the `pardiso` feature and MKL).
18    Pardiso,
19}
20
21/// Direct solver types (factor once, solve many).
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub enum DirectSolver {
24    SparseLu,
25    SkylineLdlt,
26    #[cfg(feature = "pardiso")]
27    Pardiso,
28}
29
30/// Iterative solver types.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum IterativeSolver {
33    PcG,
34    Iccg,
35}
36
37/// A factored direct solver able to solve A x = b for multiple right-hand sides.
38pub enum FactoredDirectSolver {
39    Lu(SparseLu),
40    Ldlt(SkylineLdlt),
41    #[cfg(feature = "pardiso")]
42    Pardiso(crate::fea::solvers::pardiso::PardisoSolver),
43}
44
45impl FactoredDirectSolver {
46    /// Factor `matrix` with the selected direct backend.
47    pub fn factor(kind: DirectSolver, matrix: &SparseMatrix) -> Result<Self, SolverError> {
48        match kind {
49            DirectSolver::SparseLu => Ok(FactoredDirectSolver::Lu(
50                SparseLu::factor(matrix).map_err(|e| SolverError::FactorizationFailed(e))?,
51            )),
52            DirectSolver::SkylineLdlt => Ok(FactoredDirectSolver::Ldlt(
53                SkylineLdlt::factor(matrix)
54                    .map_err(|e| SolverError::FactorizationFailed(e.to_string()))?,
55            )),
56            #[cfg(feature = "pardiso")]
57            DirectSolver::Pardiso => {
58                // PARDISO requires the constraint vector for the augmented system
59                // This is a limitation - we'll need to handle this separately
60                Err(SolverError::NotImplemented(
61                    "PARDISO factor requires constraint vector. Use DirectLagrangeSolver instead."
62                        .to_string(),
63                ))
64            }
65        }
66    }
67
68    /// Direct solve (LU / LDLT). Returns error if solver fails.
69    pub fn solve(&self, b: &[f64]) -> Result<Vec<f64>, SolverError> {
70        match self {
71            FactoredDirectSolver::Lu(lu) => lu.solve(b).map_err(SolverError::SolveFailed),
72            FactoredDirectSolver::Ldlt(l) => l
73                .solve(b)
74                .map_err(|e| SolverError::SolveFailed(e.to_string())),
75            #[cfg(feature = "pardiso")]
76            FactoredDirectSolver::Pardiso(_) => Err(SolverError::NotImplemented(
77                "PARDISO solve not implemented in this context".to_string(),
78            )),
79        }
80    }
81}
82
83/// Iterative solver for multiple right-hand sides.
84pub struct IterativeSolverInstance {
85    kind: IterativeSolver,
86    matrix: SparseMatrix,
87    max_iter: usize,
88    tol: f64,
89}
90
91impl IterativeSolverInstance {
92    /// Create a new iterative solver instance.
93    pub fn new(kind: IterativeSolver, matrix: SparseMatrix, max_iter: usize, tol: f64) -> Self {
94        Self {
95            kind,
96            matrix,
97            max_iter,
98            tol,
99        }
100    }
101
102    /// Solve A x = b. Returns error if solver fails or doesn't converge.
103    pub fn solve(&self, b: &[f64]) -> Result<Vec<f64>, SolverError> {
104        match self.kind {
105            IterativeSolver::PcG => {
106                let result = cg_solve(&self.matrix, b, self.max_iter, self.tol);
107                match result.status {
108                    CgStatus::Converged => Ok(result.x),
109                    CgStatus::NotPositiveDefinite => Err(SolverError::SolveFailed(
110                        "matrix not positive definite".to_string(),
111                    )),
112                    CgStatus::Breakdown => {
113                        Err(SolverError::SolveFailed("solver breakdown".to_string()))
114                    }
115                    CgStatus::InvalidInput => {
116                        Err(SolverError::InvalidInput("invalid input".to_string()))
117                    }
118                    CgStatus::MaxIterations => Err(SolverError::SolveFailed(
119                        "max iterations reached".to_string(),
120                    )),
121                }
122            }
123            IterativeSolver::Iccg => {
124                let result = iccg_solve(&self.matrix, b, self.max_iter, self.tol);
125                match result.status {
126                    CgStatus::Converged => Ok(result.x),
127                    CgStatus::NotPositiveDefinite => Err(SolverError::SolveFailed(
128                        "matrix not positive definite".to_string(),
129                    )),
130                    CgStatus::Breakdown => {
131                        Err(SolverError::SolveFailed("solver breakdown".to_string()))
132                    }
133                    CgStatus::InvalidInput => {
134                        Err(SolverError::InvalidInput("invalid input".to_string()))
135                    }
136                    CgStatus::MaxIterations => Err(SolverError::SolveFailed(
137                        "max iterations reached".to_string(),
138                    )),
139                }
140            }
141        }
142    }
143}
144
145/// Legacy SparseSolver for backward compatibility.
146pub struct SparseSolver {
147    direct: FactoredDirectSolver,
148}
149
150impl SparseSolver {
151    /// Factor `matrix` with the selected backend.
152    pub fn factor(kind: SolverKind, matrix: &SparseMatrix) -> Result<Self, String> {
153        match kind {
154            SolverKind::SparseLu => Ok(SparseSolver { direct: FactoredDirectSolver::factor(DirectSolver::SparseLu, matrix).map_err(|e| e.to_string())? }),
155            SolverKind::SkylineLdlt => Ok(SparseSolver { direct: FactoredDirectSolver::factor(DirectSolver::SkylineLdlt, matrix).map_err(|e| e.to_string())? }),
156            SolverKind::Pardiso => Err("PARDISO factor requires constraint vector. Use DirectLagrangeSolver instead.".to_string()),
157            SolverKind::PcG | SolverKind::Iccg => Err("iterative solvers (PCG, ICCG) do not support factor(). Use solve_iterative() or IterativeSolverInstance.".to_string()),
158        }
159    }
160
161    /// Direct solve (LU / LDLT). Returns error if solver fails.
162    pub fn solve(&self, b: &[f64]) -> Result<Vec<f64>, SolverError> {
163        self.direct.solve(b)
164    }
165
166    /// Iterative solve used for PCG/ICCG kinds.
167    pub fn solve_iterative(
168        kind: SolverKind,
169        matrix: &SparseMatrix,
170        b: &[f64],
171        max_iter: usize,
172        tol: f64,
173    ) -> Result<Vec<f64>, SolverError> {
174        match kind {
175            SolverKind::PcG => {
176                let result = cg_solve(matrix, b, max_iter, tol);
177                match result.status {
178                    CgStatus::Converged => Ok(result.x),
179                    CgStatus::NotPositiveDefinite => Err(SolverError::SolveFailed(
180                        "matrix not positive definite".to_string(),
181                    )),
182                    CgStatus::Breakdown => {
183                        Err(SolverError::SolveFailed("solver breakdown".to_string()))
184                    }
185                    CgStatus::InvalidInput => {
186                        Err(SolverError::InvalidInput("invalid input".to_string()))
187                    }
188                    CgStatus::MaxIterations => Err(SolverError::SolveFailed(
189                        "max iterations reached".to_string(),
190                    )),
191                }
192            }
193            SolverKind::Iccg => {
194                let result = iccg_solve(matrix, b, max_iter, tol);
195                match result.status {
196                    CgStatus::Converged => Ok(result.x),
197                    CgStatus::NotPositiveDefinite => Err(SolverError::SolveFailed(
198                        "matrix not positive definite".to_string(),
199                    )),
200                    CgStatus::Breakdown => {
201                        Err(SolverError::SolveFailed("solver breakdown".to_string()))
202                    }
203                    CgStatus::InvalidInput => {
204                        Err(SolverError::InvalidInput("invalid input".to_string()))
205                    }
206                    CgStatus::MaxIterations => Err(SolverError::SolveFailed(
207                        "max iterations reached".to_string(),
208                    )),
209                }
210            }
211            _ => Err(SolverError::NotImplemented(
212                "solver kind not supported for iterative solve".to_string(),
213            )),
214        }
215    }
216}
217
218// ---------------------------------------------------------------------------
219// Sparse LU: left-looking, column-oriented with true row partial pivoting
220// (PA = L U). No static pivoting / diagonal perturbation - returns error
221// on near-singular matrices.
222// ---------------------------------------------------------------------------
223//
224// IMPORTANT: This implementation is DENSE-BACKED.
225// The input sparse matrix is converted to a dense n×n matrix for Gaussian
226// elimination with partial pivoting. Time complexity: O(n³), Space: O(n²).
227// Suitable for n up to ~2000-3000 on typical hardware.
228// For larger problems, a true sparse LU (e.g. SuiteSparse, PARDISO) should be used.
229//
230/// Sparse LU factorisation P A = L U with true row partial pivoting.
231pub struct SparseLu {
232    n: usize,
233    /// Row-wise unit-lower triangle (strict part), sorted columns per row.
234    l_rows: Vec<Vec<(usize, f64)>>,
235    /// Row-wise upper triangle including diagonal, sorted columns per row.
236    u_rows: Vec<Vec<(usize, f64)>>,
237    /// Row permutation: perm[final_row] = orig_row. P * A = L * U.
238    perm: Vec<usize>,
239}
240
241impl SparseLu {
242    /// Get the permutation vector (perm\[i\] = original row index at position i).
243    pub fn perm(&self) -> &[usize] {
244        &self.perm
245    }
246
247    /// Get L factor rows (strict lower triangle, unit diagonal implicit).
248    pub fn l_rows(&self) -> &[Vec<(usize, f64)>] {
249        &self.l_rows
250    }
251
252    /// Get U factor rows (upper triangle including diagonal).
253    pub fn u_rows(&self) -> &[Vec<(usize, f64)>] {
254        &self.u_rows
255    }
256
257    /// Get matrix size.
258    pub fn n(&self) -> usize {
259        self.n
260    }
261
262    /// Verify PA = LU for debugging purposes.
263    /// Returns max absolute difference between PA and LU.
264    pub fn verify_pa_eq_lu(&self, a: &SparseMatrix) -> f64 {
265        let n = self.n;
266        // Build A dense
267        let mut a_dense = vec![vec![0.0f64; n]; n];
268        for i in 0..n {
269            for k in a.row_ptr()[i]..a.row_ptr()[i + 1] {
270                let j = a.csr_cols()[k];
271                a_dense[i][j] = a.csr_vals()[k];
272            }
273        }
274
275        // Build PA
276        let mut pa = vec![vec![0.0f64; n]; n];
277        for i in 0..n {
278            let orig_i = self.perm[i];
279            for j in 0..n {
280                pa[i][j] = a_dense[orig_i][j];
281            }
282        }
283
284        // Build LU
285        let mut lu = vec![vec![0.0f64; n]; n];
286        for i in 0..n {
287            for j in 0..n {
288                let mut sum = 0.0;
289                for k in 0..n {
290                    let l_ik = if i == k {
291                        1.0
292                    } else if k < i {
293                        self.l_rows[i]
294                            .iter()
295                            .find(|(c, _)| *c == k)
296                            .map(|(_, v)| *v)
297                            .unwrap_or(0.0)
298                    } else {
299                        0.0
300                    };
301                    let u_kj = if k <= j {
302                        self.u_rows[k]
303                            .iter()
304                            .find(|(c, _)| *c == j)
305                            .map(|(_, v)| *v)
306                            .unwrap_or(0.0)
307                    } else {
308                        0.0
309                    };
310                    sum += l_ik * u_kj;
311                }
312                lu[i][j] = sum;
313            }
314        }
315
316        // Max absolute difference
317        let mut max_diff = 0.0;
318        for i in 0..n {
319            for j in 0..n {
320                let diff = (pa[i][j] - lu[i][j]).abs();
321                if diff > max_diff {
322                    max_diff = diff;
323                }
324            }
325        }
326        max_diff
327    }
328
329    /// Factor A with true row partial pivoting (PA = LU).
330    /// Returns error if matrix is singular or nearly singular.
331    pub fn factor(a: &SparseMatrix) -> Result<SparseLu, String> {
332        let n = a.n;
333        let ac = if a.compressed {
334            None
335        } else {
336            let mut m = a.clone();
337            m.compress();
338            Some(m)
339        };
340        let a_ref = ac.as_ref().unwrap_or(a);
341        let (row_ptr, cols, vals) = a_ref.csr_data();
342
343        // Convert to dense row-major working matrix for pivoting operations
344        // This is memory-intensive but necessary for true partial pivoting
345        // on a sparse matrix. We use a dense column-major working array.
346        let mut a_dense = vec![vec![0.0f64; n]; n];
347        for i in 0..n {
348            for k in row_ptr[i]..row_ptr[i + 1] {
349                let j = cols[k];
350                a_dense[i][j] = vals[k];
351            }
352        }
353
354        // Permutation vector: perm[i] = original row index that ended up at position i
355        let mut perm = (0..n).collect::<Vec<usize>>();
356
357        // LU factors stored in dense format during factorization, then compressed
358        let mut l = vec![vec![0.0f64; n]; n]; // unit diagonal implicit
359        let mut u = vec![vec![0.0f64; n]; n];
360
361        // Compute per-column scales for scale-invariant pivot tolerance
362        // Using column-wise infinity norm scaled by machine epsilon
363        let mut col_scales = vec![0.0f64; n];
364        for j in 0..n {
365            let mut max_abs = 0.0f64;
366            for i in 0..n {
367                max_abs = max_abs.max(a_dense[i][j].abs());
368            }
369            col_scales[j] = max_abs;
370        }
371        // Global matrix scale (for reference)
372        let _matrix_scale = col_scales.iter().fold(0.0f64, |a, &v| a.max(v));
373
374        // Scale-invariant pivot tolerance:
375        // pivot_tol = EPS * n * max(|A[:,k]|_inf) * safety_factor
376        // This ensures that small-scale matrices aren't incorrectly flagged as singular
377        // and large-scale matrices don't reject legitimate small pivots
378        const PIVOT_SAFETY_FACTOR: f64 = 100.0;
379
380        // LU factorization with partial pivoting (Gaussian elimination with row swaps)
381        for k in 0..n {
382            // Find pivot row: max |A[i][k]| for i >= k
383            let mut pivot_row = k;
384            let mut max_val = a_dense[k][k].abs();
385            for i in (k + 1)..n {
386                let v = a_dense[i][k].abs();
387                if v > max_val {
388                    max_val = v;
389                    pivot_row = i;
390                }
391            }
392
393            // Check for singularity using scale-aware tolerance (per-column)
394            // True scale invariance: use actual column scale without artificial floor.
395            // If col_scale == 0 or non-finite, the column is all zeros or invalid -> singular.
396            let col_scale = col_scales[k];
397            if !col_scale.is_finite() || col_scale == 0.0 {
398                return Err(format!(
399                    "Singular matrix at column {}: column is all zeros or contains NaN/Inf (col_scale = {:.2e})",
400                    k, col_scale
401                ));
402            }
403            let pivot_tol = f64::EPSILON * n as f64 * col_scale * PIVOT_SAFETY_FACTOR;
404
405            if max_val <= pivot_tol {
406                return Err(format!(
407                    "Singular or near-singular matrix at column {}: max pivot = {:.2e}, tolerance = {:.2e} (col_scale = {:.2e})",
408                    k, max_val, pivot_tol, col_scale
409                ));
410            }
411
412            // Swap rows k and pivot_row in A and L, and permutation
413            if pivot_row != k {
414                a_dense.swap(k, pivot_row);
415                // Swap corresponding rows in L (only columns < k are filled)
416                // Use split_at_mut to get two mutable references
417                let (l_first, l_second) = if k < pivot_row {
418                    l.split_at_mut(pivot_row)
419                } else {
420                    l.split_at_mut(k)
421                };
422                let (row_k, row_pivot) = if k < pivot_row {
423                    (&mut l_first[k], &mut l_second[0])
424                } else {
425                    (&mut l_second[0], &mut l_first[k])
426                };
427                for j in 0..k {
428                    std::mem::swap(&mut row_k[j], &mut row_pivot[j]);
429                }
430                perm.swap(k, pivot_row);
431            }
432
433            // U[k][k] = A[k][k] (after potential swap)
434            u[k][k] = a_dense[k][k];
435
436            // Compute U[k][j] for j > k
437            for j in (k + 1)..n {
438                u[k][j] = a_dense[k][j];
439            }
440
441            // Compute L[i][k] for i > k
442            let pivot = u[k][k];
443            for i in (k + 1)..n {
444                l[i][k] = a_dense[i][k] / pivot;
445            }
446
447            // Update trailing submatrix: A[i][j] -= L[i][k] * U[k][j] for i,j > k
448            for i in (k + 1)..n {
449                let lik = l[i][k];
450                if lik != 0.0 {
451                    for j in (k + 1)..n {
452                        a_dense[i][j] -= lik * u[k][j];
453                    }
454                    a_dense[i][k] = 0.0; // Below diagonal becomes zero
455                }
456            }
457        }
458
459        // Build sparse L and U factors (only non-zero entries)
460        // Use relative drop tolerance: keep entries where |v| > max_row_abs * EPS * n
461        // This avoids deleting legitimate small entries in scaled matrices
462        let mut l_rows: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
463        let mut u_rows: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
464
465        // Compute per-row scale for relative drop tolerance
466        let mut l_row_scale = vec![0.0f64; n];
467        let mut u_row_scale = vec![0.0f64; n];
468        for i in 0..n {
469            for j in 0..i {
470                l_row_scale[i] = l_row_scale[i].max(l[i][j].abs());
471            }
472            for j in i..n {
473                u_row_scale[i] = u_row_scale[i].max(u[i][j].abs());
474            }
475        }
476
477        for i in 0..n {
478            // L has unit diagonal (not stored), strictly lower part
479            let l_tol = l_row_scale[i] * f64::EPSILON * n as f64;
480            for j in 0..i {
481                if l[i][j].abs() > l_tol {
482                    l_rows[i].push((j, l[i][j]));
483                }
484            }
485            // U has diagonal and upper part
486            let u_tol = u_row_scale[i] * f64::EPSILON * n as f64;
487            for j in i..n {
488                if u[i][j].abs() > u_tol {
489                    u_rows[i].push((j, u[i][j]));
490                }
491            }
492            l_rows[i].sort_unstable_by_key(|e| e.0);
493            u_rows[i].sort_unstable_by_key(|e| e.0);
494        }
495
496        Ok(SparseLu {
497            n,
498            l_rows,
499            u_rows,
500            perm,
501        })
502    }
503
504    /// Solve A x = b via forward/back substitution using P A = L U.
505    /// Returns x = A^{-1} b or error if diagonal is near-zero.
506    pub fn solve(&self, b: &[f64]) -> Result<Vec<f64>, String> {
507        let n = self.n;
508        if b.len() != n {
509            return Err(format!(
510                "Solve failed: RHS length {} does not match matrix size {}",
511                b.len(),
512                n
513            ));
514        }
515        // Check for NaN/Inf in RHS
516        for (i, &val) in b.iter().enumerate() {
517            if !val.is_finite() {
518                return Err(format!(
519                    "Solve failed: RHS contains non-finite value at index {}: {}",
520                    i, val
521                ));
522            }
523        }
524        // Apply permutation: Pb
525        let mut y = vec![0.0f64; n];
526        for i in 0..n {
527            y[i] = b[self.perm[i]];
528        }
529
530        // Forward substitution: L y = Pb (L has unit diagonal)
531        for i in 0..n {
532            let mut sum = 0.0;
533            for &(c, v) in &self.l_rows[i] {
534                sum += v * y[c];
535            }
536            y[i] -= sum;
537        }
538
539        // Backward substitution: U x = y
540        let mut x = vec![0.0f64; n];
541        for i in (0..n).rev() {
542            let mut sum = 0.0;
543            // Find diagonal and sum U[i][j] * x[j] for j > i
544            let mut diag = 1.0;
545            for &(c, v) in &self.u_rows[i] {
546                if c == i {
547                    diag = v;
548                } else if c > i {
549                    sum += v * x[c];
550                }
551            }
552            if !diag.is_finite() || diag == 0.0 {
553                return Err(format!(
554                    "Solve failed: near-zero or invalid diagonal at row {}: diag = {:.2e}",
555                    i, diag
556                ));
557            }
558            x[i] = (y[i] - sum) / diag;
559        }
560        Ok(x)
561    }
562}
563
564// ---------------------------------------------------------------------------
565// IC(0)-preconditioned conjugate gradient.
566// ---------------------------------------------------------------------------
567
568/// IC(0) incomplete Cholesky factorisation (same sparsity pattern as the
569/// lower triangle of A), stored row-wise: A ~ L L^T.
570pub struct Ic0Factor {
571    n: usize,
572    /// Row offsets into flattened storage for fast application.
573    ptr: Vec<usize>,
574    flat_cols: Vec<usize>,
575    flat_vals: Vec<f64>,
576}
577
578impl Ic0Factor {
579    pub fn factor(a: &SparseMatrix) -> Result<Ic0Factor, String> {
580        let n = a.n;
581        let ac = if a.compressed {
582            None
583        } else {
584            let mut m = a.clone();
585            m.compress();
586            Some(m)
587        };
588        let a_ref = ac.as_ref().unwrap_or(a);
589        let (row_ptr, cols, vals) = a_ref.csr_data();
590
591        // Lower triangle row-wise with diagonal.
592        let mut l_rows: Vec<Vec<(usize, f64)>> = vec![Vec::new(); n];
593        for i in 0..n {
594            for k in row_ptr[i]..row_ptr[i + 1] {
595                if cols[k] <= i {
596                    l_rows[i].push((cols[k], vals[k]));
597                }
598            }
599            l_rows[i].sort_unstable_by_key(|e| e.0);
600        }
601
602        // IC(0): row-wise algorithm. For each row i, walk the strictly-lower
603        // entries left-to-right: divide by the pivot of their column, then
604        // apply the rank-1 correction to remaining entries (pattern
605        // intersection only). Finally scale the diagonal.
606        for i in 0..n {
607            let len_i = l_rows[i].len();
608            for m in 0..len_i {
609                let (k, _) = l_rows[i][m];
610                if k >= i {
611                    break;
612                }
613                let dk = l_rows[k].last().map(|&(_, v)| v).unwrap_or(1.0);
614                if dk.abs() < 1e-300 {
615                    return Err(format!("IC(0): zero pivot at row {k}"));
616                }
617                l_rows[i][m].1 /= dk;
618                let l_ik = l_rows[i][m].1;
619                if l_ik == 0.0 {
620                    continue;
621                }
622                let krow: Vec<(usize, f64)> = l_rows[k].clone();
623                for &(cj, lj) in krow.iter() {
624                    if cj <= k || cj > i {
625                        continue;
626                    }
627                    // Includes the diagonal (cj == i): a_ii -= L_ik * L_ki.
628                    if let Some(pos) = l_rows[i].iter().position(|&(cc, _)| cc == cj) {
629                        l_rows[i][pos].1 -= l_ik * lj;
630                    }
631                }
632            }
633
634            // Diagonal: take corrected a_ii and scale to sqrt.
635            let diag_val = l_rows[i].last().map(|&(_, v)| v).unwrap_or(0.0);
636            let d = diag_val;
637            if !(d > 0.0) || !d.is_finite() {
638                return Err(format!("IC(0) breakdown at row {i}: non-positive diagonal"));
639            }
640            let last = l_rows[i].len() - 1;
641            debug_assert_eq!(l_rows[i][last].0, i);
642            l_rows[i][last].1 = d.sqrt();
643        }
644
645        // Flatten for fast forward/back substitution.
646        let mut ptr = vec![0usize; n + 1];
647        let mut flat_cols = Vec::new();
648        let mut flat_vals = Vec::new();
649        for i in 0..n {
650            ptr[i + 1] = ptr[i] + l_rows[i].len();
651            for &(c, v) in &l_rows[i] {
652                flat_cols.push(c);
653                flat_vals.push(v);
654            }
655        }
656
657        Ok(Ic0Factor {
658            n,
659            ptr,
660            flat_cols,
661            flat_vals,
662        })
663    }
664
665    /// Solve (L L^T) x = b.
666    pub fn solve(&self, b: &[f64]) -> Vec<f64> {
667        let n = self.n;
668        let mut y = b.to_vec();
669        // Forward: L y' = b
670        for i in 0..n {
671            let mut s = y[i];
672            for k in self.ptr[i]..self.ptr[i + 1] {
673                let c = self.flat_cols[k];
674                if c < i {
675                    s -= self.flat_vals[k] * y[c];
676                }
677            }
678            let d = self.flat_vals[self.ptr[i + 1] - 1];
679            y[i] = s / d;
680        }
681        // Backward: L^T x = y' via scattered updates.
682        let mut x = y;
683        for i in (0..n).rev() {
684            let d = self.flat_vals[self.ptr[i + 1] - 1];
685            let xi = x[i] / d;
686            x[i] = xi;
687            for k in self.ptr[i]..self.ptr[i + 1] - 1 {
688                let c = self.flat_cols[k];
689                x[c] -= self.flat_vals[k] * xi;
690            }
691        }
692        x
693    }
694}
695
696/// IC(0)-preconditioned conjugate gradient.
697pub fn iccg_solve(a: &SparseMatrix, b: &[f64], max_iter: usize, tol: f64) -> CgResult {
698    let ic = match Ic0Factor::factor(a) {
699        Ok(f) => f,
700        Err(_) => return super::cg_solve(a, b, max_iter, tol),
701    };
702
703    let n = b.len();
704    let ac = if a.compressed {
705        None
706    } else {
707        let mut m = a.clone();
708        m.compress();
709        Some(m)
710    };
711    let a_ref = ac.as_ref().unwrap_or(a);
712    let (rptr, ccols, cvals) = a_ref.csr_data();
713    let matvec = |p: &[f64], out: &mut [f64]| {
714        for row in 0..n {
715            let mut sum = 0.0;
716            for k in rptr[row]..rptr[row + 1] {
717                sum += cvals[k] * p[ccols[k]];
718            }
719            out[row] = sum;
720        }
721    };
722
723    let b_norm = b.iter().map(|v| v * v).sum::<f64>().sqrt();
724    let mut x = vec![0.0f64; n];
725    if b_norm == 0.0 {
726        return CgResult {
727            x,
728            iterations: 0,
729            residual: 0.0,
730            status: CgStatus::InvalidInput,
731        };
732    }
733
734    let mut r = b.to_vec();
735    let mut z = ic.solve(&r);
736    let mut p = z.clone();
737    let mut rz: f64 = r.iter().zip(z.iter()).map(|(&a, &b2)| a * b2).sum();
738    let mut iterations = 0;
739
740    let mut ap = vec![0.0f64; n];
741    for iter in 0..max_iter {
742        matvec(&p, &mut ap);
743        let pap: f64 = p.iter().zip(ap.iter()).map(|(&a, &b2)| a * b2).sum();
744        if pap.abs() <= 0.0 {
745            return CgResult {
746                x,
747                iterations,
748                residual: r.iter().map(|v| v * v).sum::<f64>().sqrt(),
749                status: CgStatus::Breakdown,
750            };
751        }
752        let alpha = rz / pap;
753        if !alpha.is_finite() {
754            return CgResult {
755                x,
756                iterations,
757                residual: r.iter().map(|v| v * v).sum::<f64>().sqrt(),
758                status: CgStatus::Breakdown,
759            };
760        }
761        for i in 0..n {
762            x[i] += alpha * p[i];
763            r[i] -= alpha * ap[i];
764        }
765
766        let rn = r.iter().map(|v| v * v).sum::<f64>().sqrt();
767        iterations = iter + 1;
768        if rn < tol * b_norm {
769            return CgResult {
770                x,
771                iterations,
772                residual: rn,
773                status: CgStatus::Converged,
774            };
775        }
776
777        z = ic.solve(&r);
778        let rz_new: f64 = r.iter().zip(z.iter()).map(|(&a, &b2)| a * b2).sum();
779        if rz == 0.0 || !rz.is_finite() {
780            return CgResult {
781                x,
782                iterations,
783                residual: r.iter().map(|v| v * v).sum::<f64>().sqrt(),
784                status: CgStatus::Breakdown,
785            };
786        }
787        let beta = rz_new / rz;
788        if !beta.is_finite() {
789            return CgResult {
790                x,
791                iterations,
792                residual: r.iter().map(|v| v * v).sum::<f64>().sqrt(),
793                status: CgStatus::Breakdown,
794            };
795        }
796        for i in 0..n {
797            p[i] = z[i] + beta * p[i];
798        }
799        rz = rz_new;
800    }
801
802    CgResult {
803        x,
804        iterations,
805        residual: r.iter().map(|v| v * v).sum::<f64>().sqrt(),
806        status: CgStatus::MaxIterations,
807    }
808}
809
810// ---------------------------------------------------------------------------
811// PARDISO (Intel MKL) optional FFI binding.
812// ---------------------------------------------------------------------------
813#[cfg(feature = "pardiso")]
814pub mod pardiso {
815    //! Direct solve via Intel MKL PARDISO (`mkl_rt`). Enable with
816    //! `--features pardiso`; requires `mkl_rt.3.dll` (or equivalent) on PATH.
817    use super::super::{CscMatrix, NEAR_ZERO_TOL_BASE, SkylineLdlt, SparseMatrix};
818    use std::os::raw::c_void;
819
820    #[cfg_attr(target_os = "windows", link(name = "mkl_rt.2", kind = "raw-dylib"))]
821    #[cfg_attr(not(target_os = "windows"), link(name = "mkl_rt.2"))]
822    unsafe extern "C" {
823        fn pardisoinit(
824            pt: *mut c_void,
825            maxfct: *const i32,
826            mnum: *const i32,
827            iparm: *mut i32,
828            msglvl: *const i32,
829            error: *mut i32,
830        );
831        fn pardiso(
832            pt: *mut c_void,
833            maxfct: *const i32,
834            mnum: *const i32,
835            mtype: *const i32,
836            phase: *const i32,
837            n: *const i32,
838            a: *const f64,
839            ia: *const i32,
840            ja: *const i32,
841            perm: *const i32,
842            nrhs: *const i32,
843            iparm: *mut i32,
844            msglvl: *const i32,
845            b: *const f64,
846            x: *mut f64,
847            error: *mut i32,
848        );
849    }
850
851    const MAXFCT: i32 = 1;
852    const MNUM: i32 = 1;
853    /// Symmetric indefinite matrix.
854    const MTYPE: i32 = -2;
855
856    /// PARDISO-backed direct solver for the augmented Lagrangian system.
857    pub struct PardisoSolver {
858        /// Leading block size (K is leading_n x leading_n)
859        leading_n: usize,
860        /// Augmented matrix size (leading_n + 1)
861        n: usize,
862        pt: Vec<u64>,
863        iparm: Vec<i32>,
864        csc: CscMatrix,
865        ia: Vec<i32>,
866        ja: Vec<i32>,
867        vals: Vec<f64>,
868        factorised: bool,
869        /// Constraint vector c for Lagrange multiplier computation.
870        c: Vec<f64>,
871        /// Scale factor for scale-invariant tolerances (max diagonal entry of leading block).
872        scale: f64,
873    }
874
875    unsafe impl Send for PardisoSolver {}
876
877    impl PardisoSolver {
878        pub fn new(k: &SparseMatrix, c: &[f64]) -> Result<Self, String> {
879            let csc = super::super::DirectLagrangeSolver::assemble_torsion_lagrange(k, c);
880            let leading_n = csc.n_rows - 1; // leading block size
881            let n = leading_n + 1; // augmented matrix size
882
883            // Compute scale from leading block K (max diagonal)
884            let mut scale = 0.0f64;
885            let mut k_compressed = k.clone();
886            k_compressed.compress();
887            for i in 0..leading_n {
888                scale = scale.max(k_compressed.matvec_diag(i).abs());
889            }
890            let scale = scale.max(1.0);
891
892            let mut s = Self {
893                leading_n,
894                n,
895                pt: vec![0u64; 64],
896                iparm: vec![0i32; 64],
897                csc,
898                ia: Vec::new(),
899                ja: Vec::new(),
900                vals: Vec::new(),
901                factorised: false,
902                c: c.to_vec(),
903                scale,
904            };
905            unsafe {
906                let mut err: i32 = 0;
907                let msglvl: i32 = 0;
908                pardisoinit(
909                    s.pt.as_mut_ptr() as *mut c_void,
910                    &MAXFCT,
911                    &MNUM,
912                    s.iparm.as_mut_ptr(),
913                    &msglvl,
914                    &mut err,
915                );
916                if err != 0 {
917                    return Err(format!("pardisoinit failed: {err}"));
918                }
919                // Zero-based indexing for ia/ja arrays.
920                s.iparm[34] = 1;
921            }
922            Ok(s)
923        }
924
925        fn ensure_factorised(&mut self) -> Result<(), String> {
926            if self.factorised {
927                return Ok(());
928            }
929            self.ia = self.csc.col_ptr.iter().map(|&v| v as i32).collect();
930            self.ja = self.csc.rows.iter().map(|&v| v as i32).collect();
931            self.vals = self.csc.vals.clone();
932
933            unsafe {
934                let mut err: i32 = 0;
935                let phase: i32 = 13; // analyse + numerical factorisation
936                let n = self.n as i32;
937                let nrhs: i32 = 0;
938                let msglvl: i32 = 0;
939                let dummy_b: f64 = 0.0;
940                let mut dummy_x: f64 = 0.0;
941                pardiso(
942                    self.pt.as_mut_ptr() as *mut c_void,
943                    &MAXFCT,
944                    &MNUM,
945                    &MTYPE,
946                    &phase,
947                    &n,
948                    self.vals.as_ptr(),
949                    self.ia.as_ptr(),
950                    self.ja.as_ptr(),
951                    std::ptr::null(),
952                    &nrhs,
953                    self.iparm.as_mut_ptr(),
954                    &msglvl,
955                    &dummy_b,
956                    &mut dummy_x,
957                    &mut err,
958                );
959                if err != 0 {
960                    return Err(format!("pardiso factorisation failed: {err}"));
961                }
962            }
963            self.factorised = true;
964            Ok(())
965        }
966
967        /// Solve [K c; c^T 0] [u; lam] = [f; 0]; returns (u, lam).
968        pub fn solve_with_multiplier(&mut self, f: &[f64]) -> Result<(Vec<f64>, f64), String> {
969            self.ensure_factorised()?;
970            let n = self.n; // augmented matrix size
971            let mut b = f.to_vec();
972            b.push(0.0); // size becomes n
973            let mut x = vec![0.0f64; n];
974
975            unsafe {
976                let mut err: i32 = 0;
977                let phase: i32 = 33; // solve + iterative refinement
978                let nn = n as i32; // pass augmented size directly
979                let nrhs: i32 = 1;
980                let msglvl: i32 = 0;
981                pardiso(
982                    self.pt.as_mut_ptr() as *mut c_void,
983                    &MAXFCT,
984                    &MNUM,
985                    &MTYPE,
986                    &phase,
987                    &nn,
988                    self.vals.as_ptr(),
989                    self.ia.as_ptr(),
990                    self.ja.as_ptr(),
991                    std::ptr::null(),
992                    &nrhs,
993                    self.iparm.as_mut_ptr(),
994                    &msglvl,
995                    b.as_ptr(),
996                    x.as_mut_ptr(),
997                    &mut err,
998                );
999                if err != 0 {
1000                    return Err(format!("pardiso solve failed: {err}"));
1001                }
1002            }
1003
1004            let lam = x.pop().unwrap_or(0.0);
1005            Ok((x, lam))
1006        }
1007
1008        /// Solve [K c; c^T 0] [u; lam] = [f; 0]; returns u.
1009        pub fn solve_direct_lagrange(&mut self, f: &[f64]) -> Result<Vec<f64>, String> {
1010            self.ensure_factorised()?;
1011            let n = self.n; // augmented matrix size
1012            let mut b = f.to_vec();
1013            b.push(0.0); // size becomes n
1014            let mut x = vec![0.0f64; n];
1015
1016            unsafe {
1017                let mut err: i32 = 0;
1018                let phase: i32 = 33; // solve + iterative refinement
1019                let nn = n as i32;
1020                let nrhs: i32 = 1;
1021                let msglvl: i32 = 0;
1022                pardiso(
1023                    self.pt.as_mut_ptr() as *mut c_void,
1024                    &MAXFCT,
1025                    &MNUM,
1026                    &MTYPE,
1027                    &phase,
1028                    &nn,
1029                    self.vals.as_ptr(),
1030                    self.ia.as_ptr(),
1031                    self.ja.as_ptr(),
1032                    std::ptr::null(),
1033                    &nrhs,
1034                    self.iparm.as_mut_ptr(),
1035                    &msglvl,
1036                    b.as_ptr(),
1037                    x.as_mut_ptr(),
1038                    &mut err,
1039                );
1040                if err != 0 {
1041                    return Err(format!("pardiso solve failed: {err}"));
1042                }
1043            }
1044
1045            x.pop();
1046            Ok(x)
1047        }
1048
1049        /// Multiplier error metric |lam| / max|u| (Python's u[-1]/max|u|).
1050        pub fn multiplier_error(&self, c: &[f64], f: &[f64], u: &[f64]) -> f64 {
1051            // lam can be recovered from the augmented solve; approximate via
1052            // residual of the constraint row is out of scope here, so mirror
1053            // the skyline implementation by refactoring K once more.
1054            let ldlt = match SkylineLdlt::factor(&{
1055                let m = {
1056                    // leading block from CSC columns 0..leading_n
1057                    let leading_n = self.leading_n;
1058                    let mut sm = SparseMatrix::new(leading_n);
1059                    for col in 0..leading_n {
1060                        for k in self.csc.col_ptr[col]..self.csc.col_ptr[col + 1] {
1061                            let r = self.csc.rows[k];
1062                            if r < leading_n && col < leading_n {
1063                                sm.add(r, col, self.csc.vals[k]);
1064                            }
1065                        }
1066                    }
1067                    sm.compress();
1068                    sm
1069                };
1070                m
1071            }) {
1072                Ok(l) => l,
1073                Err(_) => return f64::INFINITY,
1074            };
1075            let w1 = ldlt.solve(f).unwrap_or_else(|_| vec![0.0; c.len()]);
1076            let w2 = ldlt.solve(c).unwrap_or_else(|_| vec![0.0; c.len()]);
1077            let mut ct_w2 = 0.0f64;
1078            for (ci, wi) in c.iter().zip(w2.iter()) {
1079                ct_w2 += ci * wi;
1080            }
1081            let mut ct_w1 = 0.0f64;
1082            for (ci, wi) in c.iter().zip(w1.iter()) {
1083                ct_w1 += ci * wi;
1084            }
1085            // Scale-invariant tolerance for Lagrange multiplier
1086            let near_zero_tol = NEAR_ZERO_TOL_BASE * self.scale.max(1.0);
1087            // u = w1 - lambda*w2 with constraint c^T u = 0 gives
1088            // lambda = (c^T w1) / (c^T w2) = ct_w1 / ct_w2.
1089            let lambda = if ct_w2.abs() > near_zero_tol {
1090                ct_w1 / ct_w2
1091            } else {
1092                0.0
1093            };
1094            let max_u = u.iter().fold(0.0f64, |a, &v| a.max(v.abs()));
1095            if max_u > 0.0 {
1096                lambda.abs() / max_u
1097            } else {
1098                f64::INFINITY
1099            }
1100        }
1101    }
1102
1103    impl Drop for PardisoSolver {
1104        fn drop(&mut self) {
1105            if !self.factorised {
1106                return;
1107            }
1108            unsafe {
1109                let mut err: i32 = 0;
1110                let phase: i32 = -1; // release memory
1111                let n = self.n as i32;
1112                let nrhs: i32 = 0;
1113                let msglvl: i32 = 0;
1114                let dummy: f64 = 0.0;
1115                let mut x_dummy: f64 = 0.0;
1116                pardiso(
1117                    self.pt.as_mut_ptr() as *mut c_void,
1118                    &MAXFCT,
1119                    &MNUM,
1120                    &MTYPE,
1121                    &phase,
1122                    &n,
1123                    self.vals.as_ptr(),
1124                    self.ia.as_ptr(),
1125                    self.ja.as_ptr(),
1126                    std::ptr::null(),
1127                    &nrhs,
1128                    self.iparm.as_mut_ptr(),
1129                    &msglvl,
1130                    &dummy,
1131                    &mut x_dummy,
1132                    &mut err,
1133                );
1134            }
1135        }
1136    }
1137}
1138#[cfg(all(feature = "pardiso", test))]
1139mod pardiso_tests {
1140    use super::pardiso::PardisoSolver;
1141    use crate::fea::SparseMatrix;
1142
1143    #[test]
1144    fn pardiso_laplacian_smoke() {
1145        // Requires mkl_rt.3.dll on PATH at runtime.
1146        let n = 20;
1147        let mut k = SparseMatrix::new(n);
1148        for i in 0..n {
1149            k.add(i, i, 2.0);
1150            if i + 1 < n {
1151                k.add(i, i + 1, -1.0);
1152                k.add(i + 1, i, -1.0);
1153            }
1154        }
1155        let c: Vec<f64> = vec![1.0; n];
1156        let f: Vec<f64> = (0..n).map(|i| (i as f64) * 0.05).collect();
1157
1158        let mut s = PardisoSolver::new(&k, &c).expect("pardiso init");
1159        let u = s.solve_direct_lagrange(&f).expect("pardiso solve");
1160        assert_eq!(u.len(), n);
1161        // residual check
1162        let mut kmat = SparseMatrix::new(n);
1163        for i in 0..n {
1164            kmat.add(i, i, 2.0);
1165            if i + 1 < n {
1166                kmat.add(i, i + 1, -1.0);
1167                kmat.add(i + 1, i, -1.0);
1168            }
1169        }
1170        kmat.compress();
1171        let prod = kmat.matvec(&u);
1172        for i in 0..n {
1173            assert!(
1174                (prod[i] - f[i] + c[i]).abs() < 1e-6 || (prod[i] - f[i]).abs() < 1e-6,
1175                "row {} residual too large",
1176                i
1177            );
1178        }
1179    }
1180}