search

JuliaHomotopyContinuation / HomotopyContinuation.jl

A Julia package for solving systems of polynomials via homotopy continuation.
https://www.JuliaHomotopyContinuation.org
MIT License
178 stars 30 forks source link

cache_min_length failing with empty iterator #522

Open blegat opened 1 year ago

blegat commented 1 year ago

Found this while working on https://github.com/jump-dev/PolyJuMP.jl/pull/80

julia> using DynamicPolynomials

julia> @polyvar x[1:5]
(PolyVar{true}[x₁, x₂, x₃, x₄, x₅],)

julia> p = differentiate(sum(x), x)
5-element Vector{Polynomial{true, Int64}}:
 1
 1
 1
 1
 1

julia> using HomotopyContinuation

julia> s = System(p)
System of length 5
 5 variables: x₁, x₂, x₃, x₄, x₅

 1
 1
 1
 1
 1

julia> solve(s)
ERROR: MethodError: reducing over an empty collection is not allowed; consider supplying `init` to the reducer
Stacktrace:
  [1] reduce_empty(op::Base.MappingRF{HomotopyContinuation.ModelKit.var"#197#198", typeof(max)}, #unused#::Type{HomotopyContinuation.ModelKit.InterpreterInstruction})
    @ Base ./reduce.jl:356
  [2] reduce_empty_iter
    @ ./reduce.jl:379 [inlined]
  [3] mapreduce_empty_iter(f::Function, op::Function, itr::Vector{HomotopyContinuation.ModelKit.InterpreterInstruction}, ItrEltype::Base.HasEltype)
    @ Base ./reduce.jl:375
  [4] _mapreduce
    @ ./reduce.jl:427 [inlined]
  [5] _mapreduce_dim
    @ ./reducedim.jl:365 [inlined]
  [6] #mapreduce#765
    @ ./reducedim.jl:357 [inlined]
  [7] mapreduce
    @ ./reducedim.jl:357 [inlined]
  [8] #_maximum#783
    @ ./reducedim.jl:999 [inlined]
  [9] _maximum
    @ ./reducedim.jl:999 [inlined]
 [10] #maximum#781
    @ ./reducedim.jl:995 [inlined]
 [11] maximum
    @ ./reducedim.jl:995 [inlined]
 [12] cache_min_length
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/model_kit/slp_interpreter.jl:77 [inlined]
 [13] InterpretedSystem(F::System; optimizations::Bool)
    @ HomotopyContinuation.ModelKit ~/.julia/packages/HomotopyContinuation/I1faM/src/model_kit/interpreted_system_homotopy.jl:37
 [14] InterpretedSystem
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/model_kit/interpreted_system_homotopy.jl:33 [inlined]
 [15] MixedSystem(F::System; kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/systems/mixed_system.jl:13
 [16] MixedSystem
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/systems/mixed_system.jl:13 [inlined]
 [17] #fixed#79
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/systems.jl:23 [inlined]
 [18] on_affine_chart(F::System, dims::Nothing; compile::Symbol, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/systems/affine_chart_system.jl:30
 [19] polyhedral(f::System; compile::Symbol, target_parameters::Nothing, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/polyhedral.jl:182
 [20] solver_startsolutions(F::System, starts::Nothing; seed::UInt32, start_system::Symbol, generic_parameters::Nothing, p₁::Nothing, start_parameters::Nothing, p₀::Nothing, target_parameters::Nothing, compile::Symbol, start_subspace::Nothing, target_subspace::Nothing, intrinsic::Nothing, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:160
 [21] solver_startsolutions (repeats 2 times)
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:115 [inlined]
 [22] solve(args::System; show_progress::Bool, threading::Bool, catch_interrupt::Bool, target_parameters::Nothing, stop_early_cb::Function, transform_result::Nothing, transform_parameters::typeof(identity), flatten::Nothing, target_subspaces::Nothing, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:472
 [23] solve(args::System)
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:432
 [24] top-level scope
    @ REPL[15]:1

The bug can be reduced to the following

julia> solve(System([differentiate(x, x)]))
ERROR: MethodError: reducing over an empty collection is not allowed; consider supplying `init` to the reducer
Stacktrace:
  [1] reduce_empty(op::Base.MappingRF{HomotopyContinuation.ModelKit.var"#197#198", typeof(max)}, #unused#::Type{HomotopyContinuation.ModelKit.InterpreterInstruction})
    @ Base ./reduce.jl:356
  [2] reduce_empty_iter
    @ ./reduce.jl:379 [inlined]
  [3] mapreduce_empty_iter(f::Function, op::Function, itr::Vector{HomotopyContinuation.ModelKit.InterpreterInstruction}, ItrEltype::Base.HasEltype)
    @ Base ./reduce.jl:375
  [4] _mapreduce
    @ ./reduce.jl:427 [inlined]
  [5] _mapreduce_dim
    @ ./reducedim.jl:365 [inlined]
  [6] #mapreduce#765
    @ ./reducedim.jl:357 [inlined]
  [7] mapreduce
    @ ./reducedim.jl:357 [inlined]
  [8] #_maximum#783
    @ ./reducedim.jl:999 [inlined]
  [9] _maximum
    @ ./reducedim.jl:999 [inlined]
 [10] #maximum#781
    @ ./reducedim.jl:995 [inlined]
 [11] maximum
    @ ./reducedim.jl:995 [inlined]
 [12] cache_min_length
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/model_kit/slp_interpreter.jl:77 [inlined]
 [13] InterpretedSystem(F::System; optimizations::Bool)
    @ HomotopyContinuation.ModelKit ~/.julia/packages/HomotopyContinuation/I1faM/src/model_kit/interpreted_system_homotopy.jl:37
 [14] InterpretedSystem
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/model_kit/interpreted_system_homotopy.jl:33 [inlined]
 [15] MixedSystem(F::System; kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/systems/mixed_system.jl:13
 [16] MixedSystem
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/systems/mixed_system.jl:13 [inlined]
 [17] #fixed#79
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/systems.jl:23 [inlined]
 [18] on_affine_chart(F::System, dims::Nothing; compile::Symbol, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/systems/affine_chart_system.jl:30
 [19] polyhedral(f::System; compile::Symbol, target_parameters::Nothing, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/polyhedral.jl:182
 [20] solver_startsolutions(F::System, starts::Nothing; seed::UInt32, start_system::Symbol, generic_parameters::Nothing, p₁::Nothing, start_parameters::Nothing, p₀::Nothing, target_parameters::Nothing, compile::Symbol, start_subspace::Nothing, target_subspace::Nothing, intrinsic::Nothing, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:160
 [21] solver_startsolutions (repeats 2 times)
    @ ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:115 [inlined]
 [22] solve(args::System; show_progress::Bool, threading::Bool, catch_interrupt::Bool, target_parameters::Nothing, stop_early_cb::Function, transform_result::Nothing, transform_parameters::typeof(identity), flatten::Nothing, target_subspaces::Nothing, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:472
 [23] solve(args::System)
    @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:432
 [24] top-level scope
    @ REPL[18]:1
PBrdng commented 1 year ago

Hi @blegat

first of all, sorry for the late reply!

What happens here is that the software is looking for a start system to solve $(1,\ldots,1)=0$. For this system, the start system will have zero solutions and therefore it tries to iterate over an empty collection. We should add a security check that catches these exceptions.