🔢 mathematics

Computing singular solutions of polynomial systems: towards superlinear convergence without deflation

This paper introduces a new "Arclength Endgame" method for computing singular solutions of polynomial systems that achieves superlinear convergence using only function and Jacobian evaluations, alongside a heuristic extension for higher corank systems and an improved technique for estimating Puiseux series coefficients.

Original authors: Mikhail Karapetyants, Vladimir Kolmogorov, Jeferson Zapata

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mikhail Karapetyants, Vladimir Kolmogorov, Jeferson Zapata

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a hidden treasure (the solution to a math problem) by following a winding path on a map. In the world of "Numerical Algebraic Geometry," this path is created by a mathematical machine called a homotopy. You start at a known location (where the treasure is easy to find) and slowly walk along the path toward the unknown destination.

Usually, this walk is smooth. But sometimes, the path leads to a "singular" spot—a place where the ground gets weird, the map gets blurry, and the path seems to twist into a knot. This is the "Endgame." In these spots, standard walking methods (algorithms) start to stumble, slow down, or get lost entirely because the math behind them breaks down.

This paper introduces new, smarter ways to navigate these tricky "Endgame" knots without needing to carry a heavy, complicated toolkit (extra derivatives) that previous methods required.

Here is a breakdown of their three main innovations using everyday analogies:

1. The "Arclength Endgame" (For Simple Knots)

The Problem: When the path hits a simple knot (called a "corank-1" singularity), standard methods try to guess where the path is going by looking at the immediate slope. But near the knot, the slope changes so wildly that the guess is often wrong.

The New Solution: The authors invented a method called the Arclength Endgame.

The Analogy: Imagine you are walking toward a sharp bend in a road. A normal walker looks at the road right in front of their feet and guesses the direction. The new method is like a hiker who looks at the shape of the road ahead. They realize the road isn't just bending; it's spiraling in a specific, predictable pattern (like a corkscrew).
How it works: They use a technique called "Puiseux series" (a fancy way of describing these spiraling patterns). Instead of just guessing the next step, they estimate the entire spiral shape based on a few points they've already walked.
The Benefit: Because they understand the shape of the spiral, they can take much bigger, more confident steps toward the treasure. They prove mathematically that this method gets you to the solution super fast (superlinearly) without needing to calculate complex, heavy "extra derivatives" (like measuring the curvature of the road with a giant microscope). They only need to know the direction you are currently facing.

2. The "Lifted Arclength Endgame" (For Complex Knots)

The Problem: Some knots are so tangled (called "corank-2" or higher) that the simple spiral guess doesn't work. The path is too messy.

The New Solution: They propose a Lifted Arclength Endgame.

The Analogy: Imagine the path is stuck in a deep, muddy hole. You can't just walk out. So, you build a temporary bridge (adding new variables) to lift yourself out of the mud, walk across, and then drop back down on the other side.
How it works: They temporarily add "dummy" variables to the math problem to make it easier to solve, effectively "lifting" the solution out of the singularity. Once they find a better spot, they switch to a new map (a new homotopy) that starts from this better spot and leads them the rest of the way to the treasure.
The Benefit: While they haven't mathematically proven it works perfectly for every single case yet, their experiments show it works very well in practice, often finding the solution faster than old methods.

3. The "Better Compass" (Estimating the Spiral)

The Problem: To use the methods above, you need to know exactly how the path is spiraling. You need to know the "cycle number" (how many times it twists) and the "fractional exponents" (how fast it twists). Old methods were like using a compass that sometimes spun wildly or got stuck, especially when the path was sparse (twisting in weird, non-sequential ways).

The New Solution: They created a new, more stable way to read the compass.

The Analogy: Old methods tried to guess the twist by looking at two points and hoping for the best, or by trying every possible number until one fit (trial and error). The new method is like a smart sensor that looks at the pattern of the path more carefully.
How it works: They developed a new rule (called cRATIO) that compares the speed of the path at different points to figure out the twist. They also showed how to figure out not just the first twist, but the second and third twists in the sequence.
The Benefit: This new compass is more stable. It doesn't get confused by weird gaps in the path, and it gives a more accurate reading of the "twistiness" of the road, allowing the other methods (Arclength and Lifted) to work much better.

Summary

In short, the authors are saying: "When you get stuck in the messy, singular part of a math problem, stop trying to force your way through with heavy tools. Instead, look at the shape of the path, guess the spiral pattern using a smarter compass, and take a giant leap toward the solution."

They proved this works perfectly for simple knots and showed it works very well for complex ones, all while using less computational "fuel" (fewer complex calculations) than the old ways.

Technical Summary: Computing Singular Solutions of Polynomial Systems

Problem Statement

The paper addresses the numerical computation of isolated singular solutions to systems of polynomial equations $f(z) = 0$ within the framework of Numerical Algebraic Geometry (NAG). Standard approaches utilize homotopy continuation, tracking a solution curve $z(t)$ defined by $h(z(t), t) = 0$ from a known start system to the target system as $t \to 0$ .

The primary challenge arises in the "endgame" regime, where $t$ approaches zero and the solution $z^* = z(0)$ is singular (i.e., the Jacobian $f_z(z^*)$ is rank-deficient). In this region, standard Newton-based correctors fail due to the singularity of the Jacobian, and existing methods often struggle with convergence rates or require computationally expensive higher-order derivatives. The authors focus on systems where the solution is isolated and the homotopy satisfies specific transversality and regularity conditions (Assumption 1), ensuring the existence of a Puiseux series expansion for the solution curve.

