Skip to main content

section_properties/fea/
solver.rs

1//! Unified linear solver abstraction for the FEM framework.
2//!
3//! Provides a common interface for different linear solvers (direct, iterative, external)
4//! enabling a plugin-based architecture for the FEM framework.
5
6use crate::fea::SparseMatrix;
7use crate::fea::solver::impls::cg::CgSolver;
8use crate::fea::solver::impls::dense_gaussian::DenseGaussianSolver;
9use crate::fea::solver::impls::iccg::IccgSolver;
10use crate::fea::solver::impls::skyline_ldlt::SkylineLdltSolver;
11use crate::fea::solver::impls::sparse_lu::SparseLuSolver;
12
13pub mod impls;
14
15/// Capabilities of a linear solver
16#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
17pub struct SolverCapabilities {
18    /// Supports symmetric matrices
19    pub symmetric: bool,
20    /// Supports symmetric positive definite matrices
21    pub spd: bool,
22    /// Supports indefinite symmetric matrices
23    pub symmetric_indefinite: bool,
24    /// Supports general non-symmetric matrices
25    pub general: bool,
26    /// Supports multiple right-hand sides efficiently
27    pub multiple_rhs: bool,
28    /// Supports complex numbers
29    pub complex: bool,
30    /// Maximum problem size (None = unlimited)
31    pub max_size: Option<usize>,
32}
33
34impl SolverCapabilities {
35    /// Capabilities for dense Gaussian elimination
36    pub fn dense() -> Self {
37        Self {
38            symmetric: true,
39            spd: true,
40            symmetric_indefinite: true,
41            general: true,
42            multiple_rhs: true,
43            complex: false,
44            max_size: Some(500),
45        }
46    }
47
48    /// Capabilities for Skyline LDL^T
49    pub fn skyline_ldlt() -> Self {
50        Self {
51            symmetric: true,
52            spd: true,
53            symmetric_indefinite: false,
54            general: false,
55            multiple_rhs: true,
56            complex: false,
57            max_size: Some(10000),
58        }
59    }
60
61    /// Capabilities for SparseLU
62    pub fn sparse_lu() -> Self {
63        Self {
64            symmetric: true,
65            spd: true,
66            symmetric_indefinite: true,
67            general: true,
68            multiple_rhs: true,
69            complex: false,
70            max_size: Some(3000),
71        }
72    }
73
74    /// Capabilities for CG
75    pub fn cg() -> Self {
76        Self {
77            symmetric: true,
78            spd: true,
79            symmetric_indefinite: false,
80            general: false,
81            multiple_rhs: false,
82            complex: false,
83            max_size: None,
84        }
85    }
86
87    /// Capabilities for ICCG
88    pub fn iccg() -> Self {
89        Self {
90            symmetric: true,
91            spd: true,
92            symmetric_indefinite: false,
93            general: false,
94            multiple_rhs: false,
95            complex: false,
96            max_size: None,
97        }
98    }
99}
100
101/// Unified error type for all linear solvers
102#[derive(Debug, Clone, thiserror::Error)]
103pub enum SolverError {
104    #[error("invalid input: {0}")]
105    InvalidInput(String),
106
107    #[error("non-finite input at index {index}")]
108    NonFiniteInput { index: usize },
109
110    #[error("dimension mismatch: expected {expected}, got {actual}")]
111    DimensionMismatch { expected: usize, actual: usize },
112
113    #[error("singular matrix: {0}")]
114    SingularMatrix(String),
115
116    #[error("near-singular matrix: {0}")]
117    NearSingularMatrix(String),
118
119    #[error("factorization failed: {0}")]
120    FactorizationFailed(String),
121
122    #[error("solve failed: {0}")]
123    SolveFailed(String),
124
125    #[error("backend unavailable: {0}")]
126    BackendUnavailable(String),
127
128    #[error("backend error: {0}")]
129    BackendError(String),
130
131    #[error("unsupported operation: {0}")]
132    Unsupported(String),
133
134    #[error("convergence failed: {0}")]
135    ConvergenceFailed(String),
136
137    #[error("not implemented: {0}")]
138    NotImplemented(String),
139
140    #[error("matrix is not symmetric")]
141    NotSymmetric,
142
143    #[error("solver not factorized")]
144    NotFactorized,
145
146    #[error("solver did not converge")]
147    NotConverged,
148}
149
150impl SolverError {
151    pub fn invalid_input(msg: impl Into<String>) -> Self {
152        Self::InvalidInput(msg.into())
153    }
154
155    pub fn non_finite(index: usize) -> Self {
156        Self::NonFiniteInput { index }
157    }
158
159    pub fn dimension_mismatch(expected: usize, actual: usize) -> Self {
160        Self::DimensionMismatch { expected, actual }
161    }
162
163    pub fn singular(msg: impl Into<String>) -> Self {
164        Self::SingularMatrix(msg.into())
165    }
166
167    pub fn near_singular(msg: impl Into<String>) -> Self {
168        Self::NearSingularMatrix(msg.into())
169    }
170
171    pub fn factorization_failed(msg: impl Into<String>) -> Self {
172        Self::FactorizationFailed(msg.into())
173    }
174
175    pub fn solve_failed(msg: impl Into<String>) -> Self {
176        Self::SolveFailed(msg.into())
177    }
178
179    pub fn backend_unavailable(msg: impl Into<String>) -> Self {
180        Self::BackendUnavailable(msg.into())
181    }
182
183    pub fn backend_error(msg: impl Into<String>) -> Self {
184        Self::BackendError(msg.into())
185    }
186
187    pub fn unsupported(msg: impl Into<String>) -> Self {
188        Self::Unsupported(msg.into())
189    }
190
191    pub fn convergence_failed(msg: impl Into<String>) -> Self {
192        Self::ConvergenceFailed(msg.into())
193    }
194
195    pub fn not_implemented(msg: impl Into<String>) -> Self {
196        Self::NotImplemented(msg.into())
197    }
198
199    pub fn not_symmetric() -> Self {
200        Self::NotSymmetric
201    }
202
203    pub fn not_factorized() -> Self {
204        Self::NotFactorized
205    }
206
207    pub fn not_converged() -> Self {
208        Self::NotConverged
209    }
210}
211
212/// Trait for linear solvers that can factorize and solve
213pub trait LinearSolver: Send + Sync {
214    /// Get solver name
215    fn name(&self) -> &'static str;
216
217    /// Get solver capabilities
218    fn capabilities(&self) -> SolverCapabilities;
219
220    /// Factorize the matrix
221    fn factor(&mut self, matrix: &SparseMatrix) -> Result<(), SolverError>;
222
223    /// Solve for a single RHS (requires prior factorization)
224    fn solve(&self, rhs: &[f64]) -> Result<Vec<f64>, SolverError>;
225
226    /// Solve for multiple RHS (requires prior factorization)
227    fn solve_many(&self, rhs: &[Vec<f64>]) -> Result<Vec<Vec<f64>>, SolverError> {
228        rhs.iter().map(|rhs| self.solve(rhs)).collect()
229    }
230}
231
232/// How a linear solver is chosen for a system.
233///
234/// # Canonical solver names
235///
236/// `Named` carries one of the registered backend names below. Unknown names are
237/// rejected with a structured [`SolverError`] — they never fall back.
238///
239/// | name             | symmetry        | definiteness        | intended size | registered by default |
240/// |------------------|-----------------|---------------------|---------------|-----------------------|
241/// | `dense`          | any (general)   | any                 | small         | yes                   |
242/// | `skyline_ldlt`   | symmetric only  | SPD (verified)      | medium/large  | yes                   |
243/// | `sparse_lu`      | any (general)   | any                 | medium/large  | yes                   |
244/// | `cg`             | symmetric only  | SPD (assumed)       | large         | yes                   |
245/// | `iccg`           | symmetric only  | SPD (assumed)       | large         | yes                   |
246///
247/// # Semantics
248///
249/// - [`Auto`](Self::Auto): the registry analyses the matrix and picks a backend.
250///   It may substitute a different backend than any the caller had in mind.
251/// - [`Named`](Self::Named): the request is **authoritative**. The registry
252///   validates capabilities and returns an error if the backend cannot legally
253///   handle the matrix. It never substitutes another backend.
254///
255/// `skyline_ldlt`, `cg` and `iccg` require positive definiteness but perform
256/// their own definiteness check during [`LinearSolver::factor`] (skyline rejects
257/// a non-positive pivot; CG/ICCG report failure). They are therefore safe to
258/// select on a symmetric matrix, but are **never** chosen by `Auto` for a matrix
259/// whose SPD property is not established.
260#[derive(Debug, Clone, PartialEq, Eq, Default)]
261pub enum SolverSelection {
262    /// Registry-based automatic selection (default).
263    #[default]
264    Auto,
265    /// Explicit backend request (canonical name, see type docs).
266    Named(String),
267}
268
269impl SolverSelection {
270    /// Explicit selection by canonical name.
271    pub fn named(name: impl Into<String>) -> Self {
272        Self::Named(name.into())
273    }
274    /// Select the dense Gaussian backend.
275    pub fn dense() -> Self {
276        Self::Named("dense".to_string())
277    }
278    /// Select the skyline LDL^T backend (symmetric SPD).
279    pub fn skyline_ldlt() -> Self {
280        Self::Named("skyline_ldlt".to_string())
281    }
282    /// Select the sparse LU backend.
283    pub fn sparse_lu() -> Self {
284        Self::Named("sparse_lu".to_string())
285    }
286    /// Select the conjugate-gradient backend (symmetric SPD).
287    pub fn cg() -> Self {
288        Self::Named("cg".to_string())
289    }
290    /// Select the incomplete-Cholesky CG backend (symmetric SPD).
291    pub fn iccg() -> Self {
292        Self::Named("iccg".to_string())
293    }
294    /// Whether this is automatic selection.
295    pub fn is_auto(&self) -> bool {
296        matches!(self, Self::Auto)
297    }
298    /// The explicitly requested name, or `None` for [`SolverSelection::Auto`].
299    pub fn requested_name(&self) -> Option<&str> {
300        match self {
301            Self::Auto => None,
302            Self::Named(n) => Some(n.as_str()),
303        }
304    }
305}
306
307/// Why a particular solver was selected.
308#[derive(Debug, Clone, Copy, PartialEq, Eq)]
309pub enum SelectionReason {
310    /// The caller requested this backend explicitly.
311    ExplicitlyRequested,
312    /// Small system: dense is used for any matrix class.
313    SmallSystem,
314    /// Symmetric matrix whose diagonal is positive (necessary condition for
315    /// SPD): skyline is chosen; it verifies definiteness during factorization.
316    SymmetricPositiveDiagonal,
317    /// General (possibly non-symmetric) system: sparse LU.
318    GeneralSystem,
319    /// Very large system.
320    LargeSystem,
321}
322
323/// The outcome of a solver-selection query. No solver is constructed and no
324/// factorization is performed, so this is cheap and side-effect free.
325#[derive(Debug, Clone, PartialEq, Eq)]
326pub struct SolverSelectionInfo {
327    /// Canonical name of the chosen backend.
328    pub solver_name: String,
329    /// Why it was chosen.
330    pub reason: SelectionReason,
331}
332
333/// Validate that a solver with `caps` may legally handle `matrix`.
334///
335/// This is a **class** check (symmetry / generality). It deliberately does not
336/// attempt to prove positive definiteness: a symmetric indefinite matrix is a
337/// legal input to every backend that claims `general` support, and backends that
338/// require SPD (`skyline_ldlt`, `cg`, `iccg`) verify that themselves during
339/// [`LinearSolver::factor`], returning an error rather than a wrong answer.
340fn validate_solver_for_matrix(
341    name: &str,
342    caps: &SolverCapabilities,
343    matrix: &SparseMatrix,
344) -> Result<(), SolverError> {
345    if matrix.n == 0 {
346        return Err(SolverError::invalid_input("Empty matrix"));
347    }
348    if let Some(max_size) = caps.max_size.filter(|&m| matrix.n > m) {
349        return Err(SolverError::unsupported(format!(
350            "solver '{}' supports at most {} DOFs, but matrix has {}",
351            name, max_size, matrix.n
352        )));
353    }
354    let symmetric = matrix.is_symmetric(1e-12);
355    if !symmetric && !caps.general {
356        return Err(SolverError::unsupported(format!(
357            "solver '{}' requires a symmetric matrix, but the matrix is not symmetric; \
358             use 'dense' or 'sparse_lu'",
359            name
360        )));
361    }
362    Ok(())
363}
364
365/// Registry for solver backends
366pub struct SolverRegistry {
367    backends: std::collections::HashMap<String, Box<dyn LinearSolverFactory>>,
368}
369
370pub trait LinearSolverFactory: Send + Sync {
371    fn create(&self) -> Box<dyn LinearSolver>;
372    fn name(&self) -> &'static str;
373    fn capabilities(&self) -> SolverCapabilities;
374}
375
376impl SolverRegistry {
377    pub fn new() -> Self {
378        Self {
379            backends: std::collections::HashMap::new(),
380        }
381    }
382
383    pub fn register(&mut self, factory: Box<dyn LinearSolverFactory>) {
384        self.backends.insert(factory.name().to_string(), factory);
385    }
386
387    pub fn get(&self, name: &str) -> Option<&dyn LinearSolverFactory> {
388        self.backends.get(name).map(|b| b.as_ref())
389    }
390
391    pub fn list(&self) -> Vec<String> {
392        self.backends.keys().cloned().collect()
393    }
394
395    /// Registered solver names, sorted (deterministic).
396    pub fn list_sorted(&self) -> Vec<String> {
397        let mut v = self.list();
398        v.sort();
399        v
400    }
401
402    pub fn create(&self, name: &str) -> Option<Box<dyn LinearSolver>> {
403        self.backends.get(name).map(|f| f.create())
404    }
405
406    /// Validate that the named backend can legally handle `matrix`, returning
407    /// its capabilities on success. Performs **no** factorization.
408    ///
409    /// # Errors
410    ///
411    /// - [`SolverError::Unsupported`] if the name is unknown or the matrix class
412    ///   is incompatible with the backend.
413    /// - [`SolverError::InvalidInput`] for an empty matrix.
414    pub fn validate_selection(
415        &self,
416        name: &str,
417        matrix: &SparseMatrix,
418    ) -> Result<SolverCapabilities, SolverError> {
419        let factory = self
420            .get(name)
421            .ok_or_else(|| SolverError::unsupported(format!("unknown solver '{}'", name)))?;
422        let caps = factory.capabilities();
423        validate_solver_for_matrix(name, &caps, matrix)?;
424        Ok(caps)
425    }
426
427    /// Decide which backend would be used, **without** constructing or
428    /// factorizing anything. Answers "which solver, and why?".
429    ///
430    /// # Errors
431    ///
432    /// Returns an error for an unknown explicit name, an incompatible matrix
433    /// class, an empty matrix, or (for `Auto`) when no suitable backend exists.
434    pub fn select(
435        &self,
436        matrix: &SparseMatrix,
437        selection: &SolverSelection,
438    ) -> Result<SolverSelectionInfo, SolverError> {
439        match selection {
440            SolverSelection::Named(name) => {
441                self.validate_selection(name, matrix)?;
442                Ok(SolverSelectionInfo {
443                    solver_name: name.clone(),
444                    reason: SelectionReason::ExplicitlyRequested,
445                })
446            }
447            SolverSelection::Auto => self.auto_select_info(matrix),
448        }
449    }
450
451    /// The auto-selection policy, exposed as a decision (name + reason).
452    ///
453    /// Policy (conservative; never selects a solver that cannot handle the
454    /// detected matrix class):
455    ///
456    /// 1. `n <= 500` → `dense` (general, any class).
457    /// 2. symmetric with a positive diagonal (necessary condition for SPD) and
458    ///    within skyline's size limit → `skyline_ldlt` (it verifies definiteness
459    ///    at factorization).
460    /// 3. otherwise → `sparse_lu` (general; handles symmetric or not).
461    ///
462    /// Auto never selects `cg`/`iccg`. Unlike explicit selection, auto does not
463    /// hard-reject on `max_size`: it treats the limit as a preference and still
464    /// returns the only class-legal backend for very large systems.
465    ///
466    /// `cg`/`iccg` are never auto-selected: their SPD requirement cannot be
467    /// established reliably from the matrix alone.
468    pub fn auto_select_info(
469        &self,
470        matrix: &SparseMatrix,
471    ) -> Result<SolverSelectionInfo, SolverError> {
472        if matrix.n == 0 {
473            return Err(SolverError::invalid_input("Empty matrix"));
474        }
475
476        if matrix.n <= 500 && self.get("dense").is_some() {
477            return Ok(SolverSelectionInfo {
478                solver_name: "dense".to_string(),
479                reason: SelectionReason::SmallSystem,
480            });
481        }
482
483        // Symmetric with a positive diagonal: skyline is preferred, but only
484        // within its configured size limit (it requires SPD and verifies it at
485        // factorization).
486        if matrix.is_symmetric(1e-12) && has_positive_diagonal(matrix) {
487            let skyline_fits = self
488                .get("skyline_ldlt")
489                .is_some_and(|f| f.capabilities().max_size.is_none_or(|m| matrix.n <= m));
490            if skyline_fits {
491                return Ok(SolverSelectionInfo {
492                    solver_name: "skyline_ldlt".to_string(),
493                    reason: SelectionReason::SymmetricPositiveDiagonal,
494                });
495            }
496        }
497
498        if self.get("sparse_lu").is_some() {
499            return Ok(SolverSelectionInfo {
500                solver_name: "sparse_lu".to_string(),
501                reason: SelectionReason::GeneralSystem,
502            });
503        }
504
505        Err(SolverError::unsupported(
506            "no suitable solver is registered for this matrix",
507        ))
508    }
509
510    /// Construct a solver for `selection`, after capability validation.
511    ///
512    /// Explicit selections are authoritative: if the requested backend cannot
513    /// legally handle the matrix (or is unknown / uncreatable), an error is
514    /// returned and **no** other backend is substituted. `Auto` may pick any
515    /// backend that can handle the matrix class.
516    ///
517    /// The solver is returned **unfactored** — the caller calls
518    /// [`LinearSolver::factor`] then [`LinearSolver::solve`].
519    pub fn create_selected(
520        &self,
521        matrix: &SparseMatrix,
522        selection: &SolverSelection,
523    ) -> Result<Box<dyn LinearSolver>, SolverError> {
524        let info = self.select(matrix, selection)?;
525        self.create(&info.solver_name).ok_or_else(|| {
526            SolverError::backend_unavailable(format!(
527                "solver '{}' was selected but cannot be constructed",
528                info.solver_name
529            ))
530        })
531    }
532
533    /// Backwards-compatible automatic selection: returns the chosen solver, or
534    /// `None` if none is registered. Prefer [`Self::select`] /
535    /// [`Self::create_selected`] for new code.
536    pub fn auto_select(&self, matrix: &SparseMatrix) -> Option<Box<dyn LinearSolver>> {
537        let info = self.auto_select_info(matrix).ok()?;
538        self.create(&info.solver_name)
539    }
540}
541
542/// True if every diagonal entry of `matrix` is strictly positive.
543///
544/// This is a *necessary* (not sufficient) condition for SPD and is used only as
545/// a conservative screen for auto-selection. It never asserts definiteness.
546fn has_positive_diagonal(matrix: &SparseMatrix) -> bool {
547    let n = matrix.n;
548    let mut diag = vec![0.0f64; n];
549    if matrix.compressed {
550        for (i, d) in diag.iter_mut().enumerate() {
551            for k in matrix.row_ptr[i]..matrix.row_ptr[i + 1] {
552                if matrix.csr_cols[k] == i {
553                    *d = matrix.csr_vals[k];
554                }
555            }
556        }
557    } else {
558        for k in 0..matrix.rows.len() {
559            if matrix.rows[k] == matrix.cols[k] {
560                diag[matrix.rows[k]] = matrix.vals[k];
561            }
562        }
563    }
564    diag.iter().all(|&d| d > 0.0)
565}
566
567impl Default for SolverRegistry {
568    fn default() -> Self {
569        let mut registry = Self::new();
570
571        // Register built-in backends
572        registry.register(Box::new(DenseSolverFactory));
573        registry.register(Box::new(SkylineLdltFactory));
574        registry.register(Box::new(SparseLuFactory));
575        registry.register(Box::new(CgSolverFactory));
576        registry.register(Box::new(IccgSolverFactory));
577
578        registry
579    }
580}
581
582/// Factory for Dense Gaussian elimination
583struct DenseSolverFactory;
584impl LinearSolverFactory for DenseSolverFactory {
585    fn create(&self) -> Box<dyn LinearSolver> {
586        Box::new(DenseGaussianSolver::new())
587    }
588    fn name(&self) -> &'static str {
589        "dense"
590    }
591    fn capabilities(&self) -> SolverCapabilities {
592        SolverCapabilities::dense()
593    }
594}
595
596/// Factory for Skyline LDL^T
597struct SkylineLdltFactory;
598impl LinearSolverFactory for SkylineLdltFactory {
599    fn create(&self) -> Box<dyn LinearSolver> {
600        Box::new(SkylineLdltSolver::new())
601    }
602    fn name(&self) -> &'static str {
603        "skyline_ldlt"
604    }
605    fn capabilities(&self) -> SolverCapabilities {
606        SolverCapabilities::skyline_ldlt()
607    }
608}
609
610/// Factory for SparseLU
611struct SparseLuFactory;
612impl LinearSolverFactory for SparseLuFactory {
613    fn create(&self) -> Box<dyn LinearSolver> {
614        Box::new(SparseLuSolver::new())
615    }
616    fn name(&self) -> &'static str {
617        "sparse_lu"
618    }
619    fn capabilities(&self) -> SolverCapabilities {
620        SolverCapabilities::sparse_lu()
621    }
622}
623
624/// Factory for CG
625struct CgSolverFactory;
626impl LinearSolverFactory for CgSolverFactory {
627    fn create(&self) -> Box<dyn LinearSolver> {
628        Box::new(CgSolver::new())
629    }
630    fn name(&self) -> &'static str {
631        "cg"
632    }
633    fn capabilities(&self) -> SolverCapabilities {
634        SolverCapabilities::cg()
635    }
636}
637
638/// Factory for ICCG
639struct IccgSolverFactory;
640impl LinearSolverFactory for IccgSolverFactory {
641    fn create(&self) -> Box<dyn LinearSolver> {
642        Box::new(IccgSolver::new())
643    }
644    fn name(&self) -> &'static str {
645        "iccg"
646    }
647    fn capabilities(&self) -> SolverCapabilities {
648        SolverCapabilities::iccg()
649    }
650}
651
652// Re-export for public API
653pub use self::LinearSolver as Solver;
654pub use self::SolverCapabilities as Capabilities;
655pub use self::SolverError as Error;
656pub use self::SolverRegistry as Registry;