SparseConnectivityTracer.jl

Fast Jacobian and Hessian sparsity pattern detection via operator-overloading.

[!TIP] If you want to use automatic sparse differentiation to compute sparse Jacobians or Hessians with SparseConnectivityTracer (instead of just sparsity patterns), refer to the DifferentiationInterface.jl documentation.

Installation

To install this package, open the Julia REPL and run

julia> ]add SparseConnectivityTracer

Examples

Jacobian

For functions y = f(x) and f!(y, x), the sparsity pattern of the Jacobian can be obtained by computing a single forward-pass through the function:

julia> using SparseConnectivityTracer

julia> detector = TracerSparsityDetector();

julia> x = rand(3);

julia> f(x) = [x[1]^2, 2 * x[1] * x[2]^2, sin(x[3])];

julia> jacobian_sparsity(f, x, detector)
3×3 SparseArrays.SparseMatrixCSC{Bool, Int64} with 4 stored entries:
 1  ⋅  ⋅
 1  1  ⋅
 ⋅  ⋅  1

By default, BitSet is used for internal sparsity pattern representations. For very large inputs, it might be more efficient to set the type to Set{UInt}:

julia> detector = TracerSparsityDetector(; gradient_pattern_type=Set{UInt})

Hessian

For scalar functions y = f(x), the sparsity pattern of the Hessian can be obtained by computing a single forward-pass through the function:

julia> x = rand(4);

julia> f(x) = x[1] + x[2]*x[3] + 1/x[4];

julia> hessian_sparsity(f, x, detector)
4×4 SparseArrays.SparseMatrixCSC{Bool, Int64} with 3 stored entries:
 ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  1  ⋅
 ⋅  1  ⋅  ⋅
 ⋅  ⋅  ⋅  1

By default, dictionaries of BitSets are used for internal sparsity pattern representations. For very large inputs, it might be more efficient to set the type to Dict{UInt, Set{UInt}}:

julia> detector = TracerSparsityDetector(; hessian_pattern_type=Dict{UInt, Set{UInt}})

For more detailed examples, take a look at the documentation.

Local tracing

TracerSparsityDetector returns conservative "global" sparsity patterns over the entire input domain of x. It is not compatible with functions that require information about the primal values of a computation (e.g. iszero, >, ==). To compute a less conservative Jacobian or Hessian sparsity pattern at an input point x, use TracerLocalSparsityDetector instead. Note that patterns computed with TracerLocalSparsityDetector depend on the input x and have to be recomputed when x changes:

julia> using SparseConnectivityTracer

julia> detector = TracerLocalSparsityDetector();

julia> f(x) = x[1] > x[2] ? x[1] : x[2];

julia> jacobian_sparsity(f, [1 2], detector)
1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 1 stored entry:
 ⋅  1

julia> jacobian_sparsity(f, [2 1], detector)
1×2 SparseArrays.SparseMatrixCSC{Bool, Int64} with 1 stored entry:
 1  ⋅

Take a look at the documentation for more information on global and local patterns.

ADTypes.jl compatibility

SparseConnectivityTracer uses ADTypes.jl's interface for sparsity detection, making it compatible with DifferentiationInterface.jl's sparse automatic differentiation functionality. In fact, the functions jacobian_sparsity and hessian_sparsity are re-exported from ADTypes.

Related packages

• SparseDiffTools.jl: automatic sparsity detection via Symbolics.jl and Cassette.jl
• SparsityTracing.jl: automatic Jacobian sparsity detection using an algorithm based on SparsLinC by Bischof et al. (1996)

Citation

If you use SparseConnectivityTracer in your research, please cite our TMLR paper Sparser, Better, Faster, Stronger: Efficient Automatic Differentiation for Sparse Jacobians and Hessians:

@article{hill2025sparser,
  title={Sparser, Better, Faster, Stronger: Sparsity Detection for Efficient Automatic Differentiation},
  author={Adrian Hill and Guillaume Dalle},
  journal={Transactions on Machine Learning Research},
  issn={2835-8856},
  year={2025},
  url={https://openreview.net/forum?id=GtXSN52nIW},
  note={}
}

Acknowledgements

Adrian Hill gratefully acknowledges funding from the German Federal Ministry of Education and Research under the grant BIFOLD25B.