Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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
Published electronically: October 31, 2013
MathSciNet review: 3143696
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


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

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


Similar Articles

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

Additional Information

Bernd Bank
Affiliation: Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany

Marc Giusti
Affiliation: CNRS, École Polytechnique, Lab. LIX, F-91228 Palaiseau, Cedex, France

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

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.
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.