Solving parametrized systems with monodromy

monodromy_solve(F, [sols, p]; parameters=..., options..., pathtrackerkwargs...)

Solve a polynomial system F(x;p) with specified parameters and initial solutions sols by monodromy techniques. This makes loops in the parameter space of F to find new solutions. If F the parameters p only occur linearly in F it is eventually possible to compute a start pair $(x₀, p₀)$ automatically. In this case sols and p can be omitted and the automatically generated parameters can be obtained with the parameters function from the MonodromyResult.

Options

• check_startsolutions=true: If true, we do a Newton step for each entry of solsfor checking if it is a valid startsolutions. Solutions which are not valid are sorted out.
• distance_function=euclidean_distance: The distance function used for UniquePoints.
• done_callback=always_false: A callback to end the computation early. This function takes 2 arguments. The first one is the new solution x and the second one are all current solutions (including x). Return true if the compuation is done.
• equivalence_classes=true: This only applies if there is at least one group action supplied. We then consider two solutions in the same equivalence class if we can transform one to the other by the supplied group actions. We only track one solution per equivalence class.
• identical_tol::Float64=1e-6: The tolerance with which it is decided whether two solutions are identical.
• group_action=nothing: A function taking one solution and returning other solutions if there is a constructive way to obtain them, e.g. by symmetry.
• group_actions=nothing: If there is more than one group action you can use this to chain the application of them. For example if you have two group actions foo and bar you can set group_actions=[foo, bar]. See GroupActions for details regarding the application rules.
• max_loops_no_progress::Int=10: The maximal number of iterations (i.e. loops generated) without any progress.
• min_solutions: The minimal number of solutions before a stopping heuristic is applied. By default this is half of target_solutions_count if applicable otherwise 1.
• parameter_sampler=independent_normal: A function taking the parameter p and returning a new random parameter q. By default each entry of the parameter vector is drawn independently from the univariate normal distribution.
• resuse_loops::Symbol=:all: Strategy to reuse other loops for new found solutions. :all propagates a new solution through all other loops, :random picks a random loop, :none doesn't reuse a loop.
• show_progress=true: Enable a progress meter.
• strategy: The strategy used to create loops. If F only depends linearly on p this will be Petal. Otherwise this will be Triangle with weights if F is a real system.
• target_solutions_count=nothing: The computations are stopped if this number of solutions is reached.
• threading = true: Enable multithreading of the path tracking.
• timeout=float(typemax(Int)): The maximal number of seconds the computation is allowed to run.

MonodromyResult

The monodromy result contains the result of the monodromy_solve computation.

solutions(result::MonodromyResult; only_real=false, real_tol=1e-6)

Return all solutions (as SVectors) for which the given conditions apply.

Example

real_solutions = solutions(R, only_real=true)

parameters(r::MonodromyResult)

Return the parameters corresponding to the given result r.

verify_solution_completeness(F, res::MonodromyResult;
                             parameters=..., trace_tol=1e-6, options...)

Verify that the monodromy computation found all solutions by monodromy_solve. This uses a trace test as described in ^[LRS18]. The trace is a numerical value which is 0 if all solutions are found, for this the trace_tol keyword argument is used. The function returns nothing if some computation couldn't be carried out. Otherwise returns a boolean. Note that this function requires the computation of solutions to another polynomial system using monodromy. This routine can return false although all solutions are found if this additional solution set is not complete. The options... arguments can be everything which is accepted by solve and monodromy_solve.

Example

julia> @polyvar x y a b c;

julia> f = x^2+y^2-1;

julia> l = a*x+b*y+c;

julia> res = monodromy_solve([f,l], [-0.6-0.8im, -1.2+0.4im], [1,2,3]; parameters=[a,b,c])
MonodromyResult
==================================
• 2 solutions (0 real)
• return code → heuristic_stop
• 44 tracked paths
• seed → 367230

julia> verify_solution_completeness([f,l], res; parameters=[a,b,c], trace_tol = 1e-8)
[ Info: Compute additional witnesses for completeness...
[ Info: Found 2 additional witnesses
[ Info: Compute trace...
[ Info: Norm of trace: 1.035918995391323e-15
true

verify_solution_completeness(F, S, p; parameters=..., kwargs...)

Verify the solution completeness using the computed solutions S to the parameter p.

verify_solution_completeness(TTS, S, W₁₀, p₀::Vector{<:Number}, l₀)

Use the already computeded additional witnesses W₁₀. You want to obtain TTS, W₁₀ and l₀ as the output from solution_completeness_witnesses.

solution_completeness_witnesses(F, S, p; parameters=..., kwargs...)

Compute the additional necessary witnesses. Returns a triple (W₁₀, TTS, l) containing the additional witnesses W₁₀, a trace test system TTS and the parameters l for TTS.

GroupActions(actions::Function...)

Store a bunch of group actions (f1, f2, f3, ...). Each action has to return a tuple. The actions are applied in the following sense

1. f1 is applied on the original solution s
2. f2 is applied on s and the results of 1
3. f3 is applied on s and the results of 1) and 2)

and so on

Example

julia> f1(s) = (s * s,);

julia> f2(s) = (2s, -s, 5s);

julia> f3(s) = (s + 1,);

julia> GroupActions(f1)(3)
(3, 9)

julia> GroupActions(f1, f2)(3)
(3, 9, 6, -3, 15, 18, -9, 45)

julia> GroupActions(f1,f2, f3)(3)
(3, 9, 6, -3, 15, 18, -9, 45, 4, 10, 7, -2, 16, 19, -8, 46)

SymmetricGroup(n)

Group action of the symmetric group S(n).

Triangle(;useweights=true)

A triangle is a loop consisting of the main node and two addtional nodes. If weights is true the edges are equipped with additional random weights. Note that this is usually only necessary for real parameters.

Petal()

A petal is a loop consisting of the main node and one other node connected by two edges with different random weights.