JuliaDiff / ForwardDiff.jl

Forward Mode Automatic Differentiation for Julia
Other
893 stars 145 forks source link

Prohibit setindex! call if element of Jacobian is zero #452

Open MaximilianJHuber opened 4 years ago

MaximilianJHuber commented 4 years ago

I want to provide a sparse matrix to jacobian!, see this thread on Discourse.

However, setting zero-valued elements in a sparse matrix is expensive, because one needs to search if that element exists and has a non-zero value that is to be overwritten.

I propose that before the Jacobian/Hessian is filled, it is set to zero or emptied. Then setindex! is only called it the element is non-zero.

j-fu commented 4 years ago

I strongly support this.

However, I think the formulation in the second sentence needs a modification: Even if the sparse jacobian is empty, the searching on every zero insertion will happen as soon as there are some nonzero elements in a given column, so the proposed way appears to be not sufficient to me.

IMHO the matrix update should be performed only if the value to be set is nonzero, otherwise the matrix shouldn't be touched.

j-fu commented 4 years ago

Well, in light of this update I lower my priority suggestion from "strongly support" to "nice to have"... There are two kinds of zeros in jacobians: "random" ones like zero derivatives due to some extrema and "systemic" ones due to dependency patterns in the systems of equations. The later ones occur in finite difference and finite element operators and need to be handeled differenly, e.g. as suggested in SparseDiffTools.jl or using element-wise approaches as in VoronoiFVM.jl.