Numerical Homotopy Continuation for Polynomial Systems

This direction is split into other directions: numerical homotopy continuation. Its last version stays readable and citable here.

Version 1 of 141 papers49 conceptsfrozen 2026-10-04

Many fundamental problems in science and engineering—from reconstructing a 3D scene from camera images to finding the equilibrium of a power grid—boil down to solving systems of multivariate polynomial equations. While these systems look like simple extensions of high school algebra, they are notoriously difficult to solve. Traditional symbolic methods, such as Gröbner bases, often suffer from "memory explosion," where the computational resources required grow exponentially with the number of variables and the degree of the equations.

Numerical Algebraic Geometry (NAG) offers a powerful alternative. Instead of manipulating symbols, it uses Numerical Homotopy Continuation (HC) to "morph" a simple problem with known solutions into the complex target problem. This approach transforms a static algebraic puzzle into a dynamic path-tracking challenge, providing a robust, parallelizable, and globally optimal way to find all possible solutions.

The Intuition: Morphing Solutions

The core idea of homotopy continuation is to embed the problem you want to solve (the target system) into a continuous family of problems.

Imagine you have a target system $F(x) = 0$ that is too complex to solve directly. You start by constructing a start system $G(x) = 0$ that has the same structure (e.g., the same number of variables and degree) but is easy to solve. You then define a homotopy function: $$H(x, t) = (1 - t)G(x) + tF(x)$$ As the parameter $t$ moves from $0$ to $1$, the system $H(x, t)$ continuously deforms from the easy system $G(x)$ to your difficult target system $F(x)$. As Kathlén Kohn, Paul Breiding, and Bernd Sturmfels explain in Computations, we can track the known solutions of $G(x)$ along these paths as they evolve into the solutions of $F(x)$.

Path Tracking and Numerical Stability

To move along these paths, solvers use a combination of two numerical tools:

  1. ODE Solvers: The path $x(t)$ can be viewed as the solution to a differential equation. Predictor steps move the solution forward along the tangent of the path.
  2. Newton’s Method: Because numerical integration accumulates error, a corrector step (Newton’s method) is used at each interval to pull the solution back onto the "true" algebraic variety.

This dual approach allows researchers like Aayushya Agarwal and Lawrence T. Pileggi to solve highly nonlinear power flow equations that would otherwise diverge. By starting with a relaxed version of the network and incrementally increasing complexity, the solver stays within the "radius of convergence," ensuring a stable path to the final solution (Continuously Differentiable Analytical Models for Implicit Control within Power Flow).

Why It Scales: Parallelism and Linearity

The most significant advantage of Homotopy Continuation over symbolic methods is how it scales. In symbolic algebra, the complexity is often exponential. In contrast, the complexity of HC scales linearly with the number of solution paths.

Because each solution path is independent of the others, the process is "embarrassingly parallelizable." Dhagash Mehta and Jonathan D. Hauenstein demonstrated that this allows researchers to solve massive systems in string theory and particle physics by distributing millions of paths across computing clusters (Numerical algebraic geometry: a new perspective on gauge and string theories). More recently, Chiang-Heng Chien and Hongyi Fan showed that by mapping these paths to GPU warps, solvers can achieve 26x speedups, making it possible to solve complex 3D reconstruction problems in real-time (GPU-Based Homotopy Continuation for Minimal Problems in Computer Vision).

Algebraic Vision and Minimal Problems

In computer vision, "minimal problems" involve finding the smallest amount of data (e.g., the fewest points or lines) needed to estimate camera positions or scene geometry. These problems often result in high-degree polynomial systems. Joe Kileel and Kathlén Kohn describe this intersection as Algebraic Vision (Snapshot of Algebraic Vision).

For instance, estimating the relative pose of three cameras from lines and points can involve hundreds of potential solutions. Traditional solvers might get stuck in local minima or fail to find the physically correct solution. HC ensures that all potential solutions are tracked, allowing the algorithm to pick the one that best fits the noisy real-world data (TRPLP - Trifocal Relative Pose From Lines at Points).

Modern Frontiers: Learning and Integration

The latest research focuses on making HC even faster by reducing the number of paths tracked. Instead of tracking every possible mathematical root (many of which are "spurious" or complex-valued), researchers are using machine learning to predict which paths are likely to lead to real, physical solutions.

  • Pick & Solve: Petr Hruby and Tomáš Pajdla trained neural networks to predict a single promising starting point on the "problem-solution manifold," achieving 1000x speedups for 3D reconstruction (Learning to Solve Hard Minimal Problems).
  • Semialgebraic Neural Networks: S. David Mis and colleagues have even embedded HC directly into neural network architectures. By solving an internal ODE to track roots, these networks can exactly represent complex mathematical operations that standard ReLU networks can only approximate (Semialgebraic Neural Networks: From roots to representations).

By bridging the gap between abstract algebraic geometry and high-performance numerical computing, Homotopy Continuation has evolved from a theoretical tool into a practical engine for solving the world's most complex non-linear systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_numerical_homotopy_continuation_for_poly_aec9674a,
  title = {Numerical Homotopy Continuation for Polynomial Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/numerical-homotopy-continuation-for-polynomial-systems/rdr_aec9674a8aff419e8bf5cd8a5f9f1890},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_numerical_homotopy_continuation_for_poly_aec9674a_v1,
  title = {Numerical Homotopy Continuation for Polynomial Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/numerical-homotopy-continuation-for-polynomial-systems/rdr_aec9674a8aff419e8bf5cd8a5f9f1890/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}