Counting solutions of a polynomial system locally and exactly

DOI10.1016/J.JSC.2023.102222arXiv1712.05487OpenAlexW2774293199MaRDI QIDQ6170809FDOQ6170809

Ruben Becker, Michael Sagraloff

Publication date: 10 August 2023

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: We propose a symbolic-numeric algorithm to count the number of solutions of a polynomial system within a local region. More specifically, given a zero-dimensional system $f_1=cdots=f_n=0$, with $f_{i}inmathbbC[x_1,ldots,x_n]$, and a polydisc $mathbfDeltasubsetmathbb{C}^n$, our method aims to certify the existence of $k$ solutions (counted with multiplicity) within the polydisc. In case of success, it yields the correct result under guarantee. Otherwise, no information is given. However, we show that our algorithm always succeeds if $mathbfDelta$ is sufficiently small and well-isolating for a $k$-fold solution $mathbfz$ of the system. Our analysis of the algorithm further yields a bound on the size of the polydisc for which our algorithm succeeds under guarantee. This bound depends on local parameters such as the size and multiplicity of $mathbfz$ as well as the distances between $mathbfz$ and all other solutions. Efficiency of our method stems from the fact that we reduce the problem of counting the roots in $mathbfDelta$ of the original system to the problem of solving a truncated system of degree $k$. In particular, if the multiplicity $k$ of $mathbfz$ is small compared to the total degrees of the polynomials $f_i$, our method considerably improves upon known complete and certified methods. For the special case of a bivariate system, we report on an implementation of our algorithm, and show experimentally that our algorithm leads to a significant improvement, when integrated as inclusion predicate into an elimination method.

Full work available at URL: https://arxiv.org/abs/1712.05487

zbMATH Keywords

complexity analysisbivariate systemspolynomial system solvingcertified computationelimination methodsarithmetic Nullstellensatz

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Numerical computation of solutions to systems of equations (65H10) Numerical computation of roots of polynomial equations (65H04)

Cites Work

• Algorithm 795
• HomotopyContinuation.jl: a package for homotopy continuation in Julia
• Using Algebraic Geometry
• Numerically solving polynomial systems with Bertini
• Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
• Title not available (Why is that?)
• Solving zero-dimensional systems through the rational univariate representation
• On the complexity of computing with planar algebraic curves
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Title not available (Why is that?)
• Homotopies for solving polynomial systems within a bounded domain
• From approximate factorization to root isolation with application to cylindrical algebraic decomposition
• Subdivision methods for solving polynomial equations
• Exact symbolic-numeric computation of planar algebraic curves
• The shifted number system for fast linear algebra on integer matrices
• The DMM bound
• Title not available (Why is that?)
• Thirty years of polynomial system solving, and now?
• A general approach to the analysis of controlled perturbation algorithms
• Certifying solutions to square systems of polynomial-exponential equations
• Complete subdivision algorithms, II
• Complexity Analysis of Root Clustering for a Complex Polynomial
• Improved algorithms for computing determinants and resultants
• On Analytic Differential Equations
• On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
• Computing multiple zeros of polynomial systems: case of breadth one (invited talk)

Cited In (2)

• Isolating clusters of zeros of analytic systems using arbitrary-degree inflation
• On Isolating Roots in a Multiple Field Extension

This page was built for publication: Counting solutions of a polynomial system locally and exactly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170809)