Cylindrical decomposition for systems transcendental in the first variable

We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f1(x),…,fm(x),y1,…,yn)p(x,f1(x),…,fm(x),y1,…,yn), where p∈Q[x,t1,…,tm,y1,…,yn]p∈Q[x,t1,…,tm,y1,…,yn] and f1(x),…,fm(x)f1(x),…,fm(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f1(x),…,fm(x)]Q[x,f1(x),…,fm(x)]. In particular, the algorithm applies when f1(x),…,fm(x)f1(x),…,fm(x) are real exp–log functions or tame elementary functions.

► We generalize the CAD algorithm to systems transcendental in the first variable. ► Needs real root isolation in the algebra generated by the transcendental functions. ► The algorithm applies to arbitrary exp–log functions or tame elementary functions. ► The algorithm has been implemented as a part of the Mathematica system. ► We present examples and experimental results.