Rigid homotopies for sampling from algebraic varieties: a Waring structure complexity model

This paper establishes a new complexity result for rigid homotopy methods applied to polynomial systems with Waring representations and presents the first computational experiments validating these methods.

The Gist

The Big Picture: Solving Math Mazes

Imagine you are trying to solve a giant, complex maze made of mathematical equations. In the world of computer science, this is called "solving a polynomial system." For a long time, mathematicians have been trying to figure out the fastest, most reliable way to find the exit (the solution) of these mazes.

The authors of this paper are testing a specific new strategy called Rigid Homotopy. Think of this strategy not as running through the maze randomly, but as walking along a very specific, carefully constructed bridge that connects a simple, easy maze to the complex one you want to solve.

The Problem: The "Wobbly Bridge"

Usually, when computers try to solve these math mazes, they use a method called "homotopy continuation." They start with a simple problem they know the answer to, and they slowly morph it into the hard problem.

However, the path they take can be tricky. If the bridge they are walking on gets too curvy or unstable (mathematically, "ill-conditioned"), the computer might stumble, take tiny, slow steps, or even fall off the path entirely.

The Solution: The "Rigid" Bridge

The authors focus on a special type of bridge called a Rigid Homotopy.

• The Analogy: Imagine a standard bridge that can bend and twist in any direction. A "rigid" bridge is like a train track. It is locked in place. It can't twist wildly; it only moves in a very controlled, predictable way.
• Why it helps: Because the path is "rigid" (restricted to specific movements), it is much less likely to run into the dangerous, wobbly spots where the computer would get stuck.

The Special Ingredient: The "Waring" Recipe

The paper specifically looks at a certain type of math problem that has a special structure, called a Waring representation.

• The Analogy: Imagine you are baking a cake.
  • Standard Cake: You mix 100 different ingredients (flour, sugar, eggs, spices, etc.) all together in a giant bowl. It's a dense, messy mix.
  • Waring Cake: You have a special recipe where the cake is just a sum of a few distinct layers. For example, it's just "Layer A" + "Layer B" + "Layer C." Even if the final cake looks complex, you know exactly how it was built from these few simple layers.
• The Claim: The authors prove that if your math problem is built like this "Waring Cake" (a sum of a few simple parts), the "Rigid Bridge" strategy works incredibly well.

The Main Discovery: Speed and Safety

The paper makes two main claims about this strategy:

1. It's Fast on Average: They proved mathematically that for these special "Waring" problems, the computer won't get stuck. The "bridge" stays stable enough that the computer can cross it quickly, even as the problems get bigger.
2. The "Length" Doesn't Matter Much: A Waring problem has a "length" (how many layers/summands it has). The authors found that as long as you have enough layers, the extra complexity doesn't slow the computer down. It's like saying, "As long as your cake has at least 5 layers, adding 10 more layers won't make it harder to bake."

The Experiments: Testing the Bridge

The authors didn't just do the math on paper; they built a computer program (a "preliminary implementation") to test this in the real world.

• What they did: They ran thousands of tests on different math mazes.
• What they found:
  • The "Rigid Homotopy" method worked as predicted.
  • The computer took steps that were perfectly sized—neither too big (which causes falling) nor too small (which causes slowness).
  • Interestingly, they found that sometimes you don't even need the complex math to decide step size; a simple, fixed step size often worked just as well, suggesting the method is very robust.

The Bottom Line

This paper is a "proof of concept." It shows that for a specific, important class of math problems (those with Waring structures), using a "Rigid Homotopy" is a safe, efficient, and theoretically sound way to find solutions. It bridges the gap between complex mathematical theory and practical computer performance, proving that these special structured problems are easier to solve than we might have thought.

Technical Summary

Technical Summary: Rigid Homotopies for Sampling from Algebraic Varieties

Problem Statement

