Data

Tools

Indexes

Applications

Experiments

Open Source Science

SparseConnectivityTracer

Fast operator-overloading Jacobian & Hessian sparsity detection.

https://github.com/adrhill/sparseconnectivitytracer.jl

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ✓
    DOI references
    Found 2 DOI reference(s) in README
  • ✓
    Academic publication links
    Links to: arxiv.org, zenodo.org
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (10.2%) to scientific vocabulary

Keywords

autodiff hessian jacobian julia sparsity
Last synced: 6 months ago · JSON representation ·

Repository

Fast operator-overloading Jacobian & Hessian sparsity detection.

Basic Info
  • Host: GitHub
  • Owner: adrhill
  • License: mit
  • Language: Julia
  • Default Branch: main
  • Homepage:
  • Size: 2.05 MB
Statistics
  • Stars: 49
  • Watchers: 3
  • Forks: 7
  • Open Issues: 8
  • Releases: 36
Topics
autodiff hessian jacobian julia sparsity
Created almost 2 years ago · Last pushed 6 months ago
Metadata Files
Readme Changelog License Citation

README.md

SparseConnectivityTracer.jl

| | | |:--------------|:--------------------------------------------------------------------| | Documentation | Stable Dev Changelog | | Build Status | Build Status Coverage Aqua JET | | Code Style | Code Style: Runic ColPrac: Contributor's Guide on Collaborative Practices for Community Packages | | Downloads | Downloads Dependents | | Citation | arXiv DOI Zenodo DOI |

Fast Jacobian and Hessian sparsity detection via operator-overloading.

Installation

To install this package, open the Julia REPL and run

julia-repl 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-repl 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 ```

As a larger example, let's compute the sparsity pattern from a convolutional layer from Flux.jl:

```julia-repl julia> using SparseConnectivityTracer, Flux

julia> detector = TracerSparsityDetector();

julia> x = rand(28, 28, 3, 1);

julia> layer = Conv((3, 3), 3 => 2);

julia> jacobian_sparsity(layer, x, detector) 1352×2352 SparseArrays.SparseMatrixCSC{Bool, Int64} with 36504 stored entries: ⎡⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣷⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎤ ⎢⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠀⠀⠀⠀⠙⢿⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠀⠀⠀⠀⠀⠀⠙⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⎥ ⎢⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⣀⠀⠀⠀⎥ ⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠻⣷⣄⠀⎥ ⎢⢤⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠛⢦⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠳⣤⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⠓⎥ ⎢⠀⠙⢿⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠀⠀⠀⠉⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠀⠀⠀⠀⠀⠈⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⣄⠀⠀⠀⠀⠀⠀⎥ ⎢⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠻⣷⣄⠀⠀⠀⠀⎥ ⎢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⠀⠀⎥ ⎣⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⢿⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣷⣄⎦ ```

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-repl julia> detector = TracerSparsityDetector(; gradient_pattern_type=Set{UInt})

Hessian

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

```julia-repl julia> x = rand(5);

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

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

julia> g(x) = f(x) + x[2]^x[5];

