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