Linear Systems

This page documents verified linear system solvers.

Overview

Verified linear system solvers provide rigorous enclosures for solutions of $Ax = b$ with guaranteed error bounds. Multiple methods are available depending on the matrix properties and desired tightness of bounds.

Krawczyk Method

The Krawczyk method uses interval Newton iteration to verify and refine solutions. See src/linear_system/Krawczyk.jl for the basic implementation.

HBR Method

The Hansen-Bliek-Rohn enclosure method provides componentwise bounds.

• hbr_method - Main HBR solver
• hbr_method_simple - Simplified variant
• HBRResult - Result type

Gaussian Elimination

Verified Gaussian elimination with interval pivoting.

• interval_gaussian_elimination - Verified Gaussian elimination
• interval_gaussian_elimination_det - With determinant computation
• is_regular_gaussian_elimination - Regularity test via GE
• GaussianEliminationResult - Result type

Iterative Methods

Interval iterative methods for large sparse systems.

• interval_gauss_seidel - Interval Gauss-Seidel iteration
• interval_jacobi - Interval Jacobi iteration
• IterativeResult - Result type

Preconditioning

Preconditioning strategies for improving convergence.

• compute_preconditioner - Compute preconditioner
• apply_preconditioner - Apply preconditioner to system
• is_well_preconditioned - Check preconditioning quality
• PreconditionerResult - Result type

Preconditioner types (see PreconditionerType):

• MidpointInverse - Inverse of midpoint matrix
• LUFactorization - LU-based preconditioner
• LDLTFactorization - LDLT-based preconditioner (symmetric)
• IdentityPreconditioner - No preconditioning

Overdetermined Systems

Least squares solutions for overdetermined systems.

• subsquares_method - Subsquares method
• multi_jacobi_method - Multi-Jacobi method
• interval_least_squares - Interval least squares
• OverdeterminedResult - Result type

Shaving

Interval shaving for tightening bounds.

• interval_shaving - Iterative shaving
• sherman_morrison_inverse_update - Efficient inverse updates
• ShavingResult - Result type

H-Matrix Systems

Verified solvers for H-matrices (hierarchical matrices).

• verified_linear_solve_hmatrix - H-matrix linear solver
• VerifiedLinearSystemResult - Result type

Matrix Regularity

Functions to verify matrix regularity (invertibility).

• is_regular - Main regularity test
• is_regular_sufficient_condition - Sufficient condition check
• is_regular_gershgorin - Gershgorin-based check
• is_regular_diagonal_dominance - Diagonal dominance check
• is_singular_sufficient_condition - Singularity test
• RegularityResult - Result type

Determinant Bounds

Rigorous bounds on matrix determinants.

• interval_det - Interval determinant
• det_hadamard - Hadamard bound
• det_gershgorin - Gershgorin bound
• det_cramer - Cramer-based bound
• contains_zero - Check if determinant contains zero
• DeterminantResult - Result type