GitHub

Polynomial System Solvers

Globtim uses polynomial system solvers to find critical points by solving ∇p(x) = 0. This guide covers the available solvers and how to choose between them.

Available Solvers

HomotopyContinuation.jl (Default)

State of the art numerical algebraic geometry method.

Website: https://www.juliahomotopycontinuation.org/

solutions = solve_polynomial_system(
    x, n_dims, degree, coeffs,
    solver="HC"  # Default
)

msolve

State of the art symbolic (exact) method, relies on Gröbner basis computations.

Website: https://msolve.lip6.fr/

solutions = solve_polynomial_system(
    x, n_dims, degree, coeffs,
    solver="msolve",
    msolve_path="/path/to/msolve"
)

Note: Requires external installation (see below).

Installing Msolve

  1. Download from: https://msolve.lip6.fr/
  2. Build according to platform instructions
  3. Add to PATH or specify path in function call

macOS/Linux

git clone https://github.com/algebraic-solving/msolve.git
cd msolve
./autogen.sh
./configure
make
sudo make install

Verification

msolve --help

Solver Selection Guidelines

Use HomotopyContinuation when:

  • Working with smooth, well-conditioned problems
  • Need fast solutions for exploration
  • Dealing with higher dimensions (>4)
  • Numerical accuracy is sufficient

Use Msolve when:

  • Need exact verification of results
  • Working with rational coefficients
  • Dealing with degenerate or near-singular systems
  • Publishing results requiring certainty

Example Comparison

using Globtim, DynamicPolynomials

# Setup problem
f = Deuflhard
TR = test_input(f, dim=2, center=[0,0], sample_range=1.2)
pol = Constructor(TR, 8)

@polyvar x[1:2]

# HomotopyContinuation (numerical)
@time solutions_hc = solve_polynomial_system(
    x, 2, 8, pol.coeffs,
    solver="HC"
)

# msolve (symbolic/exact)
@time solutions_ms = solve_polynomial_system(
    x, 2, 8, pol.coeffs,
    solver="msolve"
)

# Compare results
println("HC found $(length(solutions_hc)) solutions")
println("Msolve found $(length(solutions_ms)) solutions")

Advanced Options

HomotopyContinuation Parameters

Control solver behavior:

solutions = solve_polynomial_system(
    x, n_dims, degree, coeffs,
    solver="HC",
    hc_options=Dict(
        :compile => false,      # Disable compilation for small problems
        :threading => true,     # Enable parallel tracking
        :tracker_options => TrackerOptions(
            automatic_differentiation=2,  # AD order
            refinement_accuracy=1e-12    # Target accuracy
        )
    )
)

Msolve Parameters

Fine-tune exact solving:

solutions = solve_polynomial_system(
    x, n_dims, degree, coeffs,
    solver="msolve",
    msolve_options=Dict(
        :precision => 128,      # Bit precision for intermediate computations
        :threads => 4,          # Number of threads
        :output_format => "qq"  # Rational output format
    )
)

Handling Solver Results

Both solvers return solutions in a common format:

# Process solutions
df = process_crit_pts(solutions, f, TR, solver=solver_name)

# Check solution quality
for sol in solutions
    grad_norm = norm(gradient(pol.polynomial, sol))
    println("Solution: $sol, |∇p|: $grad_norm")
end