Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Point searching in real singularcomplete 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

Abstract: 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\;\vert\;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.