Use SparseConnectivityTracer.jl

amontoison commented 1 month ago

fix #232 @gdalle

github-actions[bot] commented 1 month ago

Package name	latest	stable
CaNNOLeS.jl
DCISolver.jl
DerivativeFreeSolvers.jl
JSOSolvers.jl
NLPModelsIpopt.jl
OptimalControl.jl
OptimizationProblems.jl
Percival.jl
QuadraticModels.jl
SolverBenchmark.jl
SolverTools.jl

gdalle commented 1 month ago

Can you try it with the branch from https://github.com/adrhill/SparseConnectivityTracer.jl/pull/75 ?

tmigot commented 1 month ago

Hi @amontoison @gdalle ! Thanks for adding this new feature. Can you make it that we don't remove the Symbolics-way of computing the sparse matrices? I am fine having both ways.

amontoison commented 1 month ago

@tmigot What do you want to keep Symbolics.jl?

tmigot commented 1 month ago

@tmigot What do you want to keep Symbolics.jl?

Why not? I don't think that the debate is 100% clear that the SparseConnectivityTracer is better than Symbolics, and it doesn't cost us a lot to maintain Symbolics for now.

gdalle commented 1 month ago

If you want to switch easily between both, I'd suggest using the ADTypes interface for sparsity detection. SparseConnectivityTracer supports it natively, and Symbolics will once https://github.com/JuliaSymbolics/Symbolics.jl/pull/1134 is merged. Then it will be as easy as switching the "detector" object

https://sciml.github.io/ADTypes.jl/stable/#Sparsity-detector

gdalle commented 1 month ago

Wait for https://github.com/adrhill/SparseConnectivityTracer.jl/issues/90

amontoison commented 3 weeks ago

@gdalle Do you have functions to perform J*u, J'*v, H*w in SCT.jl? I already dropped Symbolics.jl and I can drop SparseDiffTools.jl if I have these routines.

amontoison commented 3 weeks ago

@gdalle It seems that this case is not supported in ADTypes: https://github.com/amontoison/ADNLPModels.jl/blob/SCT/src/sparsity_pattern.jl#L9-L13

gdalle commented 3 weeks ago

Do you have functions to perform Ju, J'v, H*w in SCT.jl?

What do you mean by that? The result of a matrix-vector product is dense in general, why would you want its sparsity pattern?

gdalle commented 3 weeks ago

@gdalle It seems that this case is not supported in ADTypes: https://github.com/amontoison/ADNLPModels.jl/blob/SCT/src/sparsity_pattern.jl#L9-L13

You need to use the function from ADTypes with the detector

function compute_jacobian_sparsity(c, x0)
  detector = SparseConnectivityTracer.TracerSparsityDetector()  # replaceable
  S = ADTypes.jacobian_sparsity(c, x0, detector)
  return S
end

amontoison commented 3 weeks ago

@gdalle It seems that this case is not supported in ADTypes: https://github.com/amontoison/ADNLPModels.jl/blob/SCT/src/sparsity_pattern.jl#L9-L13

You need to use the function from ADTypes with the detector
function compute_jacobian_sparsity(c, x0)
  detector = SparseConnectivityTracer.TracerSparsityDetector()  # replaceable
  S = ADTypes.jacobian_sparsity(c, x0, detector)
  return S
end
My bad, I did the typo...

gdalle commented 3 weeks ago

@gdalle Do you have functions to perform Ju, J'v, H*w in SCT.jl?

These functions are not connected to the sparsity pattern. The right way to perform them is with DifferentiationInterface

amontoison commented 3 weeks ago

@gdalle Can you review the PR?

tmigot commented 3 weeks ago

Hi guys! Thanks @gdalle and @amontoison for this. Why did you end up droping Symbolics in the same PR? Have you guys run some performance benchmark?

gdalle commented 3 weeks ago

There are several reasons, which @amontoison summed up here: https://github.com/control-toolbox/CTDirect.jl/issues/88#issuecomment-2150412031. A big one was the compatibility issues of Symbolics (some recent versions were buggy, and it hasn't supported Julia 1.6 for a while) and the general weight of the SciML stack of dependencies, as opposed to the very lightweight SparseConnectivityTracer.

We didn't benchmark specifically against Symbolics on optimization problems. However we did run other benchmarks:

SparseConnectivityTracer against Symbolics on the Jacobian test case used in the very article that introduced Symbolics sparsity detection: https://github.com/adrhill/SparseConnectivityTracer.jl/pull/4#issuecomment-2093461551
SparseConnectivityTracer against JuMP: https://github.com/adrhill/SparseConnectivityTracer.jl/issues/118

