Bit complexity for computing one point in each connected component of a smooth real algebraic set

DOI10.1016/J.JSC.2022.08.010arXiv2207.04289MaRDI QIDQ6404478FDOQ6404478

Authors: Jesse Elliott, Mark Giesbrecht, Éric Schost 

Publication date: 9 July 2022

Abstract: We analyze the bit complexity of an algorithm for the computation of at least one point in each connected component of a smooth real algebraic set. This work is a continuation of our analysis of the hypersurface case (On the bit complexity of finding points in connected components of a smooth real hypersurface, ISSAC'20). In this paper, we extend the analysis to more general cases. Let $F=(f_1,\mathrm{...},f_p)$ in $mathbbZ[X_1,\mathrm{...},X_n{]}^p$ be a sequence of polynomials with $V=V(F)subsetmathbb{C}^n$ a smooth and equidimensional variety and $langleFanglesubsetmathbbC[X_1,\mathrm{...},X_n]$ a radical ideal. To compute at least one point in each connected component of $Vcapmathbb{R}^n$, our starting point is an algorithm by Safey El Din and Schost (Polar varieties and computation of one point in each connected component of a smooth real algebraic set, ISSAC'03). This algorithm uses random changes of variables that are proven to generically ensure certain desirable geometric properties. The cost of the algorithm was given in an algebraic complexity model; here, we analyze the bit complexity and the error probability, and we provide a quantitative analysis of the genericity statements. In particular, we are led to use Lagrange systems to describe polar varieties, as they make it simpler to rely on techniques such as weak transversality and an effective Nullstellensatz.

Mathematics Subject Classification ID

Real algebraic sets (14P05) Computational real algebraic geometry (14Q30)

This page was built for publication: Bit complexity for computing one point in each connected component of a smooth real algebraic set

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