Failure to parse local Jacobian sparsity pattern

[adrhill]

Reopening from JuliaDiff/DifferentiationInterface.jl#641:

using DifferentiationInterface, SparseConnectivityTracer, SparseMatrixColorings
dense_first_order_backend = AutoForwardDiff()
sparse_first_order_backend = AutoSparse(
    dense_first_order_backend;
    sparsity_detector=SparseConnectivityTracer.TracerLocalSparsityDetector(),
    coloring_algorithm=GreedyColoringAlgorithm(LargestFirst()),
)
function f_sparse_vector(x::AbstractVector)
	n = length(x)
    ret = []
    for i in 1:n-1
        append!(ret, abs2(x[i + 1]) - abs2(x[i]) + abs2(x[n - i]) - abs2(x[n - i + 1]))
    end
    return ret
end
xbig = rand(1000)
jac_prep_sparse_nonallocating = prepare_jacobian(f_sparse_vector, sparse_first_order_backend, zero(xbig))

fails with the stack trace

ERROR: MethodError: no method matching jacobian_pattern_to_mat(::Vector{SparseConnectivityTracer.Dual{Float64, SparseConnectivityTracer.GradientTracer{…}}}, ::Vector{Any})

Closest candidates are:
  jacobian_pattern_to_mat(::AbstractArray{D}, ::AbstractArray{<:Real}) where {P, T<:SparseConnectivityTracer.GradientTracer, D<:SparseConnectivityTracer.Dual{P, T}}
   @ SparseConnectivityTracer ~/.julia/packages/SparseConnectivityTracer/4CmIb/src/trace_functions.jl:122

Stacktrace:
 [1] _local_jacobian_sparsity(f::Function, x::Vector{Float64}, ::Type{SparseConnectivityTracer.GradientTracer{SparseConnectivityTracer.IndexSetGradientPattern{Int64, BitSet}}})
   @ SparseConnectivityTracer ~/.julia/packages/SparseConnectivityTracer/4CmIb/src/trace_functions.jl:91
 [2] jacobian_sparsity(f::Function, x::Vector{Float64}, ::TracerLocalSparsityDetector{SparseConnectivityTracer.GradientTracer{…}, SparseConnectivityTracer.HessianTracer{…}})
   @ SparseConnectivityTracer ~/.julia/packages/SparseConnectivityTracer/4CmIb/src/adtypes_interface.jl:149
 [3] _prepare_sparse_jacobian_aux(::DifferentiationInterface.PushforwardFast, ::Vector{…}, ::Tuple{…}, ::AutoSparse{…}, ::Vector{…})
   @ DifferentiationInterfaceSparseMatrixColoringsExt ~/.julia/packages/DifferentiationInterface/gSdHF/ext/DifferentiationInterfaceSparseMatrixColoringsExt/jacobian.jl:61
 [4] prepare_jacobian(::typeof(f_sparse_vector), ::AutoSparse{AutoForwardDiff{…}, TracerLocalSparsityDetector{…}, GreedyColoringAlgorithm{…}}, ::Vector{Float64})
   @ DifferentiationInterfaceSparseMatrixColoringsExt ~/.julia/packages/DifferentiationInterface/gSdHF/ext/DifferentiationInterfaceSparseMatrixColoringsExt/jacobian.jl:41
 [5] top-level scope
   @ REPL[19]:1
Some type information was truncated. Use `show(err)` to see complete types.

[adrhill]

Shorter MWE:

julia> using SparseConnectivityTracer

julia> function f(x::AbstractVector)
               n = length(x)
           ret = []
           for i in 1:n-1
               append!(ret, abs2(x[i + 1]) - abs2(x[i]) + abs2(x[n - i]) - abs2(x[n - i + 1]))
           end
           return ret
       end
f (generic function with 1 method)

julia> x = randn(10);

julia> jacobian_sparsity(f, x, TracerLocalSparsityDetector())
ERROR: MethodError: no method matching jacobian_pattern_to_mat(::Vector{SparseConnectivityTracer.Dual{Float64, SparseConnectivityTracer.GradientTracer{…}}}, ::Vector{Any})
The function `jacobian_pattern_to_mat` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  jacobian_pattern_to_mat(::AbstractArray{D}, ::AbstractArray{<:Real}) where {P, T<:SparseConnectivityTracer.GradientTracer, D<:SparseConnectivityTracer.Dual{P, T}}
   @ SparseConnectivityTracer ~/Developer/SparseConnectivityTracer.jl/src/trace_functions.jl:122
  jacobian_pattern_to_mat(::AbstractArray{T}, ::AbstractArray{<:Real}) where T<:SparseConnectivityTracer.GradientTracer
   @ SparseConnectivityTracer ~/Developer/SparseConnectivityTracer.jl/src/trace_functions.jl:103

Stacktrace:
 [1] _local_jacobian_sparsity(f::Function, x::Vector{Float64}, ::Type{SparseConnectivityTracer.GradientTracer{SparseConnectivityTracer.IndexSetGradientPattern{Int64, BitSet}}})
   @ SparseConnectivityTracer ~/Developer/SparseConnectivityTracer.jl/src/trace_functions.jl:91
 [2] jacobian_sparsity(f::Function, x::Vector{Float64}, ::TracerLocalSparsityDetector{SparseConnectivityTracer.GradientTracer{…}, SparseConnectivityTracer.HessianTracer{…}})
   @ SparseConnectivityTracer ~/Developer/SparseConnectivityTracer.jl/src/adtypes_interface.jl:149
 [3] top-level scope
   @ REPL[15]:1
Some type information was truncated. Use `show(err)` to see complete types.

[adrhill]

Looks like this was just an issue of SCT's type annotations being too strict.
We expected AbstractArray{<:Real}, but ret is a Vector{Any}.

[ErikQQY]

Looks like this was just an issue of SCT's type annotations being too strict.
We expected AbstractArray{<:Real}, but ret is a Vector{Any}.

Yeah, the reason causing this error is the type yt being too strict in these functions, I actually encountered this issue when I was doing the refactoring in SciML/BoundaryValueDiffEq.jl#258. I locally changed the annotation of yt into more generic ones and the errors are gone.

SparseConnectivityTracer.jl/src/trace_functions.jl

Lines 103 to 126 in e6d357b

	function jacobian_pattern_to_mat(
	xt::AbstractArray{T}, yt::AbstractArray{<:Real}
	) where {T<:GradientTracer}
	n, m = length(xt), length(yt)
	I = Int[] # row indices
	J = Int[] # column indices
	V = Bool[] # values
	for (i, y) in enumerate(yt)
	if y isa T && !isemptytracer(y)
	for j in gradient(y)
	push!(I, i)
	push!(J, j)
	push!(V, true)
	end
	end
	end
	return sparse(I, J, V, m, n)
	end
	function jacobian_pattern_to_mat(
	xt::AbstractArray{D}, yt::AbstractArray{<:Real}
	) where {P,T<:GradientTracer,D<:Dual{P,T}}
	return jacobian_pattern_to_mat(tracer.(xt), _tracer_or_number.(yt))
	end

[adrhill]

Fixed in SCT v0.6.9.