Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We prove that the Davenport–Mahler bound holds for arbitrary graphs with vertices on the set of roots of a given univariate polynomial with complex coefficients. © 2016 Elsevier Inc.

Registro:

Documento: Artículo
Título:On the Davenport–Mahler bound
Autor:Escorcielo, P.; Perrucci, D.
Filiación:Departamento de Matemática, FCEN, Universidad de Buenos Aires, Argentina
IMAS, CONICET-UBA, Argentina
Palabras clave:Davenport–Mahler bound; Root separation; Subdiscriminants; Numerical analysis; Arbitrary graphs; Complex coefficients; Subdiscriminants; Univariate; Computational complexity
Año:2017
Volumen:41
Página de inicio:72
Página de fin:81
DOI: http://dx.doi.org/10.1016/j.jco.2016.12.001
Título revista:Journal of Complexity
Título revista abreviado:J. Complexity
ISSN:0885064X
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v41_n_p72_Escorcielo

Referencias:

  • Basu, S., Pollack, R., Roy, M.-F., Algorithms in Real Algebraic Geometry (2006) Algorithms and Computation in Mathematics, 10. , second ed. Springer-Verlag Berlin
  • Davenport, J., Cylindrical algebraic decomposition. Technical Report 88-10 (1988), University of Bath England; Du, Z., Sharma, V., Yap, C., Amortized bound for root isolation via Sturm sequences (2007) Symbolic-numeric Computation, Trends Math., pp. 113-129. , Birkhäuser Basel
  • Eigenwillig, A., Real Root Isolation for Exact and Approximate Polynomials Using Descartes’ Rule of Signs (2008), (Doctoral dissertation) Universität des Saarlandes; Eigenwillig, A., Sharma, V., Yap, C., Almost tight recursion tree bounds for the Descartes method (2006) ISSAC 2006, pp. 71-78. , ACM New York
  • Emiris, I., Mourrain, B., Tsigaridas, E., The DMM bound: multivariate (aggregate) separation bounds (2010) ISSAC 2010, pp. 243-250. , ACM New York
  • Johnson, J., Algorithms for polynomial real root isolation (1998) Quantifier elimination and cylindrical algebraic decomposition, Linz, 1993, Texts Monogr. Symbol. Comput., pp. 269-299. , Springer Vienna
  • Kerber, M., Sagraloff, M., A worst-case bound for topology computation of algebraic curves (2012) J. Symbolic Comput., 47 (3), pp. 239-258
  • Kincaid, D., Cheney, W., Numerical analysis (1996) Mathematics of Scientific Computing, , second ed. Brooks/Cole Publishing Co. Pacific Grove, CA
  • Mahler, K., An inequality for the discriminant of a polynomial (1964) Michigan Math. J., 11, pp. 257-262
  • Mignotte, M., Ştefănescu, D., (1999) Polynomials. An Algorithmic Approach, Springer Series in Discrete Mathematics and Theoretical Computer Science, , Springer-Verlag Singapore Singapore Centre for Discrete Mathematics & Theoretical Computer Science, Auckland
  • Yap, C., Fundamental Problems of Algorithmic Algebra (2000), Oxford University Press New York

Citas:

---------- APA ----------
Escorcielo, P. & Perrucci, D. (2017) . On the Davenport–Mahler bound. Journal of Complexity, 41, 72-81.
http://dx.doi.org/10.1016/j.jco.2016.12.001
---------- CHICAGO ----------
Escorcielo, P., Perrucci, D. "On the Davenport–Mahler bound" . Journal of Complexity 41 (2017) : 72-81.
http://dx.doi.org/10.1016/j.jco.2016.12.001
---------- MLA ----------
Escorcielo, P., Perrucci, D. "On the Davenport–Mahler bound" . Journal of Complexity, vol. 41, 2017, pp. 72-81.
http://dx.doi.org/10.1016/j.jco.2016.12.001
---------- VANCOUVER ----------
Escorcielo, P., Perrucci, D. On the Davenport–Mahler bound. J. Complexity. 2017;41:72-81.
http://dx.doi.org/10.1016/j.jco.2016.12.001