论文标题
在平滑真实代数集的每个连接组件中计算一个点的位复杂性
Bit complexity for computing one point in each connected component of a smooth real algebraic set
论文作者
论文摘要
我们分析了平滑真实代数集的每个连接组件中至少一个点的计算算法的位复杂性。这项工作是我们对Hypersurface病例的分析的延续（关于在平滑真实的超脸的连接组件中查找点的位，ISSAC'20）。在本文中，我们将分析扩展到更一般的情况。 Let $F=(f_1,..., f_p)$ in $\mathbb{Z}[X_1, ... , X_n]^p$ be a sequence of polynomials with $V = V(F) \subset \mathbb{C}^n$ a smooth and equidimensional variety and $\langle F \rangle \subset \mathbb{C}[X_1, ...，x_n] $一个根本的理想。要计算$ v \ cap \ mathbb {r}^n $的每个连接组件中的至少一个点，我们的起点是Safey El Din and Schost的算法（极性品种和计算平滑的真实代数集的每个连接组件中一个点的一个点和计算，ISSAC'03）。该算法使用变量的随机更改，这些变量被证明是一致确保某些理想的几何特性。该算法的成本是在代数复杂度模型中给出的。在这里，我们分析了位的复杂性和错误概率，并提供了对通用语句的定量分析。特别是，我们被促使我们使用拉格朗日系统来描述极地品种，因为它们使依靠诸如弱横向性和有效的无效的无效技术变得更加简单。
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,..., f_p)$ in $\mathbb{Z}[X_1, ... , X_n]^p$ be a sequence of polynomials with $V = V(F) \subset \mathbb{C}^n$ a smooth and equidimensional variety and $\langle F \rangle \subset \mathbb{C}[X_1, ..., X_n]$ a radical ideal. To compute at least one point in each connected component of $V \cap \mathbb{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.
