Zero counting for a class of univariate Pfaffian functions

DOI10.1016/J.JALGEBRA.2015.11.050MaRDI QIDQ5964515zbMATH OpenOpenAlexFDO

Authors María Laura Barbagallo, Gabriela Jeronimo, Juan Sabia

Publication date 29 February 2016

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.07406

complexity Pfaffian functions Sturm sequences zero counting

Derivations and commutative rings (13N15) Rationally connected varieties (14M22) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Symbolic computation and algebraic computation (68W30)

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.

Review text

Given an integer polynomial \(\mathrm{F}(X,Y)\), this paper introduces first a new symbolic algorithm to count the number of real zeros in a real interval of \(f(x)=\mathrm{F}(x,\varphi(x))\), where \(\varphi(x)\) is a univariate Pfaffian function of order 1. This algorithm, which is called \texttt{ZeroCounting}, uses Sturm sequences associated to \(f(x)\) and Subresultants as essential tools, and relies on an oracle for sign determination. In some sense, this work is a continuation of \textit{D. Richardson} [in: ISSAC '91. Proceedings of the 1991 international symposium on Symbolic and algebraic computation. Bonn, Germany, July 15--17, 1991. New York, NY: ACM Press. 247--255 (1991; Zbl 0925.65091)], where Sturm sequences of transcendental functions are introduced, and [\textit{A. Maignan}, in: Proceedings of the 1998 international symposium on symbolic and algebraic computation, ISSAC '98, Rostock, Germany, August 13--15, 1998. New York, NY: ACM Press. 215--221 (1998; Zbl 0924.65044)], where the function \(\mathrm{F}(x,e^x)\) is studied. Secondly, in the particular case of \(E\)-polynomials, that is, \(f(x)=\mathrm{F}(x,e^{h(x)})\) with \(h(X)\in \mathbb{Z}[X]\), the algorithm \texttt{ZeroCounting} is modified in order to obtain a zero counting algorithm with no calls to oracles. The complexity analysis of each subroutine used is provided. In addition, an explicit upper bound for the absolute value of the real zeros of an E-polynomial is also presented. Examples are not given.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Zero counting for a class of univariate Pfaffian functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964515)