Solving parametric systems of polynomial equations over the reals through Hermite matrices (Q2117425)

The focus of this work lies on finite collections of parametric polynomials, under the assumption that the set of common roots is finite for generic choices of the parameters. Given such a collection, it tackles the problem of describing semialgebraic sets (cells) of parameter space such that the number of real roots remains constant within each set. Moreover, the union of these semialgebraic sets must be dense in parameter space. In particular, the main result is the existence of algorithms that construct inequalities that describe these semialgebraic sets and compute, for each set, the number of real roots, as well as sample points. This problem has many applications in life sciences and engineering. A common approach is provided by Cylindrical Algebraic Decomposition [\textit{G. E. Collins}, ACM SIGSAM Bull. 1, 2, 1--10 (1976)], although its computational cost is high (in time and data involved in the descriptions). Polynomials whose zero locus contains the boundary of the cells are used in other algorithms [\textit{L. Yang} and \textit{B. Xia}, Proceedings of the A3L, 281--289 (2005); \textit{D. Lazard} and \textit{F. Rouillier}, J. Symb. Comput. 42, No. 6, 636--667 (2007; Zbl 1156.14044)], although the approach presented here, by means of Hermite matrices, has the potential to be computationally cheaper. Let \(f=(f_1,\ldots ,f_m)\) be a collection of polynomials in \(\mathbb{Q}[y][x]\), where the \(y=(y_1,\ldots ,y_t)\) are sometimes seen as parameters and the \(x=(x_1,\ldots ,x_n)\) as variables, and consider the complex algebraic variety \(V\) defined in \(\mathbb{C}^t\times\mathbb{C}^n\) by the ideal \(\langle f_1,\ldots ,f_m\rangle \), which is assumed here to be radical. Assume also that the fibers of the projection of \(V\) over parameter space \(\mathbb{C}^t\) are generically nonempty and finite. The main theorem (Theorem I) states that, for generic choices of \(f\), it is possible to find semialgebraic descriptions of the cells in terms of polynomials in \(\mathbb{Q}[y]\) whose degree is bounded by \(n(d-1)d^n\), where \(d=\max\{\mathrm{deg}(f_i):i=1,\ldots ,m\}\), by means of a probabilistic algorithm, and one further algorithm allows to compute the number of real roots and find sample points for each cell. The theorem also gives complexity bounds for both algorithms in terms of the arithmetic operations in \(\mathbb{Q}\) that they need. Proposed algorithms performing these tasks are also provided. The algorithms proposed here are based on Hermite matrices [\textit{C. Hermite}, J. Reine Angew. Math. 52, 39--51 (1856; Zbl 02750422)]. For this, the authors extend to polynomials with parametric coefficients the definition of Hermite matrices, as well as techniques that count real roots for zero-dimensional polynomial ideals using the signature of these matrices. The cells appear as the connected components of the complementary of the closed set defined by a polynomial, which is derived from the determinant of the parametric Hermite matrix associated to \(f\). Algorithm 2 uses zero-dimensional parametrizations [\textit{L. Kronecker}, J. Reine Angew. Math. 92, 1--122 (1882; JFM 14.0038.02)], which can be found as a result of Theorem II and Corollary 3, to compute points for the different cells. Then, it computes the number of real points using the signature of the specialization of the parametric Hermite matrix to the sample points. Moreover, in Algorithm 3 the leading principal minors of the parametric Hermite matrix are used for the semialgebraic descriptions of the cells. The algorithms have been implemented in Maple, using FGb and RAGlib. These implementations might not meet the best bounds proven to be possible in Theorem I, but still improve existing ones. They have been tested via two types of experiments. The first one is a comparison with other known algorithms for random dense polynomial systems of total fixed degrees, for 2, 3 and 4 parameters. The second one consists of applying the algorithm to two known examples: Kuramoto model [\textit{Y. Kuramoto}, in: Araki, H. (ed.), International Symposium on Mathematical Problems in Theoretical Physics, 420--422 (1975)] and Static output feedback [\textit{D. Henrion} and \textit{M. Sebek}, in: Jeffrey, David J. (ed.), Proceedings of the 2008 international symposium on symbolic and algebraic computation, ISSAC 2008, Linz/Hagenberg, Austria, July 20--23, 2008, 111--116 (2008; Zbl 1487.93024)].