Counting solutions of a polynomial system locally and exactly

DOI10.1016/J.JSC.2023.102222MaRDI QIDQ6170809zbMATH OpenOpenAlexFDO

Publication date 10 August 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

complexity analysis bivariate systems polynomial system solving certified computation elimination methods arithmetic 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)

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} = c d o t s = f_{n} = 0

, with

f_{i} i n m a t h b b C [x_{1}, l d o t s, x_{n}]

, and a polydisc

m a t h b f D e l t a s u b s e t m a t h b b 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

m a t h b f D e l t a

is sufficiently small and well-isolating for a

k

-fold solution

m a t h b f z

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

m a t h b f z

as well as the distances between

m a t h b f z

and all other solutions. Efficiency of our method stems from the fact that we reduce the problem of counting the roots in

m a t h b f D e l t a

of the original system to the problem of solving a truncated system of degree

k

. In particular, if the multiplicity

k

of

m a t h b f z

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.

Cites work

Cited in

(2)

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)