Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Point searching in real singular complete intersection varieties: algorithms of intrinsic complexity
HTML articles powered by AMS MathViewer

by Bernd Bank, Marc Giusti and Joos Heintz PDF
Math. Comp. 83 (2014), 873-897 Request permission

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\;|\;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
Similar Articles
Additional Information
  • 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
  • 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.
  • © Copyright 2013 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • 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
  • MathSciNet review: 3143696