Separation bounds for polynomial systems

Ioannis Z. Emiris, Bernard Mourrain, Elias P. TsigaridasJ. Symb. Comput 2020 · DOI · OpenReview

Introduction

In the field of computational algebra, the challenge of "root isolation"—identifying all common solutions to a system of multivariate polynomials—is foundational. To perform this task reliably, algorithms require a precise "separation bound," defined as the minimum distance between any two distinct roots. This bound dictates the precision necessary for numerical methods to distinguish between close solutions without missing any or failing to converge.

Historically, the benchmark for these calculations has been Canny’s Gap theorem. However, Canny’s bounds are often "loose," predicting that roots could be significantly closer than they appear in practical applications. This leads to excessive computational overhead. Furthermore, many traditional bounds are restricted to "square" systems (where the number of equations equals the number of variables) or zero-dimensional systems. This research introduces novel, tighter, and "adaptive" separation bounds that exploit the inherent sparsity of polynomial systems and extend to overdetermined or higher-dimensional cases.

Methodology: Leveraging Sparsity and Resultants

The authors extend the Davenport-Mahler-Mignotte (DMM) bound, originally a univariate tool, to the multivariate domain ($DMM_n$). Their methodology integrates several advanced mathematical frameworks:

  • Mixed Volume: Unlike the Bézout bound, which assumes a dense system where every possible term is present, mixed volume accounts for the sparsity of the system. By focusing on the actual non-zero coefficients typical of real-world equations, the authors provide a more realistic estimate of root distribution.
  • Sparse (Toric) Resultants: The researchers utilize resultants to eliminate variables, reducing complex multivariate systems into univariate forms. They then apply height bounds to these resulting polynomials to estimate root locations with greater accuracy.
  • Toric Generalized Characteristic Polynomial (TGCP): To address positive-dimensional systems—where solutions may form curves or surfaces—the paper employs a perturbation technique to isolate specific points of interest for analysis.
  • Linear Combinations for Overdetermined Systems: For systems with more equations than variables, a reduction technique transforms them into "square" systems, allowing the application of the new $DMM_n$ bounds.

Key Theoretical Insights

The core contribution of this work is the demonstration that sparsity is a superpower in algebraic computing. By utilizing mixed volume instead of total degree, the authors show that the worst-case scenarios for sparse systems are significantly more manageable than previously theorized.

The resulting $DMM_n$ bound improves upon Canny’s Gap theorem by a factor of $O(d^{n-1})$, where $d$ represents the degree and $n$ the number of variables. Crucially, these bounds are universal; they do not require the system to be zero-dimensional or square, making them highly versatile for general algebraic computing tasks. Additionally, the paper provides a new proof establishing that computing the eigenvalues and eigenvectors of an integer matrix has polynomial bit complexity, a significant improvement over previous exponential estimates.

Results and Practical Applications

The theoretical advancements translate into tangible improvements in several areas:

  1. Bound Tightness: For specific systems, the new bounds are within a factor of $O(2^n)$ of being optimal. This is a marked improvement over previous results, particularly for systems with a small number of variables.
  2. Global Optimization: When calculating the minimum value of a positive polynomial over a simplex, the authors' bounds are at least one order of magnitude tighter than the three best-known preceding methods.
  3. Algorithm Efficiency: The paper offers an asymptotic bound on the steps required for subdivision-based algorithms (common in robotics and CAD) to isolate all real roots, providing a clearer roadmap for algorithmic optimization.
  4. Eigenvalue Precision: The derived bound for eigenvalues is "exponentially better" than Canny’s original theorem, facilitating higher precision in spectral analysis.

Limitations and Future Outlook

While these results represent a significant leap forward, they focus on "worst-case" bounds. In practice, roots are often even better separated than these tighter bounds suggest. Developing an "average-case" $DMM_n$ bound remains a primary challenge for future research.

Furthermore, the authors note that the specific constants in their formulas could be further refined. For positive-dimensional systems, there is ongoing work to express bounds more precisely in relation to the dimension of "excess" components. Despite these areas for refinement, the $DMM_n$ framework provides a robust and more efficient theoretical foundation for the next generation of algebraic solvers.

Summary updated

BibTeX
@article{emiris2020separation,
  author = {Ioannis Z. Emiris and Bernard Mourrain and Elias P. Tsigaridas},
  title = {{Separation bounds for polynomial systems}},
  journal = {J. Symb. Comput.},
  year = {2020},
  doi = {10.1016/j.jsc.2019.07.001},
}
Figure