Decompression of acyclic coloring with SparseMatrixCSC

[amontoison]

The current code is quite optimal, but we could optimize further for SparseMatrixCSC by storing here four values (i, j, k1, k2), where k1 is the position in A.nzval of A[i,j] and k2 is the position of A[j,i] in A.nzval.

We should do the same thing for diagonal coefficients here.

The current issue is that I don't know how to use this information if we just want to update one triangle of the Hessian.
The positions in A.nzval are not valid anymore.

[gdalle]

Feel free to give it a try!
Ideally I would want to avoid having three separate index storages, one for the full Hessian and one for each triangle, so indeed I'm not sure how to handle only one triangle.

[amontoison]

I have a solution @gdalle!

If H[i,j] is in the upper triangular part (i < j) we could store the offset k1 such that during the decompression H.nzval[k] = H[i,j] with

k = H.colptr[j] + k1

It will work for both options :F and :U.

If H[i,j] is in the lower triangular part (i > j) we could store the offset k2 such that during the decompression H.nzval[k] = H[i,j] with

k = H.colptr[j+1] - k2

It will work for both options :F and :L.

We can use the same strategy for diagonal coefficients.

[gdalle]

But those offsets depend on the column, right?

[amontoison]

Yes but we also need to store i and j to update stored_values so that's fine.