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...
| Publicado: |
2014
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255718_v83_n286_p873_Bank http://hdl.handle.net/20.500.12110/paper_00255718_v83_n286_p873_Bank |
| Aporte de: |
| id |
paper:paper_00255718_v83_n286_p873_Bank |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_00255718_v83_n286_p873_Bank2023-06-08T14:53:16Z Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity Copolar and bipolar varieties Degree of variety Intrinsic complexity Polar Real polynomial equation solving Singularities 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. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255718_v83_n286_p873_Bank http://hdl.handle.net/20.500.12110/paper_00255718_v83_n286_p873_Bank |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Copolar and bipolar varieties Degree of variety Intrinsic complexity Polar Real polynomial equation solving Singularities |
| spellingShingle |
Copolar and bipolar varieties Degree of variety Intrinsic complexity Polar Real polynomial equation solving Singularities Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity |
| topic_facet |
Copolar and bipolar varieties Degree of variety Intrinsic complexity Polar Real polynomial equation solving Singularities |
| description |
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. |
| title |
Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity |
| title_short |
Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity |
| title_full |
Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity |
| title_fullStr |
Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity |
| title_full_unstemmed |
Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity |
| title_sort |
point searching in real singular complete intersection varieties: algorithms of intrinsic complexity |
| publishDate |
2014 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255718_v83_n286_p873_Bank http://hdl.handle.net/20.500.12110/paper_00255718_v83_n286_p873_Bank |
| _version_ |
1768546008797544448 |