JuliaDiff / SparseDiffTools.jl

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

reduce time complexity of matrix2graph #107

Closed ghislainb closed 4 years ago

ghislainb commented 4 years ago

This uses an intermediate structure to arrange the indices of the columns of the matrix by rows and avoid the nested for-loops of complexity O(nnz^2).

Benchmark #93 on my local machine, old version :

julia> @time matrix2graph(jacsparsity, false)
447.022331 seconds (1.02 M allocations: 100.974 MiB, 0.01% gc time)

New version :

julia> @time matrix2graph(jacsparsity, false)
  0.158604 seconds (1.18 M allocations: 116.212 MiB, 24.89% gc time)

[my first Julia PR ! :smiley: ]

ChrisRackauckas commented 4 years ago

fantastic!