# How to NLsolve with sparsity but no jacobian?

**URL:** <https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462>\
**Category:** Optimization (Mathematical)\
**Tags:** question, package, diffeq, differentiation\
**Created:** [November 24, 2019, 8:39pm UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462 "2019-11-24T20:39:49Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![MatFi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/matfi/32/10002_2.png) [@MatFi](https://discourse.julialang.org/u/MatFi)\
**Post date:** [November 24, 2019, 8:39pm UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462/1 "2019-11-24T20:39:49Z")

</div>

From the [NLsolve-docs](https://github.com/JuliaNLSolvers/NLsolve.jl) i know that one can pass a jacobian to `nlsolve` and make the solver treating the jacobian as sparse.  
But what can I do when I don’t want to write down a jacobian of a PDE discretisation, and only know its sparsity pattern?  
I tried to pass this pattern to `DiffEqDiffTools.forwarddiff_color_jacobian!`. The resulting jacobian than to `nlsolve`. And surprise… specifing a jacobian that way ended up with `nlsolve` taking for ever to get a wrong / `NaN` solution.

Here is what I have tired.

```julia
using SparseDiffTools
using DiffEqDiffTools
using NLsolve

f! = (dx, x) -> rhs!(dx, x, some_parameters, 0) # Discretized PDE

jac = some_sparsity_pattern_ of_J_from_f!
colors = matrix_colors(jac)
 j = (jac, x) -> forwarddiff_color_jacobian!(jac, f!, x, colorvec = colors)

x0 = some_initial_guess 
#then I call
nlsolve(f, j, x0) # slow
nlsolve(f , x0) # fast and works (but want to have it faster)

```

Is there any way exploit the sparsity of the jacobian to speed up `nlsolve` ?

---

<div class="post-metadata">

**Author:** ![MatFi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/matfi/32/10002_2.png) [@MatFi](https://discourse.julialang.org/u/MatFi)\
**Post date:** [November 24, 2019, 9:07pm UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462/2 "2019-11-24T21:07:24Z")

</div>

I’ve just figured out that the problem caused by the colorvec argument. Without it works but no gain in terms of speed is observed.

---

<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:** [November 24, 2019, 9:43pm UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462/3 "2019-11-24T21:43:41Z")

</div>

Using just the `colorvec` will build the compressed Jacobian. You need to make sure you decompress it, and for that you need to pass the sparsity pattern to `sparsity`. So in most use cases you’ll want to pass both `colorvec` and `sparsity`.

---

<div class="post-metadata">

**Author:** ![MatFi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/matfi/32/10002_2.png) [@MatFi](https://discourse.julialang.org/u/MatFi)\
**Post date:** [November 24, 2019, 10:00pm UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462/4 "2019-11-24T22:00:37Z")

</div>

Ahhh … The inplace variant does not provide such an sparsity argument ( but the out of place does). I looks like that nlsolve simply offers dense target variables for the Jacobians, so that the sparsity information is lost, this I totally have missed…thanks so far. OK tomorrow I will elaboate on this…

---

<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:** [November 24, 2019, 10:15pm UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462/5 "2019-11-24T22:15:05Z")

</div>

> [@MatFi](#):
>
> The inplace variant does not provide such an sparsity argument

Yes it does. It’s the argument called `sparsity`.

---

<div class="post-metadata">

**Author:** ![MatFi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/matfi/32/10002_2.png) [@MatFi](https://discourse.julialang.org/u/MatFi)\
**Post date:** [November 25, 2019, 8:34am UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462/6 "2019-11-25T08:34:59Z")

</div>

> [@ChrisRackauckas](#):
>
> Yes it does. It’s the argument called `sparsity` .

Indeed, thanks for that hint again. Now it works quite nicely

```julia
f! = (dx, x) -> rhs!(dx, x, some_parameters, 0) # Discretized PDE

jac_sp = some_sparsity_pattern_ of_J_from_f!
colors = matrix_colors(jac_sp)
j!(jac,x)= forwarddiff_color_jacobian!(jac,f, x;
                                        colorvec = colors,
                                        sparsity = jac_sp)

x0 = some_initial_guess 

nlsolve(f!, x0) # 13 s
nlsolve(f!, j!, x0) # 11 s

# ask nlsolve to manipulate sparse matrices instead of full ones
df = OnceDifferentiable(f!, j!, u0,copy(u0), jac_sp)
nlsolve(df, u0) # 2 s

```

that’s quite nice (650% faster in my case)… @ChrisRackauckas : might it also be worth to wrap something like that i to `SSRootfind`?

---

<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:** [November 25, 2019, 8:39am UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462/7 "2019-11-25T08:39:59Z")

</div>

Indeed it would be good to do that in SSRootfind. But also, I think NLsolve should just be enhanced so that the `colorvec = colors` argument is exposed and then `sparsity` should always be set to the sparse Jacobian if you’ve passed that to NLsolve. Then this would be fairly automatic.

Then, Optim.jl should also take the `colorvec` and `sparsity` arguments, and everything with sparse handling would be cohesive.

@pkofod see the example above.

---

<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:** [November 25, 2019, 8:41am UTC](https://discourse.julialang.org/t/how-to-nlsolve-with-sparsity-but-no-jacobian/31462/8 "2019-11-25T08:41:38Z")

</div>

For future reference on what was going on here with the compression/decompression, consult the following notes:

[https://mitmath.github.io/18337/lecture9/stiff\_odes](https://mitmath.github.io/18337/lecture9/stiff_odes)