Module direct_solver 

Sparse direct solvers

This module provides production-quality direct solvers for sparse linear systems:

• Sparse LU factorization: Dense kernel with partial pivoting, AMD column ordering
• Sparse Cholesky: For symmetric positive definite (SPD) matrices
• Fill-reducing orderings: AMD (Approximate Minimum Degree), nested dissection
• Symbolic analysis: Determines the fill-in pattern before numeric factorization
• Numeric factorization: Computes the actual factor values
• Triangular solves: Forward and backward substitution

Architecture

Factorization is split into two phases:

1. Ordering phase — Computes a fill-reducing permutation (AMD or nested dissection)
2. Numeric phase — Applies the permutation, then factors the reordered matrix

References

• Davis, T.A. (2006). “Direct Methods for Sparse Linear Systems”. SIAM.
• Amestoy, P.R., Davis, T.A., & Duff, I.S. (1996). “An approximate minimum degree ordering algorithm”. SIAM J. Matrix Anal. Appl. 17(4), 886-905.
• George, A. & Liu, J.W. (1981). “Computer Solution of Large Sparse Positive Definite Systems”. Prentice-Hall.

Structs

SparseCholResult

Result of sparse Cholesky factorization (L * L^T = PAP^T).

SparseCholeskySolver

Sparse Cholesky solver for symmetric positive definite matrices.

SparseLuResult

Result of sparse LU factorization (PAQ = L*U).

SparseLuSolver

Sparse LU solver with partial pivoting.

SymbolicAnalysis

Result of the symbolic analysis phase.

Traits

SparseSolver

Trait for sparse direct solvers.

Functions

amd_ordering

Approximate Minimum Degree (AMD) ordering.

elimination_tree

Compute the elimination tree of a symmetric matrix.

inverse_perm

Compute the inverse permutation.

nested_dissection_ordering

Nested dissection ordering.

sparse_cholesky_solve

Solve Ax = b using sparse Cholesky (matrix must be SPD).

sparse_lu_solve

Solve Ax = b using sparse LU factorization with AMD ordering.

symbolic_cholesky

Perform symbolic analysis for Cholesky factorization.