JuliaHomotopyContinuation / HomotopyContinuation.jl

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

OverflowError: Cannot compute a start system. #509

Closed freemin7 closed 2 years ago

freemin7 commented 2 years ago
ERROR: OverflowError: Cannot compute a start system.
Stacktrace:
 [1] compute_mixed_cells!(iter::PolyhedralStartSolutionsIterator)
   @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/polyhedral.jl:49
 [2] iterate(iter::PolyhedralStartSolutionsIterator)
   @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/polyhedral.jl:64
 [3] _collect(cont::UnitRange{Int64}, itr::PolyhedralStartSolutionsIterator, #unused#::Base.HasEltype, isz::Base.SizeUnknown)
   @ Base ./array.jl:660
 [4] collect
   @ ./array.jl:649 [inlined]
 [5] #solve#279
   @ ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:501 [inlined]
 [6] 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:487
 [7] solve(args::System)
   @ HomotopyContinuation ~/.julia/packages/HomotopyContinuation/I1faM/src/solve.jl:446
 [8] top-level scope
   @ REPL[12]:1

For this program:

using HomotopyContinuation

multis = 7;
n = 2;

z = zeros(Int,n,n,n,n,n,n);

for x1 in 1:n
for y1 in 1:n
for x2 in 1:n
for y2 in 1:n
z1 = zeros(Int,n,n)
z2 = zeros(Int,n,n)
z1[x1,y1]=1
z2[x2,y2]=1
z3 = z1*z2
for x3 in 1:n
for y3 in 1:n
if z3[x3,y3] == 1
z[x3,y3,x1,y1,x2,y2] = 1
end
end
end
end
end
end
end

@var a[1:n,1:n,1:multis] b[1:n,1:n,1:multis] w[1:n,1:n,1:multis]

eq = []

for c_row in 1:n
for c_col in 1:n
  for a_row in 1:n
  for a_col in 1:n
    for b_row in 1:n
    for b_col in 1:n

        push!(eq, -z[c_row,c_col,a_row,a_col,b_row,b_col] + sum(a[a_row,a_col,rounds]*b[b_row,b_col,rounds]*w[c_row,c_col,rounds] for rounds in 1:multis));

    end
    end
  end
  end
end
end

for i in 1:n
    for j in 1:n
        for rounds in 1:multis
            #push!(eq,a[i,j,rounds]^2 - a[i,j,rounds]^4)
            #push!(eq,b[i,j,rounds]^2 - b[i,j,rounds]^4)
            push!(eq,w[i,j,rounds]^2 - w[i,j,rounds]^4)
        end
    end
end

F = System(eq)
result = solve(F)
PBrdng commented 2 years ago

This can happen for the Polyhedral Start System (which is the default start system). The reason is that for the polyhedral start system one needs to compute a regular triangulation of some polytope, which uses integer arithmetic. If the polytopes are too complicated, this produces overflows.

Total Degree Homotopy is also not an option, because:

julia> paths_to_track(F, start_system = :total_degree)
6989586621679009792

You could try and see if monodromy works for your problem.

freemin7 commented 2 years ago

Is there some obvious procedure how i can express the symmetries (multiple group actions?) of the problem to cut down the number of paths to track for the polytope approach as i do not have an initial solution?

Finding an initial solution (in particular when the commented out constraints are removed and n and multis increased) might be really challenging.

PBrdng commented 2 years ago

In polyhedral and total degree start systems, no. They are general purpose methods and do not know symmetries.

In monodromy you can exploit group actions; see here.