search

JuliaDiff / SparseDiffTools.jl

Fast jacobian computation through sparsity exploitation and matrix coloring
MIT License
237 stars 41 forks source link

Add fast path for forwarddiff_color_jacobian! with sparse J #146

Closed sjdaines closed 3 years ago

sjdaines commented 3 years ago

Partial fix for https://github.com/JuliaDiff/SparseDiffTools.jl/issues/138 https://github.com/JuliaDiff/SparseDiffTools.jl/issues/100

Add a fast path for the case where J and sparsity are are both SparseMatrixCSC and have the same sparsity pattern.

codecov-commenter commented 3 years ago

Codecov Report

Merging #146 (b968680) into master (e798411) will increase coverage by 0.05%. The diff coverage is 100.00%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master     #146      +/-   ##
==========================================
+ Coverage   83.05%   83.10%   +0.05%     
==========================================
  Files          12       12              
  Lines         667      669       +2     
==========================================
+ Hits          554      556       +2     
  Misses        113      113
Impacted Files Coverage Δ
src/differentiation/compute_jacobian_ad.jl 93.04% <100.00%> (+0.11%) :arrow_up:
src/coloring/high_level.jl 100.00% <0.00%> (ø)
src/coloring/matrix2graph.jl 100.00% <0.00%> (ø)

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update e798411...b968680. Read the comment docs.

sjdaines commented 3 years ago

OK done... now requires PR https://github.com/JuliaDiff/FiniteDiff.jl/pull/124 (however admit I don't fully understand how this could work and might be proliferating cut-and-paste cases instead of sane dispatches).

Now we have:

  1. add a _use_sparseCSC_common_sparsity!(J, sparsity) test function to FiniteDiff.iteration_utils.
  2. move the new _colorediteration!(Jsparsity::SparseMatrixCSC,vfx,colorvec,color_i,ncols) to FiniteDiff.iteration_utils
  3. FiniteDiff.finite_difference_jacobian! uses the same optimisation (although doesn't look like anyone has hit this problem there?)
ChrisRackauckas commented 3 years ago

Add a lower bound on 2.8.1