search

JuliaSmoothOptimizers / ADNLPModels.jl

Other
29 stars 12 forks source link

Replace ColPack with SparseMatrixColorings? #237

Closed gdalle closed 2 weeks ago

gdalle commented 1 month ago

Hi there @amontoison and friends! It's me again, and I come bearing gifts :sunglasses: My new package SparseMatrixColorings.jl aims to be a pure-Julia reimplementation of ColPack. It does not yet have every functionality, but it has the essentials. In addition, it offers decompression algorithms, and the test suite is outrageously thorough. Would you be interested in trying it out as a replacement for ColPack.jl? I haven't yet run benchmarks because there are some things I don't understand about the ColPack.jl interface (see https://github.com/exanauts/ColPack.jl/issues/12 if @michel2323 wants to help), but I expect performance to be rather good. As an alternative, we could try a full integration with DifferentiationInterface.jl as discussed in #229, but that might be a lot of change at once.

amontoison commented 3 weeks ago

It's fine to add SparseMatrixColorings here Guillaume but it will be great to have benchmarks if we replace colpack.jl. We could support both to more easily do the benchmarks?

gdalle commented 3 weeks ago

I'd love to benchmark against ColPack.jl but I need an answer to https://github.com/exanauts/ColPack.jl/issues/12, otherwise I don't even know where to start.

To support both coloring options, the right way would be to switch to the ADTypes coloring interface. It is implemented by SparseMatrixColorings.jl, and I can easily add it to ColPack.jl once I figure out the issue above.

As an example, PR #238 does something similar (switch from specific package to generic interface) with sparsity detection.

amontoison commented 3 weeks ago

@michel2323 We need you!

gdalle commented 3 weeks ago

I think I found the answer: https://github.com/exanauts/ColPack.jl/issues/12#issuecomment-2147837471

Bipartite coloring is not supported by ColPack.jl, even though it is the most efficient graph representation of Jacobian coloring problems. So I'll only be able to benchmark on Hessian coloring problems, which are symmetric. Let's see what that turns up

gdalle commented 3 weeks ago

Here are some benchmarks. In the range of parameters I've tested, SMC is uniformly better than ColPack.jl (but not necessarily better than ColPack itself). Full benchmark code here for @michel2323 to check:

https://gdalle.github.io/MatrixColoringComparison/

For the Jacobian benchmarks, the insane speedup is probably due to the construction of a column adjacency grah instead of the natural row-column bipartite graph. It's bad because the adjacency graph is much denser than the bipartite graph. ColPack itself (in C++) can work directly with bipartite graphs, so it's just a question of interfaces. In other words, this single line is a x10 performance hit at least: https://github.com/JuliaSmoothOptimizers/ADNLPModels.jl/blob/15d897d0b8af92f8faad67274919a28116590c62/src/ad.jl#L527

image

image

gdalle commented 3 weeks ago

Of course there's also the fact that ColPack (the C++ library) has had zero activity for the past 5 years, and that I trust pure readable Julia code a bit more than undertested C++ bindings (even though they get the job done and I'm grateful for them).

gdalle commented 2 weeks ago

With our latest changes in https://github.com/exanauts/ColPack.jl/pull/20, here's what I get for the partial column coloring of random sparse matrices (the star coloring plot stayed the same).

Note that this comparison is done with the natural order on vertices. ColPack is still better than SMC for custom orders (it has more of them and probably will compute them faster even once https://github.com/gdalle/SparseMatrixColorings.jl/pull/18 is merged).

image