   ISSN 1088-6842(online) ISSN 0025-5718(print)

Point searching in real singular complete intersection varieties: algorithms of intrinsic complexity

Authors: Bernd Bank, Marc Giusti and Joos Heintz
Journal: Math. Comp. 83 (2014), 873-897
MSC (2010): Primary 68W30, 14B05, 14P05, 14B07, 68W10
DOI: https://doi.org/10.1090/S0025-5718-2013-02766-4
Published electronically: October 31, 2013
MathSciNet review: 3143696
Full-text PDF Free Access

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)}$.

[Enhancements On Off] (What's this?)

References

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 14B05, 14P05, 14B07, 68W10

Retrieve articles in all journals with MSC (2010): 68W30, 14B05, 14P05, 14B07, 68W10

Bernd Bank
Affiliation: Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany
Email: bank@mathematik.hu-berlin.de

Marc Giusti
Affiliation: CNRS, École Polytechnique, Lab. LIX, F-91228 Palaiseau, Cedex, France
Email: marc.giusti@polytechnique.fr

Joos Heintz
Affiliation: Departamento de Computación, Universidad de Buenos Aires, CONICET, Ciudad Universitaria, Pabellon I, 1428 Buenos Aires, Argentina — Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, Avda. de los Castros, E-39005 Santander, Spain
Email: joos@dc.uba.ar

Keywords: Real polynomial equation solving, intrinsic complexity, singularities, polar, copolar and bipolar varieties, degree of variety
Received by editor(s): August 16, 2011
Received by editor(s) in revised form: July 12, 2012
Published electronically: October 31, 2013
Additional Notes: This research was partially supported by the following Argentinian, French and Spanish grants: CONICET PIP 2461/01, UBACYT 20020100100945, PICT–2010–0525, Digiteo DIM 2009–36HD “Magix”, ANR-2010-BLAN-0109-04 “LEDA”, MTM2010-16051.