Skip to main content

KktSolver

Trait KktSolver 

Source
pub trait KktSolver<T: Real> {
    type Symbolic;
    type Numeric;

    // Required methods
    fn analyze(
        &self,
        pattern: &Pattern,
        form: KktForm,
        ordering: &dyn Ordering,
    ) -> Result<Self::Symbolic, KktError>;
    fn factorize(
        &self,
        symbolic: &Self::Symbolic,
        k: &CscMatrix<T>,
        reg: Regularization<T>,
    ) -> Result<(Self::Numeric, Inertia), KktError>;
    fn solve(&self, numeric: &Self::Numeric, x: &mut [T]);
    fn nnz_factor(&self, numeric: &Self::Numeric) -> usize;
    fn name(&self) -> &'static str;

    // Provided methods
    fn solve_refined(
        &self,
        numeric: &Self::Numeric,
        k: &CscMatrix<T>,
        b: &[T],
        x: &mut [T],
        refinement: Refinement<T>,
    ) -> RefineReport<T> { ... }
    fn solve_refined_with(
        &self,
        numeric: &Self::Numeric,
        k: &CscMatrix<T>,
        b: &[T],
        x: &mut [T],
        refinement: Refinement<T>,
        work: &mut RefineWorkspace<T>,
    ) -> RefineReport<T> { ... }
}
Expand description

Analyze/factorize/solve of symmetric systems with a fixed pattern (the CHOLMOD shape, read, not copied). Regularization (its policy, Algorithm K) and refinement (Algorithm F) are shared by every backend.

use xingo_sparse::{
    Amd, Col, CscMatrix, KktForm, KktSolver, Refinement, Regularization, Row, SupernodalLdl,
};
// K = [−D, Aᵀ; A, 0] with D = diag(1, 2), A = [1 1]: lower triangle.
let k = CscMatrix::from_triplets(3, 3, &[
    (Row(0), Col(0), -1.0), (Row(2), Col(0), 1.0),
    (Row(1), Col(1), -2.0), (Row(2), Col(1), 1.0),
])
.unwrap();
let form = KktForm::Augmented { n_primal: 2, n_dual: 1 };
let solver = SupernodalLdl::<f64>::default(); // recommended; FaerLdl is the alternative
let sym = solver.analyze(&k.pattern(), form, &Amd::default()).unwrap();
let (num, inertia) = solver.factorize(&sym, &k, Regularization::default()).unwrap();
assert_eq!(inertia, form.expected_inertia(3)); // (S6): 1 positive, 2 negative
let b = [1.0, 0.0, 3.0];
let mut x = [0.0; 3];
let report = solver.solve_refined(&num, &k, &b, &mut x, Refinement::default());
assert!(report.converged && report.residual <= 1e-12);

Required Associated Types§

Source

type Symbolic

The result of the symbolic phase.

Source

type Numeric

The result of the numeric phase.

Required Methods§

Source

fn analyze( &self, pattern: &Pattern, form: KktForm, ordering: &dyn Ordering, ) -> Result<Self::Symbolic, KktError>

Symbolic phase on the lower triangle of pattern (plus a full diagonal) with the given ordering; done once per pattern.

Source

fn factorize( &self, symbolic: &Self::Symbolic, k: &CscMatrix<T>, reg: Regularization<T>, ) -> Result<(Self::Numeric, Inertia), KktError>

Numeric phase on the lower triangle of k (inside the analyzed pattern) with regularization (Algorithm K); returns the factor and its inertia (S6).

Source

fn solve(&self, numeric: &Self::Numeric, x: &mut [T])

x ← F⁻¹ x in place, dense, with F the regularized factor.

§Panics

If x.len() is not the order of the factor.

Source

fn nnz_factor(&self, numeric: &Self::Numeric) -> usize

Nonzeros of the factor (for the IPM log).

Source

fn name(&self) -> &'static str

A short name for logs and tables.

Provided Methods§

Source

fn solve_refined( &self, numeric: &Self::Numeric, k: &CscMatrix<T>, b: &[T], x: &mut [T], refinement: Refinement<T>, ) -> RefineReport<T>

Solve followed by iterative refinement against k (Algorithm F); keeps the best iterate (S7). k is the matrix to be solved — the unregularized one the factor approximates, or any other with the same order; only its lower triangle is read. x is overwritten. Allocates its work vectors; KktSolver::solve_refined_with reuses them.

§Panics

If b, x and k do not have the order of the factor.

Source

fn solve_refined_with( &self, numeric: &Self::Numeric, k: &CscMatrix<T>, b: &[T], x: &mut [T], refinement: Refinement<T>, work: &mut RefineWorkspace<T>, ) -> RefineReport<T>

KktSolver::solve_refined with caller-owned work vectors: once work has served a call with the same order and budget, the refinement allocates nothing.

§Panics

If b, x and k do not have the order of the factor.

Dyn Compatibility§

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors§