GitHub

SelectedInversion

Quickly compute selected entries of the inverse of a sparse matrix.

Introduction

Sparse matrices are one of the pillars of scientific computing. Sparse factorization methods allow us to solve linear systems involving the inverse efficiently. But in some applications, we might need a bunch of entries of the inverse. Selected inversion algorithms efficiently compute those entries of the inverse that correspond to non-zero entries in the factorization.

SelectedInversion.jl directly interfaces with CHOLMOD-based Cholesky factorizations, which are the default for sparse symmetric positive-definite matrices in Julia.

Installation

SelectedInversion.jl is a registered Julia package. To install it:

  1. Download Julia (>= version 1.10).

  2. Launch the Julia REPL and type ] add SelectedInversion.

SelInv API

Make sure to also check the Tutorial.

SelectedInversion.selinv — Function
selinv(A::SparseMatrixCSC; depermute=false)
    -> @NamedTuple{Z::AbstractMatrix, p::Vector{Int64}}

Compute the selected inverse Z of A. The sparsity pattern of Z corresponds to that of the Cholesky factor of A, and the nonzero entries of Z match the corresponding entries in A⁻¹.

Arguments

  • A::SparseMatrixCSC: The sparse symmetric positive definite matrix for which the selected inverse will be computed.

Keyword arguments

  • depermute::Bool: Whether to depermute the selected inverse or not.

Returns

A named tuple Zp. Zp.Z is the selected inverse, and Zp.p is the permutation vector of the corresponding sparse Cholesky factorization.

source
selinv(F::SparseArrays.CHOLMOD.Factor; depermute=false)
    -> @NamedTuple{Z::AbstractMatrix, p::Vector{Int64}}

Compute the selected inverse Z of some matrix A based on its sparse Cholesky factorization F.

Arguments

  • F::SparseArrays.CHOLMOD.Factor: Sparse Cholesky factorization of some matrix A. F will be used internally for the computations underlying the selected inversion of A.

Keyword arguments

  • depermute::Bool: Whether to depermute the selected inverse or not.

Returns

A named tuple Zp. Zp.Z is the selected inverse, and Zp.p is the permutation vector of the corresponding sparse Cholesky factorization.

source
selinv(F::LDLt; depermute=false) -> @NamedTuple{Z::AbstractMatrix, p::Vector{Int64}}

Compute the selected inverse based on Julia's built-in LDL^T factorization.

This method converts the LDL^T factorization to LL^T format by copying the L factor and setting the diagonal to 1/D[k,k], then uses the existing simplicial selected inversion algorithm.

Arguments

  • F::LDLt: Built-in Julia LDL^T factorization (e.g., from ldlt(A) on SymTridiagonal)

Keyword arguments

  • depermute::Bool: Whether to depermute the selected inverse or not.

Returns

A named tuple Zp. Zp.Z is the selected inverse, and Zp.p is the permutation vector.

source
selinv(A::SymTridiagonal; depermute=false) -> @NamedTuple{Z::AbstractMatrix, p::Vector{Int64}}

Compute the selected inverse of a symmetric tridiagonal matrix.

This method leverages Julia's efficient built-in ldlt factorization for SymTridiagonal matrices, which has a specialized fast implementation for tridiagonal structures.

Arguments

  • A::SymTridiagonal: The symmetric tridiagonal matrix

Keyword arguments

  • depermute::Bool: Whether to depermute the selected inverse or not.

Returns

A named tuple Zp. Zp.Z is the selected inverse, and Zp.p is the permutation vector.

source
SelectedInversion.selinv_diag — Function
selinv_diag(A; depermute=true) -> Vector{Float64}

Compute the diagonal of the selected inverse of A.

Arguments

  • A: A sparse matrix or a factorization object.

Keyword arguments

  • depermute::Bool: Whether to depermute the diagonal or not. Default is true.

Returns

A vector containing the diagonal entries of the selected inverse.

source
selinv_diag(F::LDLt{T, SymTridiagonal{T, Vector{T}}}; depermute=true) -> Vector{Float64}

Optimized diagonal computation for LDLt factorizations of SymTridiagonal matrices. Leverages precomputed D and L factors to skip the forward pass entirely.

Arguments

  • F::LDLt: LDLt factorization of a SymTridiagonal matrix

Keyword arguments

  • depermute::Bool: Whether to depermute the diagonal or not. Default is true.

Returns

A vector containing the diagonal entries of the selected inverse.

source
selinv_diag(A::SymTridiagonal; depermute=true) -> Vector{Float64}

Compute the diagonal of the selected inverse of a symmetric tridiagonal matrix.

This method uses a specialized Kalman smoother-inspired algorithm that is much faster than the general approach, achieving O(n) time complexity with only two passes through the data and minimal allocations.

Arguments

  • A::SymTridiagonal: The symmetric tridiagonal matrix

Keyword arguments

  • depermute::Bool: Whether to depermute the diagonal or not. Default is true. For SymTridiagonal matrices, no permutation is applied, so this parameter has no effect but is kept for interface consistency.

Returns

A vector containing the diagonal entries of the selected inverse.

source