Finally, note that SparseConnectivityTracer is only a default choice, not an eternal commitment. Thanks to the new ADTypes sparsity detection API, going back to Symbolics is basically as easy as replacing the detector object in the code below with SymbolicsSparsityDetector. I explained it in the PR https://github.com/JuliaSmoothOptimizers/ADNLPModels.jl/pull/238 before it was superseded by the present one.

https://github.com/JuliaSmoothOptimizers/ADNLPModels.jl/blob/29b1d2d4d4233041567b66a6645c24c6eba95888/src/sparsity_pattern.jl#L9-L16

I don't think this detector configuration is accessible to the user yet, because it is still in the low-level functions, but it would be good to pass this object down all the way from the top level API

tmigot commented 3 weeks ago

There are several reasons, which @amontoison summed up here: control-toolbox/CTDirect.jl#88 (comment). A big one was the compatibility issues of Symbolics (some recent versions were buggy, and it hasn't supported Julia 1.6 for a while)

Ok, but it is not a real constraint, it was just a versioning mistake that is being resolved.

and the general weight of the SciML stack of dependencies, as opposed to the very lightweight SparseConnectivityTracer.

Agreed.

I am in general very in favor of what you guys did here. My point was mainly that it is strange to do everything in the same PR especially if we don't benchmark this package. The correct strategy should have been:

add SparseConnectivityTracer
add a benchmark SparseConnectivityTracer/Symbolics
discuss about droping Symbolics ? (also it was only an optional dep so it didn't slow down the user experience, only the unit tests)

Could you open an issue to remember us to make the detector configuration accessible to users? Thanks!

gdalle commented 3 weeks ago

I agree with the temporary aspect of the SymbolicUtils kerfuffle. However, Julia 1.6 support was dropped some time ago by Symbolics and it isn't coming back. So that's a real limitation if you want to continue supporting 1.6, at least until 1.10 is declared as the new LTS.

I agree that big changes all at once are not ideal. Initially I tried a soft transition in PR #238 (just using the detector framework, but sticking with Symbolics). I got the tests working on 1.10 but they failed on 1.6 because of the missing SymbolicsSparsityDetector object (which was introduced after 1.6 support was dropped from Symbolics). I guess the SymbolicsSparsityDetector could have been backported to a version of Symbolics that does support 1.6, but given the tiresomeness of it all, Alexis and I thought it would be best to do a clean break

gdalle commented 3 weeks ago

I opened an issue to keep track of the detector configuration, and I'll add benchmarks against Symbolics to my SCT/JuMP comparison in https://github.com/adrhill/SparseConnectivityTracer.jl/issues/118

amontoison commented 3 weeks ago

There are several reasons, which @amontoison summed up here: control-toolbox/CTDirect.jl#88 (comment). A big one was the compatibility issues of Symbolics (some recent versions were buggy, and it hasn't supported Julia 1.6 for a while)

Ok, but it is not a real constraint, it was just a versioning mistake that is being resolved.

I wanted to have sparse AD by default here. The AD was sparse only if Symbolics.jl was installed. Note thay Symbolics.jl downloads all the internet when we install it. Because it was an optional dependency, we were unable to set a compat entry on it and depending on multiple factors, the version installed could be incompatible or broken.... It's not something that I want for the users of ADNLPModels.jl.

and the general weight of the SciML stack of dependencies, as opposed to the very lightweight SparseConnectivityTracer.

Agreed.

I am in general very in favor of what you guys did here. My point was mainly that it is strange to do everything in the same PR especially if we don't benchmark this package. The correct strategy should have been:

add SparseConnectivityTracer

add a benchmark SparseConnectivityTracer/Symbolics

discuss about droping Symbolics ? (also it was only an optional dep so it didn't slow down the user experience, only the unit tests)

I wanted to drop Symbolics.jl and SparsityPatternDetection.jl and it was the best strategy for me. Even if we lose performances (in the worst case), we can improve things with Guillaume and Adrian. We opened issues in Symbolics.jl two years ago and nothing was solved...

Could you open an issue to remember us to make the detector configuration accessible to users? Thanks!

It's already available as a keyword argument for the sparse AD backends (SparseADHessian and SparseADJacobian).

JuliaSmoothOptimizers / ADNLPModels.jl

Use SparseConnectivityTracer.jl #230