Piecewise algebraic functions (Q2277540)

The authors study what they call piecewise algebraic (P. A.) sets and functions. The P. A. sets are simply the constructible subsets of \({\mathbb{C}}^ n\) defined over \({\mathbb{Z}}\) (given by finite Boolean combination of polynomial equations and inequalities with coefficients in \({\mathbb{Z}})\), and P. A. functions are multivalued functions whose graph is P. A. The main tool is a decomposition of P. A. sets into a finite disjoint union of ``normal'' P. A. sets, which are roughly finite sheeted coverings of complements of algebraic hypersurfaces in affine spaces corresponding to a subset of the coordinates. This gives closure properties of P. A. sets and functions with respect to several constructions, and a nice notion of dimension. The authors care that the constructions are performed inside ``certainly computable'' P. A. sets. Then they turn to some applications: dependence of the minimal complexity of the computation of a polynomial upon its coefficients, dependence of the Jordan canonical form of a matrix upon its coefficients, dependence of formal solutions of meromorphic differential equations upon the coefficients of the equation. It is a pity that there is no mention of quantifier elimination theory, concerning the properties of constructible subsets defined over \({\mathbb{Z}}\). For instance the fact that ``the projection of a certainly computable P. A. set is a certainly computable P. A. set'' is just the effective quantifier elimination for algebraically closed field, and this has now been well studied from the point of view of complexity [\textit{J. Heintz}, Theor. Comput. Sci. 24, 239--277 (1983; Zbl 0546.03017)]. Also, the decomposition into normal P. A. sets plays a role very similar to the cylindrical algebraic decomposition of \textit{G. E. Collins} [see Autom. Theor. Formal Lang., 2nd GI Conf., Kaiserslautern 1975, Lect. Notes Comput. Sci. 33, 134--183 (1975; Zbl 0318.02051)] in the real case.