julia> hessian_sparsity(g, x, detector) 5×5 SparseArrays.SparseMatrixCSC{Bool, Int64} with 7 stored entries: ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1 1 ⋅ 1 ⋅ 1 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 1 ⋅ ⋅ 1 ⋅ ⋅ 1 ```

By default, a dictionaries of BitSet 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-repl 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 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 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-repl julia> using SparseConnectivityTracer

julia> detector = TracerLocalSparsityDetector();

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

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

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

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 preprint Sparser, Better, Faster, Stronger: Efficient Automatic Differentiation for Sparse Jacobians and Hessians:

bibtex @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.

Owner

  • Name: Adrian Hill
  • Login: adrhill
  • Kind: user
  • Location: Berlin
  • Company: TU Berlin

PhD student @ TU Berlin

Citation (CITATION.cff) 

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
  - family-names: "Hill"
    given-names: "Adrian"
    orcid: "https://orcid.org/0009-0009-5977-301X"
  - family-names: "Dalle"
    given-names: "Guillaume"
    orcid: "https://orcid.org/0000-0003-4866-1687"
title: "SparseConnectivityTracer.jl"
version: 0.1.0
date-released: 2024-04-22
url: "https://github.com/adrhill/SparseConnectivityTracer.jl"
preferred-citation:
  type: article
  authors:
  - family-names: "Hill"
    given-names: "Adrian"
    orcid: "https://orcid.org/0009-0009-5977-301X"
  - family-names: "Dalle"
    given-names: "Guillaume"
    orcid: "https://orcid.org/0000-0003-4866-1687"
  title: "Sparser, Better, Faster, Stronger: Sparsity Detection for Efficient Automatic Differentiation"
  journal: "Transactions on Machine Learning Research"
  year: 2025
  issn: "2835-8856"
  url: "https://openreview.net/forum?id=GtXSN52nIW"

GitHub Events

Total
  • Create event: 28
  • Commit comment event: 20
  • Release event: 13
  • Issues event: 30
  • Watch event: 20
  • Delete event: 15
  • Issue comment event: 149
  • Push event: 127
  • Pull request review comment event: 60
  • Pull request review event: 55
  • Pull request event: 51
  • Fork event: 3
Last Year
  • Create event: 28
  • Commit comment event: 20
  • Release event: 13
  • Issues event: 30
  • Watch event: 20
  • Delete event: 15
  • Issue comment event: 149
  • Push event: 127
  • Pull request review comment event: 60
  • Pull request review event: 55
  • Pull request event: 51
  • Fork event: 3

Issues and Pull Requests

Last synced: 6 months ago

All Time
  • Total issues: 55
  • Total pull requests: 110
  • Average time to close issues: about 2 months
  • Average time to close pull requests: 7 days
  • Total issue authors: 12
  • Total pull request authors: 9
  • Average comments per issue: 4.33
  • Average comments per pull request: 3.18
  • Merged pull requests: 91
  • Bot issues: 0
  • Bot pull requests: 3
Past Year
  • Issues: 22
  • Pull requests: 76
  • Average time to close issues: 30 days
  • Average time to close pull requests: 8 days
  • Issue authors: 9
  • Pull request authors: 9
  • Average comments per issue: 2.82
  • Average comments per pull request: 2.29
  • Merged pull requests: 57
  • Bot issues: 0
  • Bot pull requests: 3
View more stats
Top Authors
Issue Authors
  • adrhill (37)
  • gdalle (32)
  • SouthEndMusic (7)
  • ErikQQY (3)
  • amontoison (3)
  • Vaibhavdixit02 (1)
  • visr (1)
  • gbaraldi (1)
  • ranocha (1)
  • aml5600 (1)
  • JuliaTagBot (1)
  • baggepinnen (1)
Pull Request Authors
  • adrhill (165)
  • gdalle (42)
  • SouthEndMusic (8)
  • dependabot[bot] (7)
  • ErikQQY (4)
  • visr (4)
  • ranocha (2)
  • Vaibhavdixit02 (1)
  • amontoison (1)
  • hexaeder (1)
Top Labels
Issue Labels
enhancement (8) new overloads (7) discussion (7) bug (6) good first issue (3) input tracing (3) array (3) documentation (2) patterns (2) not planned (2) run benchmark (1) breaking change (1) new overload needed (1) breaking (1)
Pull Request Labels
run benchmark (26) dependencies (7) patterns (7) documentation (5) new overloads (4) bug (2) breaking change (2) github_actions (1) testing (1) enhancement (1)

Packages

  • Total packages: 1
  • Total downloads:
    • julia 4,917 total
  • Total dependent packages: 0
  • Total dependent repositories: 0
  • Total versions: 35
juliahub.com: SparseConnectivityTracer

Fast operator-overloading Jacobian & Hessian sparsity detection.

  • Versions: 35
  • Dependent Packages: 0
  • Dependent Repositories: 0
  • Downloads: 4,917 Total
Rankings
Dependent repos count: 9.5%
Average: 24.0%
Dependent packages count: 38.5%
Last synced: 6 months ago

Dependencies

.github/workflows/CI.yml actions
  • actions/checkout v4 composite
  • codecov/codecov-action v3 composite
  • julia-actions/cache v1 composite
  • julia-actions/julia-buildpkg v1 composite
  • julia-actions/julia-docdeploy v1 composite
  • julia-actions/julia-processcoverage v1 composite
  • julia-actions/julia-runtest v1 composite
  • julia-actions/setup-julia v1 composite
.github/workflows/CompatHelper.yml actions
.github/workflows/TagBot.yml actions
  • JuliaRegistries/TagBot v1 composite
.github/workflows/Benchmark.yml actions
  • actions/cache v3 composite
  • actions/checkout v4 composite
  • julia-actions/setup-julia latest composite