Methodology

The proposed approach, termed the Arclength Endgame, combines pseudo-arclength continuation techniques with the estimation of Puiseux series parameters. The method is divided into two phases: a predictor phase and a corrector phase.

1. Predictor Phase

The goal is to estimate the leading terms of the Puiseux series $z(t) = z^* + \sum a_j t^{k_j/c}$ to predict the solution at $t=0$ (or a small $t$ ).

Estimation of Exponents: The authors introduce a new method, cRATIO, to estimate the leading fractional exponent ratio $k_1/c$ . This method utilizes the ratio of norms $\|t \dot{z}(t) - t_1 \dot{z}(t_1)\| / \|z(t) - z(t_1)\|$ , which converges to $k_1/c$ as $t \to 0$ . They compare this against existing methods like cSORT (trial-and-error) and cLOG (geometric sequence sampling), noting cRATIO's empirical stability.
Higher-Order Estimation: For systems requiring higher-order accuracy, the paper proposes a recursive method to estimate subsequent ratios $k_i/c$ (for $i \ge 2$ ) by applying the $k_1/c$ estimation logic to transformed functions derived from the original series.
Coefficient Estimation: The authors present a new scheme for estimating coefficients $a_{k_i}$ using a scaled Vandermonde matrix inversion. Unlike classical Hermite interpolation which assumes dense exponents $(1, 2, 3)$ , this method accommodates sparse exponents and utilizes higher-order derivatives (approximated via Hermite Finite Differences to avoid Hessian computation).

2. Corrector Phase

Once a predictor point $\hat{x}$ is estimated, the system is augmented to restore non-singularity for Newton's method.

Corank-1 ( $\kappa=1$ ): The system $h(x)=0$ is augmented with a single linear equation $q \cdot (x - \hat{x}) = 0$ , where $q$ is a vector orthogonal to the tangent of the solution curve (derived from the null space of the augmented Jacobian $[h_z, h_t]$ ). This creates a well-conditioned square system solvable by Newton's method.
Corank $\kappa \ge 2$ (Lifted Arclength Endgame): For higher corank, the method introduces $\kappa-1$ auxiliary variables and $\kappa$ hyperplanes to regularize the system. Since the resulting point may not lie on the original homotopy, the authors propose a "lifted" strategy: the homotopy is dynamically reset to a Newton homotopy $h_v(z, t) = f(z) - t f(v)$ , where $v$ is the refined solution. This allows the process to continue refining the solution near the singularity.

Key Contributions

Arclength Endgame for Corank-1: The authors introduce a new algorithm for corank-1 systems that achieves superlinear convergence in a neighborhood of the singular root. Crucially, this method relies only on evaluations of the system and its Jacobian, avoiding the computation of higher-order derivatives required by deflation-based methods with proven superlinear convergence.
Lifted Arclength Endgame: A heuristic extension for systems with corank $\kappa \ge 2$ . While formal convergence proofs are not provided for this case, experimental results demonstrate promising superlinear convergence behavior.
Improved Puiseux Series Estimation:
- A new, stable method (cRATIO) for estimating the leading fractional exponent $k_1/c$ .
- A novel recursive framework for estimating higher-order fractional exponents ( $k_i/c$ for $i \ge 2$ ) and their associated coefficients, enabling higher-order predictors for sparse Puiseux series.
Theoretical Guarantees: The paper provides formal proofs (Theorem 1 and Corollary 2) establishing the superlinear convergence rate for the corank-1 case, dependent on the accuracy of the exponent estimation and the neighborhood of the root.

Results

The authors benchmark their methods (AL for corank-1, LAL for corank $\ge 2$ ) against the classical power-series endgame (CLASSIC) using a suite of polynomial systems, including the Griewank-Osborne, Lecerf, and Caprasse systems, as well as custom-generated systems with specific coranks and winding numbers.

Convergence: The plots (Figures 1–12) illustrate the tracking residual $\log_{10} \|f(z)\|$ versus the cumulative number of matrix inversions. The proposed methods generally demonstrate faster convergence (steeper descent in residual) and the ability to reach deeper residuals with fewer matrix inversions compared to the classical approach, particularly in the deep endgame regime.
Stability: The comparison of exponent estimation methods (Figures 13–18) suggests that the proposed cRATIO method offers competitive or superior stability compared to cSORT and cLOG in various test instances.
Robustness: The lifted approach (LAL) successfully handles systems with higher coranks where standard endgames typically fail or stall, maintaining convergence through dynamic homotopy resetting.

Significance and Claims

The paper claims that the Arclength Endgame offers a significant advancement in computing singular solutions by achieving superlinear convergence without the computational overhead of deflation techniques (which require higher-order derivatives and can increase system dimension significantly).

The authors emphasize that their method is "endgame-aware," explicitly utilizing the geometric properties of the solution curve (Puiseux series) to regularize the system. They position the work as a practical improvement for Numerical Algebraic Geometry, providing a method that is both theoretically grounded (for corank-1) and empirically effective (for higher corank), while relying on standard function and Jacobian evaluations. The work does not claim to solve all singularities universally but targets the specific regime of isolated singular roots under generic homotopy assumptions.