Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity
Bernd Bank, M Giusti, Joos Heintz · Mathematics of Computation · 2013
Let $X_1,\ldots ,X_n$ be indeterminates over $\mathbb {Q}$ and let $X:=(X_1,\ldots ,$ $X_n)$. Let $F_1,\ldots ,F_p$ be a regular sequence of polynomials in $\mathbb {Q}[X]$ of degree at most $d$ such that for each $1\le k \le p$ the ideal $(F_1,\ldots , F_k)$ is radical. Suppose that the variables $X_1,\ldots ,X_n$ are in generic position with respect to $F_1,\ldots ,F_p$. Further, suppose that the polynomials are given by an essentially division-free circuit $\beta$ in $\mathbb {Q}[X]$ of size $L$ and non-scalar depth $\ell$. We present a family of algorithms $\Pi _i$ and invariants $\delta _i$ of $F_1,\ldots ,F_p$, $1\le i \le n-p$, such that $\Pi _i$ produces on input $\beta$ a smooth algebraic sample point for each connected component of $\{x\in \mathbb {R}^n\;|\;F_1(x)=\cdots =F_p(x)=0\}$ where the Jacobian of $F_1=0,\ldots , F_p=0$ has generically rank $p$. The sequential complexity of $\Pi _i$ is of order $L(n d)^{O(1)}(\min \{(n d)^{c n},\delta _i\})^2$ and its non-scalar parallel complexity is of order $O(n(\ell +\log n d)\log \delta _i)$. Here $c>0$ is a suitable universal constant. Thus, the complexity of $\Pi _i$ meets the already known worst case bounds. The particular feature of $\Pi _i$ is its pseudo-polynomial and intrinsic complexity character and this entails the best runtime behavior one can hope for. The algorithm $\Pi _i$ works in the non-uniform deterministic as well as in the uniform probabilistic complexity model. We also exhibit a worst case estimate of order $(n^n d)^{O(n)}$ for the invariant $\delta _i$. The reader may notice that this bound overestimates the extrinsic complexity of $\Pi _i$, which is bounded by $(nd)^{O(n)}$.