Homotopy Graph

Monodromy tracking uses a graph of parameter points. A Vertex stores a parameter value and the solutions currently known over that value. An Edge stores the correspondences found by tracking paths between two vertices.

The high-level solver can build a complete graph automatically, so most examples do not need to construct edges by hand. Build explicit edges only when you want to track a chosen graph.

Vertices And Edges

julia> CC = AcbField(256);
julia> v1 = vertex([CC(1), CC(-1)], [[CC(1), CC(1)]])Vertex(1 solutions)
julia> v2 = vertex([CC(cis(0.2)), CC(cis(0.3))])Vertex(0 solutions)
julia> e = edge(v1, v2)Edge(0 correspondences)
julia> e.correspondence12Tuple{Int64, Int64}[]

Custom Graph

Pass an explicit edge list to solve_monodromy when the complete graph is not the graph you want to track. The following example builds a cyclic graph on six vertices.

julia> @variables x y p q;
julia> CC = AcbField(256);
julia> F = [p*x^2 + 3y - 4, y^2 + q];
julia> compiled = compile_edge_homotopy(F, [x, y], [p, q]);Compilation Done.
julia> v1 = vertex([CC(1), CC(-1)], [[CC(1), CC(1)]]);
julia> vertices = [v1; [vertex([CC(cis(0.2k)), CC(cis(0.3k))]) for k in 1:5]];
julia> edges = build_edges(vertices, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)]);
julia> length(edges)6

result = solve_monodromy(compiled, vertices, edges; max_roots=4)
length(result.edges)

CertifiedHomotopyTracking.Vertex — Type

Vertex

Node of a monodromy graph.

Fields:

base_point: parameter value attached to the vertex.
solutions: known solutions over base_point.
Edges: incident graph edges.

Construct vertices with vertex.

source

CertifiedHomotopyTracking.Edge — Type

Edge

Undirected monodromy graph edge with tracked correspondences in both directions.

Fields:

node1, node2: endpoint vertices.
correspondence12: pairs (i, j) mapping solution i at node1 to solution j at node2.
correspondence21: reverse correspondences.

Construct edges with edge or build_edges.

source

CertifiedHomotopyTracking.vertex — Function

vertex(p)
vertex(p, solutions)

Create a monodromy graph vertex at parameter point p.

Use vertex(p, [x0]) when one or more start solutions are already known.

source

CertifiedHomotopyTracking.edge — Function

edge(v, w)

Create an empty monodromy graph edge between vertices v and w.

source

CertifiedHomotopyTracking.build_edges — Function

build_edges(vertices, edge_pairs) -> Vector{Edge}

Create graph edges from pairs of vertex indices and register each edge with its endpoint vertices.

Example

CC = AcbField(128);
vertices = [vertex([CC(i)]) for i in 1:3];
edges = build_edges(vertices, [(1, 2), (2, 3), (3, 1)])
length(edges)

source