Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity
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 degree at 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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00255718_v83_n286_p873_Bank |
| Aporte de: |
| Sumario: | 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 degree at 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 to F1, . . . ,Fp. Further, suppose that the polynomials are given by an essentially division-free circuit β in Q[X] of size L and non-scalar depth l. We present a family of algorithms φi and invariants di of F1, . . . ,Fp, 1 = i = n - p, such that δi produces on input β a smooth algebraic sample point for each connected component of {x ε Rn F1(x) = . . . = Fp(x) = 0} where the 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})2 and its non-scalar parallel complexity is of order O(n(l + lognd) 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 (nn d)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). © 2013 American Mathematical Society. |
|---|