The paper addresses the computational complexity of solving polynomial systems, specifically focusing on bridging the gap between theoretical complexity analysis (centered on Smale's 17th problem) and practical computational performance. While homotopy continuation has established average-case polynomial-time algorithms for dense random systems, practical applications often involve structured systems with specific representations that allow for efficient evaluation but may not fit standard dense models.

The authors investigate rigid homotopy, a method that restricts the deformation of polynomial systems to a low-dimensional family of unitary transformations. The specific problem tackled is determining the average-case complexity of rigid homotopy continuation for polynomial systems admitting Waring representations (sums of powers of linear forms). The goal is to prove that the expected condition number for such systems remains polynomially bounded, thereby ensuring that the algorithm terminates in polynomial time on average, similar to dense or Algebraic Branching Program (ABP) models.

Methodology

Theoretical Framework

The authors analyze the complexity of rigid homotopy using the $\gamma$-number (Smale's condition number), which governs the convergence radius of Newton's method and dictates the step size in path tracking.

1. Rigid Homotopy Setup: Instead of varying coefficients arbitrarily, the method deforms a system $f$ via unitary actions $u \in U(n+1)^n$. The path is defined by $\phi(t) = \exp(tA)$, where $A$ is a skew-Hermitian matrix.
2. Split $\gamma$-number: Due to the component-wise nature of the unitary action, the authors utilize a "split $\gamma$-number" ($\hat{\gamma}$) that combines the component-wise curvature measures with a condition number $\kappa$ reflecting the transversality of the hypersurfaces.
3. Waring Representation: A homogeneous polynomial $f$ of degree $D$ is represented as $f(z) = \sum_{i=1}^r L_i(z)^D$, where $L_i$ are linear forms and $r$ is the length of the representation. This model is chosen because it offers low evaluation complexity ($O(r(n+D))$) compared to the dense coefficient size.

Complexity Analysis

The core theoretical contribution is the derivation of an upper bound for the averaged $\gamma$-number ($\Gamma_{\text{Avg}}$) for random Waring systems.

• Expectation Formulation: The authors formulate the expected squared condition number as an integral over the space of Waring representations ($W_r$) and the zero set of the polynomial.
• Unitary Invariance: By exploiting the unitary invariance of the Gaussian measure on the linear forms, the authors reduce the problem to an iterated integral. They decompose the parameter space into radial and spherical components.
• Integral Evaluation: The inner integral (over the coefficients of the linear forms excluding the constant term) is evaluated using properties of the Bombieri-Weyl norm and Gaussian moments. The outer integral (over the constant terms constrained by the zero condition) is bounded using polar coordinates and estimates on the spherical maximum of the integrand.
• Resulting Bound: The analysis yields a bound dependent on the dimension $n$, degree $D$, and the Waring length $r$. A key factor is $R_{r,D} = \prod_{j=2}^D \frac{r}{r-j}$, which captures the structural penalty of the Waring representation.

Computational Experiments

The authors implemented the rigid homotopy algorithm (Algorithms 3.1–3.3) in Julia, utilizing automatic differentiation (Enzyme) and FFTW for polynomial evaluation.

• Sampling: Random start pairs $(u, \zeta)$ are generated using a randomized construction to ensure a "good start pair."
• Path Tracking: The algorithm tracks the solution path from $t=1$ to $t=0$ using a step size inversely proportional to the estimated $\gamma$-number ($\hat{\gamma}_{\text{Frob}}$).
• Estimation: A probabilistic estimator (Algorithm 3.2) is used to approximate the Frobenius norm of the shifted polynomial, avoiding the combinatorial explosion of monomials in the black-box model.

Key Contributions

1. Theoretical Complexity Bound (Theorem 6): The paper proves that for random polynomials with a Waring decomposition of length $r$, the expected squared averaged condition number is polynomially bounded in $n$ and $D$. Specifically, the bound includes a factor $R_{r,D}$ which approaches 1 as $r \to \infty$. This demonstrates that the favorable complexity behavior of rigid homotopy extends to this class of structured inputs.
2. Extension to Systems (Corollary 7): The result is extended to homogeneous systems of Waring polynomials, establishing that the rigid homotopy algorithm terminates in polynomial time on average for these systems.
3. First Implementation: The authors provide the first computational implementation of rigid homotopy for Waring systems, validating the theoretical framework with empirical data.
4. Empirical Validation: Experiments confirm that the estimated condition numbers and iteration counts behave as predicted:
   • Dependence on $r$ is weak and asymptotically negligible.
   • Dependence on $n$ and $D$ aligns with the theoretical polynomial growth.
   • The probabilistic estimator for $\gamma$-numbers, while occasionally producing large outliers, generally provides stable estimates for typical instances.

Results

• Complexity: The expected condition number is bounded by $O(\text{poly}(n, D) \cdot R_{r,D})$. Since $R_{r,D} \approx 1 + O(1/r)$, the structural cost vanishes for sufficiently large $r$.
• Experimental Trends:
  • Iteration counts and estimated $\Gamma$ values increase with dimension $n$ and degree $D$.
  • Increasing the Waring length $r$ does not systematically increase the condition number or iteration count, supporting the theoretical claim that the penalty vanishes.
  • Step Size Comparison: Comparisons with heuristic constant step sizes show that while the adaptive algorithm is robust, constant step sizes (e.g., $10^{-2}$ to $10^{-4}$) often achieve 100% success rates for small systems, suggesting potential for efficiency gains by bypassing the expensive $\gamma$-estimation in practice.
• Scalability: The current implementation struggles with larger $n$ and $D$ due to the conservative step size construction, which can lead to excessively small steps and high iteration counts.

Significance and Claims

The paper claims to provide a new complexity result that validates the practicality of rigid homotopy for a broader class of polynomial systems beyond dense or ABP models. By proving that Waring-type structured inputs admit polynomial average complexity, the authors argue that rigid homotopy is a viable paradigm for solving structured systems arising in applications like polynomial neural networks.

The authors are modest regarding the current implementation's limitations. They acknowledge that the probabilistic estimation of $\gamma$-numbers can be conservative, leading to inefficiencies in practice. They frame their work as a "proof of concept" that establishes the theoretical foundation and demonstrates initial empirical behavior, while identifying the need for more robust, adaptive step-size strategies and refined condition number estimators for future scalability. The work does not claim to solve all polynomial systems but specifically targets those with low evaluation complexity representations.