# Calculating Sparse Jacobians with Autodifferentiation

**URL:** <https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313>\
**Category:** Numerics\
**Tags:** package\
**Created:** [February 26, 2017, 7:12am UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313 "2017-02-26T07:12:18Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [February 26, 2017, 7:12am UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/1 "2017-02-26T07:12:18Z")

</div>

Is there a way with any of the autodifferentiation tools to specify a sprasity pattern or bandedness for the Jacobian? This is something which would be incredibly useful for the differential equation solvers, but I don’t know if it exists anywhere in the package ecosystem.

---

<div class="post-metadata">

**Author:** ![dfdx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dfdx/32/120_2.png) [@dfdx](https://discourse.julialang.org/u/dfdx)\
**Post date:** [February 26, 2017, 11:25am UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/2 "2017-02-26T11:25:11Z")

</div>

Can you provide a couple of examples of such sparse Jacobians? In [XDiff.jl](https://github.com/dfdx/XDiff.jl), I actively experiment with the symbolic representation of sparse arrays using Einstein notation, e.g.:

```julia
using XDiff

dxs = rdiff(:(y = 2x); ctx=Dict(:outfmt => :ein), x=rand(3))
dxs[:x]
# ==> 
# quote
# tmp1 = 2
# dy_dx[i, j] = tmp1 * (i == j)
# end

```

Here the derivative `dy/dx` is a sparse matrix, whose elements are equal `tmp1` (i.e. 2), but only when the first index `i` is equal to the second index `j`, e.g.:

```julia
 2 ⋅ ⋅
 ⋅ 2 ⋅
 ⋅ ⋅ 2

```

If this is similar to what you need, we can work it out to support your concrete use case.

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [February 26, 2017, 12:30pm UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/3 "2017-02-26T12:30:46Z")

</div>

There is [https://github.com/mauro3/MatrixColorings.jl](https://github.com/mauro3/MatrixColorings.jl) which would need updating. I think the code reasonably clean and it would probably be easier to use this as starting point than nothing. The dependency of Ragged.jl would need to be exchanged, probably for [https://github.com/mbauman/RaggedArrays.jl](https://github.com/mbauman/RaggedArrays.jl). I could move the package to DiffEq org, if that helps, or to JuliaDiff. (There is also these issues in ForwardDiff.jl [https://github.com/JuliaDiff/ForwardDiff.jl/issues/43](https://github.com/JuliaDiff/ForwardDiff.jl/issues/43), [https://github.com/JuliaDiff/ForwardDiff.jl/issues/91](https://github.com/JuliaDiff/ForwardDiff.jl/issues/91))

+1000 to get that functionality into Julia.

---

<div class="post-metadata">

**Author:** ![tkelman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkelman/32/692_2.png) [@tkelman](https://discourse.julialang.org/u/tkelman)\
**Post date:** [February 26, 2017, 4:43pm UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/4 "2017-02-26T16:43:41Z")

</div>

This is exactly what [ReverseDiffSparse](https://github.com/mlubin/ReverseDiffSparse.jl) does.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [February 26, 2017, 4:44pm UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/5 "2017-02-26T16:44:58Z")

</div>

> [@tkelman](#):
>
> This is exactly what ReverseDiffSparse does.

Really? The README says:

> Reverse-mode automatic differentiation for closed-form scalar algebraic expressions, producing gradients and Hessians.

> <https://github.com/mlubin/ReverseDiffSparse.jl/issues/18>
>
> It would be nice to be able to use coloring and AD for Jacobians as well, in my …case it would be for a function f:
> 
> \`\`\`
> f(y, ydot) = ....
> J = df/dy + a\* df/dydot 
> \`\`\`
> 
> I think this would entail two things: make the graph algorithms work on the non-symmetric case. Document it so I can figure out how to use it. It would be nice if both the coloring and the AD would be usable. The coloring alone I could then use for finite difference Jacobians.
> 
> I'm hoping to use this in https://github.com/JuliaLang/ODE.jl/pull/72
> 
> See also: https://groups.google.com/d/msg/julia-users/P\_56xjp3WVo/wbZj0Tu0TzwJ

---

<div class="post-metadata">

**Author:** ![mauro3](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mauro3/32/292_2.png) [@mauro3](https://discourse.julialang.org/u/mauro3)\
**Post date:** [February 26, 2017, 7:40pm UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/6 "2017-02-26T19:40:13Z")

</div>

Yes, Hessians are symmetric, thus different, (I think) more specialized coloring algorithms are used.

---

<div class="post-metadata">

**Author:** ![jrevels](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jrevels/32/10393_2.png) [@jrevels](https://discourse.julialang.org/u/jrevels)\
**Post date:** [February 28, 2017, 2:49am UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/7 "2017-02-28T02:49:36Z")

</div>

This is definitely something that’s planned for ReverseDiff, though there are items that I think would be more useful to tackle first, like factoring out the execution tracing infrastructure.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [February 28, 2017, 2:53am UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/8 "2017-02-28T02:53:31Z")

</div>

What about ForwardDiff? Won’t Jacobians do well there, or only for smaller Jacobians?

---

<div class="post-metadata">

**Author:** ![jrevels](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jrevels/32/10393_2.png) [@jrevels](https://discourse.julialang.org/u/jrevels)\
**Post date:** [February 28, 2017, 3:08am UTC](https://discourse.julialang.org/t/calculating-sparse-jacobians-with-autodifferentiation/2313/9 "2017-02-28T03:08:24Z")

</div>

Yup. A ForwardDiff-only implementation should be a bit simpler as well, if anybody wants to pursue it. It should basically come down to implementing a function which takes in a sparsity pattern and spits out a seeded dual number configuration that matched it.

Eventually, I expect ReverseDiff will win the day in this arena because of the ability to write optimization passes over the tape. One such optimization is to elide whole execution passes by showing they are constant w.r.t. specific output directions; I had this implemented at one point but rolled it back for the sake of a refactor (before the package was released). ReverseDiff can also leverage mixed-mode AD (i.e. switch to forward-mode if it’s more efficient to do so), though making those kinds of decisions automatically requires some finesse.

My secret dream is to have a unified mixed-mode AD package that makes all of these decisions for the user…