POINT SEARCHING IN REAL SINGULAR COMPLETE INTERSECTION VARIETIES: ALGORITHMS OF INTRINSIC COMPLEXITY

• Published in: Mathematics of computation 2014-03, Vol.83 (286), p.873-897
• Main Authors: BANK, BERND, GIUSTI, MARC, HEINTZ, JOOS
• Format: Article
• Language: English
• Subjects: Algebra; Arithmetic; Geometry; Hypergeometric functions; Hypersurfaces; Jacobians; Mathematical procedures; Mathematical theorems; Mathematical vectors; Polynomials
• ISSN: 0025-5718; 1088-6842
• DOI: 10.1090/S0025-5718-2013-02766-4

Let X₁,...,Xn be indeterminates over ℚ and let X := (X₁,...,Xn). Let F₁,...,Fp be a regular sequence of polynomials in ℚ[X] of degree at most d such that for each 1 ≤ k ≤ p the ideal (F₁,...,Fk) is radical. Suppose that the variables X₁,...,Xn are in generic position with respect to F₁,...,Fp. Further, suppose that the polynomials are given by an essentially division-free circuit β in ℚ[X} of size L and non-scalar depth ℓ. We present a family of algorithms Πi and invariants δi of F₁,...,Fp, 1 ≤ i ≤ n — p, such that Πi produces on input β a smooth algebraic sample point for each connected component of {x ε ℝn | F₁(x) = ... = Fp(x) = 0} where the Jacobian of F₁ = 0,...,Fp = 0 has generically rank p. The sequential complexity of Πi is of order L(nd)O(1)(min{(nd)cn,δi})² and its non-scalar parallel complexity is of order O(n(ℓ + log n d) log δi). Here c > 0 is a suitable universal constant. Thus, the complexity of Πi meets the already known worst case bounds. The particular feature of Πi is its pseudo-polynomial and intrinsic complexity character and this entails the best runtime behavior one can hope for. The algorithm Π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 (nnd)O(n) for the invariant δi. The reader may notice that this bound overestimates the extrinsic complexity of Πi, which is bounded by (nd)O(n).