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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bank, B., Giusti, M., Heintz, J.
Formato: JOUR
Materias:
Copolar and bipolar varieties
Degree of variety
Intrinsic complexity
Polar
Real polynomial equation solving
Singularities
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_00255718_v83_n286_p873_Bank
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_00255718_v83_n286_p873_Bank
record_format dspace
spelling todo:paper_00255718_v83_n286_p873_Bank2023-10-03T14:36:14Z Point searching in real singular complete intersection varieties: Algorithms of intrinsic complexity Bank, B. Giusti, M. Heintz, J. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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
Bank, B.
Giusti, M.
Heintz, J.
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.
format JOUR
author Bank, B.
Giusti, M.
Heintz, J.
author_facet Bank, B.
Giusti, M.
Heintz, J.
author_sort Bank, B.
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
url http://hdl.handle.net/20.500.12110/paper_00255718_v83_n286_p873_Bank
work_keys_str_mv AT bankb pointsearchinginrealsingularcompleteintersectionvarietiesalgorithmsofintrinsiccomplexity
AT giustim pointsearchinginrealsingularcompleteintersectionvarietiesalgorithmsofintrinsiccomplexity
AT heintzj pointsearchinginrealsingularcompleteintersectionvarietiesalgorithmsofintrinsiccomplexity
_version_ 1782023534682308608

Ejemplares similares