# Inverse subset algorithm?

**URL:** <https://discourse.julialang.org/t/inverse-subset-algorithm/102252>\
**Category:** Numerics\
**Tags:** linearalgebra, sparse\
**Created:** [July 29, 2023, 8:18pm UTC](https://discourse.julialang.org/t/inverse-subset-algorithm/102252 "2023-07-29T20:18:11Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![ElOceanografo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eloceanografo/32/624_2.png) [@ElOceanografo](https://discourse.julialang.org/u/ElOceanografo)\
**Post date:** [July 29, 2023, 8:18pm UTC](https://discourse.julialang.org/t/inverse-subset-algorithm/102252/1 "2023-07-29T20:18:11Z")

</div>

Reading [this paper](https://doi.org/10.18637/jss.v070.i05), I came across a reference to the “inverse subset algorithm,” in the context of efficiently calculating the gradient of the log-determinant of a sparse symmetric matrix (Section 4.1, Equation 8 and immediately below). I’m not familiar with it, and before going down a total rabbit hole, I was wondering if it’s already implemented or otherwise available anywhere in the Julia ecosystem?

Relevant to this issue in ChainRules: [Errors for gradient and hessian of logabsdet of sparse matrix · Issue #719 · JuliaDiff/ChainRules.jl · GitHub](https://github.com/JuliaDiff/ChainRules.jl/issues/719)

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [July 30, 2023, 11:54am UTC](https://discourse.julialang.org/t/inverse-subset-algorithm/102252/2 "2023-07-30T11:54:34Z")

</div>

> [@ElOceanografo](#):
>
> Reading [this paper](https://github.com/JuliaDiff/ChainRules.jl/issues/719), I came across a reference

It seems you put the wrong link, it links to the Github issue instead of to a paper.

---

<div class="post-metadata">

**Author:** ![ElOceanografo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eloceanografo/32/624_2.png) [@ElOceanografo](https://discourse.julialang.org/u/ElOceanografo)\
**Post date:** [July 30, 2023, 7:01pm UTC](https://discourse.julialang.org/t/inverse-subset-algorithm/102252/3 "2023-07-30T19:01:44Z")

</div>

My mistake, pasted the same link twice. Paper is here: [TMB: Automatic Differentiation and Laplace Approximation | Journal of Statistical Software](https://www.jstatsoft.org/article/view/v070i05)

---

<div class="post-metadata">

**Author:** ![ElOceanografo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eloceanografo/32/624_2.png) [@ElOceanografo](https://discourse.julialang.org/u/ElOceanografo)\
**Post date:** [August 1, 2023, 9:37pm UTC](https://discourse.julialang.org/t/inverse-subset-algorithm/102252/4 "2023-08-01T21:37:42Z")

</div>

OK, one rabbit hole later, it seems the answer to my question is “no.” There is an implementation buried in SuiteSparse [here](https://github.com/PetterS/SuiteSparse/tree/master/MATLAB_Tools/sparseinv), but it does not seem to be exposed in Julia’s SparseArrays.LibSuiteSparse. There is also an R package “sparseinv” that [appears to wrap](https://search.r-project.org/CRAN/refmans/sparseinv/html/Takahashi_Davis.html) that code.

---

<div class="post-metadata">

**Author:** ![ElOceanografo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eloceanografo/32/624_2.png) [@ElOceanografo](https://discourse.julialang.org/u/ElOceanografo)\
**Post date:** [August 7, 2023, 5:02pm UTC](https://discourse.julialang.org/t/inverse-subset-algorithm/102252/5 "2023-08-07T17:02:50Z")

</div>

For anyone who finds this later, I put together a small package (registration pending) implementing this algorithm here:

> <https://github.com/ElOceanografo/SparseInverseSubset.jl/blob/main/src/SparseInverseSubset.jl>