GitHub

ProjectedHypersurfaces.jl

This repository implements "numerical elimination" techniques for representing, and computing the complement of, real hypersurfaces that arise through projection of a known variety.

It is based on the paper Elimination Without Eliminating: Computing Complements of Real Hypersurfaces Using Pseudo-Witness Sets by Paul Breiding, John Cobb, Aviva Englander, Nayda Farnsworth, Jon Hauenstein, Oskar Henriksson, David Johnson, Jordy Lopez Garcia, and Deepak Mundayur.

Projected hypersurfaces

ProjectedHypersurfaces.ProjectedHypersurface — Type
ProjectedHypersurface{TC} <: HC.AbstractSystem

A hypersurface $\mathcal{H}$ in $\mathbb{C}^k$ that arises through projection of $(k-1)$-dimensional variety in a higher-dimensional ambient space.

The hypersurface $\mathcal{H}$ is represented by a pseudowitness set.

source
ProjectedHypersurfaces.trace_test — Method
trace_test(h::ProjectedHypersurface)

Performs a trace test to vertify completeness of the underlying pseduo-witness set and therefore correctness of the degree. A value close to zero (e.g., in the order to 1e-16) indicates that the pseudo-witness set is likely complete.

See trace_test(::PseudoWitnessSet) for details.

source

Pseudo-witness sets

ProjectedHypersurfaces.PseudoWitnessSet — Method
PseudoWitnessSet(F::System, k::Int; linear_subspace_codim::Int, L::LinearSubspace)

Generates a pseudo witness set for the image of the variety $V(F)\subseteq\mathbb{C}^n$ for a system $F\in\mathbb{C}[x_1,\ldots,x_n]^r$ under the projection $\pi\colon\mathbb{C}^k\times\mathbb{C}^{n-k}\to\mathbb{C}^k$.

Optional inputs:

  • linear_subspace_codim: The codimension of the linear space used for the witness set. Defaults to n - length(F).
  • L: The linear space used for the witness set. Should be the preimage under $\pi$ of a linear subspace in $\mathbb{C}^k$.
  • filter_condition: A function that takes a point in $\mathbb{C}^{n}$ and returns a boolean. If provided, only points

in the pseudo-witness set that satisfy this condition will be included. Can be used to filter out irrelevant irreducible components.

source
ProjectedHypersurfaces.decompose — Method
decompose(PWS::PseudoWitnessSet)

Performs a numerical irreducible decomposition of the upstairs variety of a pseudo-witness set PWS and returns a vector of pseudo-witness sets (one for each irreducible component).

If several upstairs components have the same downstairs projection, only one of these components will be used.

source
ProjectedHypersurfaces.trace_test — Method
trace_test(PWS::PseudoWitnessSet)

Performs a trace test for completness of a pseudo-witness set; see [LRS18] for details.

Returns a trace, which theoretically should be zero if and only if the pseudo-witness set is complete (has all the witness points, meaning that we have correctly computed the degree of the variety).

Since we are working with floating point arithmetic, it will likely not be exactly zero. A very low trace (e.g. on the order of 1e-16) is a strong heutistic indication that the pseudo-witness set is complete, but does not constitute a proof.

[LRS18] Leykin, Anton, Jose Israel Rodriguez, and Frank Sottile. "Trace test." Arnold Mathematical Journal 4.1 (2018): 113-125.

source
ProjectedHypersurfaces.track! — Method
track!(u::Vector{Vector{ComplexF64}}, PWS::PseudoWitnessSet, p::AbstractVector)

Given a pseudo-witness set PWS and a point p in the downstairs space, move the line downstains so that it passes through p and track the pseudo-witness points.

The resulting points are stored in u and the success of each track is recorded in PWS.track_report.

source

Interpolation

ProjectedHypersurfaces.interpolate — Method
interpolate(
    h::ProjectedHypersurface;
    tol::Float64=1e-8,
    oversampling_factor=1.5
)

Interpolate the projected hypersurface h to obtain a polynomial representation of the discriminant. The interpolation is performed by sampling points on the hypersurface via sample_points and finding an element of the nullspace of the Vandermonde matrix via singular value decomposition. The resulting polynomial is normalized to have integer coefficients with the smallest possible common denominator.

The output is an InterpolationResult object containing the polynomial. It also includes some numbers that quantify the quality of the interpolation:

  • σ_min: The smallest singular value of the Vandermonde matrix (should be small if the interpolation is successful).
  • σ_gap: The ratio of the next-smallest singular value to the smallest singular value (should be large if the interpolation is successful).
  • residual: The residual of the interpolation, computed as the norm of the Vandermonde matrix times the coefficients divided by the norm of the coefficients (should be small if the interpolation is successful).

Input:

