# Solving parametrized systems with monodromy

Next to `solve`

, HomotopyContinuation.jl provides the function `monodromy_solve`

which uses the monodromy method to solve a parameterized system of polynomials. Often `monodromy_solve`

allows to still compute all isolated solutions of system where the number of paths tracked in `solve`

](@ref) is already infeasible. Make sure to check out our monodromy guide for a more in depth introduction into this method.

`HomotopyContinuation.monodromy_solve`

— Function`monodromy_solve(F, [sols, p]; options..., tracker_options = TrackerOptions())`

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`

.

```
monodromy_solve(F, [sols, L]; dim, codim, intrinsic = nothing, options...,
tracker_options = TrackerOptions())
```

Solve the polynomial system `[F(x); L(x)] = 0`

where `L`

is a `[LinearSubspace`

](@ref). If `sols`

and `L`

are not provided it is necesary to provide `dim`

or `codim`

where `(co)dim`

is the expected (co)dimension of a component of `V(F)`

. See also `linear_subspace_homotopy`

for the `intrinsic`

option.

**Options**

`catch_interrupt = true`

: If true catches interruptions (e.g. issued by pressing Ctrl-C) and returns the partial result.`check_startsolutions = true`

: If`true`

, we do a Newton step for each entry of`sols`

for checking if it is a valid startsolutions. Solutions which are not valid are sorted out.`compile = mixed`

: If`true`

then a`System`

(resp.`Homotopy`

) is compiled to a straight line program (`CompiledSystem`

resp.`CompiledHomotopy`

) for evaluation. This induces a compilation overhead. If`false`

then the generated program is only interpreted (`InterpretedSystem`

resp.`InterpretedHomotopy`

). This is slower than the compiled version, but does not introduce compilation overhead.`distance = EuclideanNorm()`

: The distance function used for`UniquePoints`

.`loop_finished_callback = always_false`

: A callback to end the computation. This function is called with all current`PathResult`

s after a loop is exhausted. 2 arguments. Return`true`

if the compuation should be stopped.`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.`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 = 5`

: 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 no lower limit is enforced.`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 Normal distribution.`permutations = false`

: Whether to keep track of the permutations induced by the loops.`resuse_loops = :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.`target_solutions_count`

: The computation is stopped if this number of solutions is reached.`threading = true`

: Enable multithreading of the path tracking.`timeout`

: The maximal number of*seconds*the computation is allowed to run.`trace_test = true`

: If`true`

a trace test is performed to check whether all solutions are found. This is only applicable if monodromy is performed with a linear subspace. See also`trace_test`

.`trace_test_tol = 1e-10`

: The tolerance for the trace test to be successfull. The trace is divided by the number of solutions before compared to the trace*test*tol.`unique_points_rtol`

: the relative tolerance for`unique_points`

.`unique_points_atol`

: the absolute tolerance for`unique_points`

.

`HomotopyContinuation.MonodromyOptions`

— Type`MonodromyOptions(; options...)`

Options for `monodromy_solve`

.

`HomotopyContinuation.find_start_pair`

— Function`find_start_pair(F; max_tries = 100, atol = 0.0, rtol = 1e-12)`

Try to find a pair `(x,p)`

for the system `F`

such that `F(x,p) = 0`

by randomly sampling a pair `(x₀, p₀)`

and performing Newton's method in variable *and* parameter space.

It is also possible to verify (but not certify) that all solutions were found. Note that this computation can take substantially longer than the original `monodromy_solve`

computation.

`HomotopyContinuation.verify_solution_completeness`

— Function```
verify_solution_completeness(F::System, monodromy_result; options...)
verify_solution_completeness(F::System, solutions, parameters;
trace_tol = 1e-14,
show_progress = true,
compile = COMPILE_DEFAULT[],
monodromy_options = (compile = compile,),
parameter_homotopy_options = (compile = compile,),
)
```

Verify that a monodromy computation found all solutions by `monodromy_solve`

. This uses the trace test described in ^{[dCR17]} and ^{[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.

**Example**

```
@var x y a b c;
f = x^2+y^2-1;
l = a*x+b*y+c;
sys = System([f, l]; parameters = [a, b, c]);
mres = monodromy_solve(sys, [-0.6-0.8im, -1.2+0.4im], [1,2,3]);
show(mres);
verify_solution_completeness(sys, mres)
```

```
MonodromyResult
==================================
• 2 solutions (0 real)
• return code → heuristic_stop
• 44 tracked paths
• seed → 367230
julia> verify_solution_completeness(sys, mres)
[ Info: Certify provided solutions...
[ Info: Got 2 dinstinct solutions.
[ Info: Compute additional witnesses for completeness...
┌ Info: MonodromyResult
│ ===============
│ • return_code → :heuristic_stop
│ • 4 solutions
│ • 28 tracked loops
└ • random_seed → 0x21e7406a
[ Info: Certify additional witnesses...
[ Info: Computed 2 additional witnesses
[ Info: Compute trace using two parameter homotopies...
[ Info: Norm of trace: 9.33238819760471e-17
true
```

## Monodromy Result

A call to `monodromy_solve`

returns a `MonodromyResult`

:

`HomotopyContinuation.MonodromyResult`

— Type`MonodromyResult`

The monodromy result contains the result of the `monodromy_solve`

computation.

`HomotopyContinuation.solutions`

— Method`solutions(result::MonodromyResult)`

Return all solutions.

`HomotopyContinuation.nsolutions`

— Method`nsolutions(result::MonodromyResult)`

Returns the number solutions of the `result`

.

`HomotopyContinuation.ModelKit.parameters`

— Method`parameters(result::MonodromyResult)`

Return the parameters corresponding to the given result `r`

.

`HomotopyContinuation.results`

— Method`results(result::MonodromyResult)`

Returns the computed `PathResult`

s.

`HomotopyContinuation.nresults`

— Method`nresults(result::MonodromyResult)`

Returns the number of results computed.

`HomotopyContinuation.is_success`

— Method`is_success(result::MonodromyResult)`

Returns true if the monodromy computation achieved its target solution count.

`HomotopyContinuation.is_heuristic_stop`

— Method`is_heuristic_stop(result::MonodromyResult)`

Returns true if the monodromy computation stopped due to the heuristic.

`HomotopyContinuation.seed`

— Method`seed(result::MonodromyResult)`

Return the random seed used for the computations.

`HomotopyContinuation.permutations`

— Method`permutations(r::MonodromyResult; reduced=true)`

Return the permutations of the solutions that are induced by tracking over the loops. If `reduced=false`

, then all permutations are returned. If `reduced=true`

then permutations without repetitions are returned.

If a solution was not tracked in the loop, then the corresponding entry is 0.

Example: monodromy loop for a varying line that intersects two circles.

```
using LinearAlgebra
@var x[1:2] a b c
c1 = (x - [2, 0]) ⋅ (x - [2, 0]) - 1
c2 = (x - [-2, 0]) ⋅ (x - [-2, 0]) - 1
F = [c1 * c2; a * x[1] + b * x[2] - c]
S = monodromy_solve(F, [[1, 0]], [1, 1, 1], parameters = [a, b, c], permutations = true)
permutations(S)
```

will return

```
2×2 Array{Int64,2}:
1 2
2 1
```

and `permutations(S, reduced = false)`

returns

```
2×12 Array{Int64,2}:
1 2 2 1 1 … 1 2 1 1 1
2 1 1 2 2 2 1 2 2 2
```

## Group actions

If there is a group acting on the solution set of the polynomial system this can provided with the `group_action`

keyword for single group actions or with the `group_actions`

keyword for compositions of group actions. These will be internally transformed into `GroupActions`

.

`HomotopyContinuation.GroupActions`

— Type`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

- f1 is applied on the original solution
`s`

- f2 is applied on
`s`

and the results of 1 - 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)
```

To help with the more common group actions we provide some helper functions:

`HomotopyContinuation.SymmetricGroup`

— Type`SymmetricGroup(n)`

Group action of the symmetric group S(n).