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

Abstract

Abstract. Let X1, . . .,Xn be indeterminates over Q and let X := (X1, . . . ,Xn). Let F1, . . . ,Fp be a regular sequence of polynomials in Q[X] of degreeat most d such that for each 1 ≤ k ≤ p the ideal (F1, . . . , Fk) is radical.Suppose that the variables X1, . . .,Xn are in generic position with respect toF1, . . . ,Fp. Further, suppose that the polynomials are given by an essentiallydivision-free circuit β in Q[X] of size L and non-scalar depth .We present a family of algorithms Πi and invariants δi of F1, . . . ,Fp, 1 ≤i ≤ n − p, such that Πi produces on input β a smooth algebraic sample pointfor each connected component of {x ∈ Rn | F1(x) = ・ ・ ・ = Fp(x) = 0} wherethe Jacobian of F1 = 0, . . . , Fp = 0 has generically rank p.The sequential complexity of Πi is of order L(nd)O(1)(min{(nd)cn, δi})2and its non-scalar parallel complexity is of order O(n( + lognd) log δi). Herec > 0 is a suitable universal constant. Thus, the complexity of Πi meetsthe already known worst case bounds. The particular feature of Πi is itspseudo-polynomial and intrinsic complexity character and this entails the bestruntime behavior one can hope for. The algorithm Πi works in the non-uniformdeterministic as well as in the uniform probabilistic complexity model. Wealso exhibit a worst case estimate of order (nn d)O(n) for the invariant δi. Thereader may notice that this bound overestimates the extrinsic complexity ofΠi, which is bounded by (nd)O(n).1.