Replace ColPack with SparseMatrixColorings?

[gdalle]

Hi there @amontoison and friends! It's me again, and I come bearing gifts 😎
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 exanauts/ColPack.jl#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]

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]

I'd love to benchmark against ColPack.jl but I need an answer to exanauts/ColPack.jl#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]

@michel2323 We need you!

[gdalle]

I think I found the answer: exanauts/ColPack.jl#12 (comment)

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]

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:

ADNLPModels.jl/src/ad.jl

Line 527 in 15d897d

adjA = ColPack.matrix2adjmatrix(A; partition_by_rows = partition_by_rows)

[gdalle]

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]

With our latest changes in exanauts/ColPack.jl#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 gdalle/SparseMatrixColorings.jl#18 is merged).