Abstract:We consider the problem of computing sample points in each connected component of a semi-algebraic set defined by the non-vanishing or the positivity of an n-variate polynomial of degree d, with rational coefficients of bit size bounded by $\tau$. Such a problem is a basic routine in effective real algebraic geometry, used in higher-level algorithms for solving polynomial systems over the reals and finds many applications in sciences. We design a probabilistic algorithm for solving this problem, which is based on reductions to different routines for solving zero-dimensional polynomial systems. It assumes that the input polynomial satisfies sufficiently generic properties (namely, smoothness of its defining hypersurface). This is done through the computations of critical points of well-chosen maps to capture the connected components of the semi-algebraic set under study. We derive a bit complexity estimate for the cost of this algorithm, which is, in terms of the B{é}zout bound d(d -1)^{n-1}, essentially cubic for obtaining parametrisations of the sought-for real points. Moreover, we also consider the case of obtaining rational approximations of those points, which are precise enough to lie in the same connected components as their exact counterparts, which yields a cost that is essentially quartic in the B{é}zout bound. In these complexity estimates, we take into account the degree structure of the input polynomial and its partial derivatives, allowing for a more refined bit complexity when the partial derivative of the input polynomial have degree lower than expected. We also analyse the probability of success of those algorithms. We report on practical experiments, benchmarking with random dense input polynomials as well as polynomials coming from applications, which were out of reach of the state-of-the-art implementations, and hence illustrate the practical efficiency of these new algorithms.
| Subjects: | Symbolic Computation (cs.SC); Algebraic Geometry (math.AG) |
| Cite as: | arXiv:2605.18110 [cs.SC] |
| (or arXiv:2605.18110v2 [cs.SC] for this version) | |
| https://doi.org/10.48550/arXiv.2605.18110 arXiv-issued DOI via DataCite |
From: Edern Gillot [view email] [via CCSD proxy]
[v1]
Mon, 18 May 2026 09:19:29 UTC (281 KB)
[v2]
Fri, 22 May 2026 16:01:52 UTC (270 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。