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