Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present a new procedure to count the number of real zeros of a class of univariate Pfaffian functions of order 1. The procedure is based on the construction of Sturm sequences for these functions and relies on an oracle for sign determination. In the particular case of E-polynomials, we design an oracle-free effective algorithm solving this task within exponential complexity. In addition, we give an explicit upper bound for the absolute value of the real zeros of an E-polynomial. © 2016 Elsevier Inc.

Registro:

Documento: Artículo
Título:Zero counting for a class of univariate Pfaffian functions
Autor:Barbagallo, M.L.; Jeronimo, G.; Sabia, J.
Filiación:Departamento de Matemática, FCEN, Universidad de Buenos Aires, Argentina
Departamento de Ciencias Exactas, CBC, Universidad de Buenos Aires, Argentina
IMAS, CONICET-UBA, Argentina
Palabras clave:Complexity; Pfaffian functions; Sturm sequences; Zero counting
Año:2016
Volumen:452
Página de inicio:549
Página de fin:573
DOI: http://dx.doi.org/10.1016/j.jalgebra.2015.11.050
Título revista:Journal of Algebra
Título revista abreviado:J. Algebra
ISSN:00218693
CODEN:JALGA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00218693_v452_n_p549_Barbagallo

Referencias:

  • Basu, S., Pollack, R., Roy, Marie-Françoise, Algorithms in Real Algebraic Geometry (2006) Algorithms and Computation in Mathematics, 10. , http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted1.html, Springer-Verlag, Berlin, Online version available at
  • Gabrielov, A., Vorobjov, N., Complexity of computations with Pfaffian and Noetherian functions (2004) Normal Forms, Bifurcations and Finiteness Problems in Differential Equations, , Kluwer
  • von zur Gathen, J., Parallel arithmetic computations: a survey (1986) Lecture Notes in Comput. Sci., 233, pp. 93-112. , Springer, Berlin, Mathematical Foundations of Computer Science
  • von zur Gathen, J., Gerhard, Jürgen, (2003) Modern Computer Algebra, , Cambridge University Press, Cambridge
  • Heindel, L.E., Integer arithmetic algorithms for polynomial real zero determination (1971) J. ACM, 18, pp. 533-548
  • Khovanskii, A., On a class of systems of transcendental equations (1980) Sov. Math., Dokl., 22, pp. 762-765
  • Khovanskii, A., Fewnomials (1991) Translations of Mathematical Monographs, 88. , American Mathematical Society, Providence, RI
  • Macintyre, A., Wilkie, A.J., (1996) On the Decidability of the Real Exponential Field, Kreiseliana: About and Around Georg Kreisel, pp. 441-467. , A.K. Peters
  • Maignan, A., Solving one and two-dimensional exponential polynomial systems (1998) Proc. ISSAC'98, pp. 215-221. , ACM Press, New York, NY
  • McCallum, S., Weispfenning, V., Deciding polynomial-transcendental problems (2012) J. Symbolic Comput., 47 (1), pp. 16-31
  • Mignotte, M., Ştefănescu, D., Polynomials. An Algorithmic Approach (1999) Springer Series in Discrete Mathematics and Theoretical Computer Science, , Springer-Verlag Singapore, Singapore
  • Perrucci, D., Linear solving for sign determination (2011) Theoret. Comput. Sci., 412 (35), pp. 4715-4720
  • Richardson, D., Towards computing non algebraic cylindrical decompositions (1991) Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, pp. 247-255. , S.M. Watt (Ed.)
  • Roy, Marie-Françoise, Vorobjov, N., Finding irreducible components of some real transcendental varieties (1994) Comput. Complexity, 4, pp. 107-132
  • Sagraloff, M., Mehlhorn, K., Computing real roots of real polynomials (2016) J. Symbolic Comput., 73, pp. 46-86
  • Vorobjov, N.N., The complexity of deciding consistency of systems of polynomials in exponent inequalities (1992) J. Symbolic Comput., 13 (2), pp. 139-173
  • Waldschmidt, M., Transcendence measures for exponentials and logarithms (1978) J. Aust. Math. Soc. A, 25 (4), pp. 445-465
  • Wolter, H., On the "problem of the last root" for exponential terms (1985) Z. Math. Log. Grundl. Math., 31 (2), pp. 163-168
  • Wolter, H., On roots of exponential terms (1993) MLQ Math. Log. Q., 39 (1), pp. 96-102

Citas:

---------- APA ----------
Barbagallo, M.L., Jeronimo, G. & Sabia, J. (2016) . Zero counting for a class of univariate Pfaffian functions. Journal of Algebra, 452, 549-573.
http://dx.doi.org/10.1016/j.jalgebra.2015.11.050
---------- CHICAGO ----------
Barbagallo, M.L., Jeronimo, G., Sabia, J. "Zero counting for a class of univariate Pfaffian functions" . Journal of Algebra 452 (2016) : 549-573.
http://dx.doi.org/10.1016/j.jalgebra.2015.11.050
---------- MLA ----------
Barbagallo, M.L., Jeronimo, G., Sabia, J. "Zero counting for a class of univariate Pfaffian functions" . Journal of Algebra, vol. 452, 2016, pp. 549-573.
http://dx.doi.org/10.1016/j.jalgebra.2015.11.050
---------- VANCOUVER ----------
Barbagallo, M.L., Jeronimo, G., Sabia, J. Zero counting for a class of univariate Pfaffian functions. J. Algebra. 2016;452:549-573.
http://dx.doi.org/10.1016/j.jalgebra.2015.11.050