Keyword arguments:

  • tol: The tolerance for rationalizing the coefficients.
  • oversampling_factor: The factor by which to oversample the points.
source

Routing functions and gradient roadmaps

ProjectedHypersurfaces.RoutingFunction — Method
RoutingFunction(
    H::Vector{ProjectedHypersurface};
    e::Union{Int,Nothing} = nothing,
    c::Union{Vector,Nothing} = nothing,
    g::Union{Vector{Expression},Vector{Variable},Nothing} = nothing,
)

Construct a routing function for a collection of projected hypersurfaces H. The routing function is defined as $r(x) = \frac{\prod_{h \in H} h(x) \prod_{g \in G} g(x)}{(1 + \|x - c\|^2)^e}$ where $G$ is a collection of additional polynomials and $c$ is a vector in the ambient space. The denominator exponent e is automatically set so that the denominator has higher degree than the numerator.

Input arguments:

Keyword arguments:

  • e: The exponent of the denominator. If not provided, it is automatically set to be greater than the degree of the numerator.
  • c: A vector in the ambient space. If not provided, it is randomly generated
  • g: A vector of additional polynomials to include in the numerator.
source
ProjectedHypersurfaces.Region — Type
Region

A single region of a RoutingFunction r, i.e. one connected component of critical points as computed by gradient_roadmap. Modelled after the Region struct in HypersurfaceRegions.jl.

A Region bundles the routing points lying in the region together with their Morse indices, the Euler characteristic of the region, and a region number. The routing points are the real critical points of r (a subset of its complex critical points). The routing function r is stored so that a point in the parameter space can be flowed to a routing point in a membership test.

Fields

  • routing_points::Vector{Vector{Float64}}: the routing points in the region.
  • routing_point_indices::Vector{Int}: the position of each routing point in the list of routing points the region was computed from.
  • morse_indices::Vector{Int}: the Morse index of each routing point.
  • χ::Int: the Euler characteristic of the region, ∑ᵢ (-1)^μᵢ.
  • r::RoutingFunction: the routing function whose routing points these are.
  • region_number::Int: the index of this region within the roadmap.

See also routing_points, routing_point_indices, morse_indices, euler_characteristic and number.

source
ProjectedHypersurfaces.Region — Method
Region(routing_points, morse_indices, r::RoutingFunction, region_number;
       routing_point_indices = 1:length(routing_points))

Construct a Region from its routing points and their Morse indices, computing the Euler characteristic χ = ∑ᵢ (-1)^μᵢ automatically.

routing_point_indices records where each routing point sits in the list of routing points the region was carved out of; it defaults to 1:n, which is the right answer when the region is built directly from a standalone list of points.

source
ProjectedHypersurfaces.gradient_roadmap — Function
gradient_roadmap(
    r::RoutingFunction,
    crit_pts::AbstractVector{<:AbstractVector{<:Real}},
    epsilon::Float64 = 1e-6,
    reltol::Float64 = 1e-6,
    abstol::Float64 = 1e-9,
)

Partition a collection crit_pts of critical points of a routing function r into connected components via gradient flow. The function returns a GradientRoadmap containing the connected components, Morse indices, and any failed connection attempts.

source
ProjectedHypersurfaces.membership — Method
membership(regions::Vector{Region}, p; reltol = 1e-6, abstol = 1e-9)
membership(R::GradientRoadmap, p; reltol = 1e-6, abstol = 1e-9)

Determine which Region a point p in the parameter space belongs to.

The point p is flowed by gradient ascent of the routing function until it reaches a routing point; the region whose routing points contain that limit is returned. All regions in regions are assumed to come from the same roadmap, i.e. to share a common routing function (the one stored on the first region).

Returns nothing if regions is empty or if the gradient flow does not converge to one of the known routing points.

Options:

  • reltol = 1e-6, abstol = 1e-9: parameters for the accuracy of the ODE solver.
source
ProjectedHypersurfaces.morse_indices — Method
morse_indices(result::GradientRoadmap)

Return the Morse index computed for each routing point, or nothing if the roadmap failed before indices were available.

source
ProjectedHypersurfaces.partition — Method
partition(R::GradientRoadmap)

Return the partition of the indices of the routing points induced by the regions.

The ordering of the blocks of the partition is the same as the ordering of the regions in the output of regions.

source
ProjectedHypersurfaces.regions — Method
regions(R::GradientRoadmap)

Return the connected components of R as a vector of Region objects.

Each region carries the coordinates of its routing points, their Morse indices, the Euler characteristic, and the routing function, so the returned vector is self-contained and can be passed directly to membership.

source
ProjectedHypersurfaces.return_code — Method
return_code(R::GradientRoadmap)

Return a symbolic status code for a gradient roadmap. It can take two values:

  • :success if all connection attempts succeeded
  • :partial_success if some connection attempts failed
source