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

DOI10.1016/J.JSC.2021.12.002zbMATH Open1487.14130arXiv2011.14136OpenAlexW3108459106WikidataQ114154451 ScholiaQ114154451MaRDI QIDQ2117425FDOQ2117425

Authors: Huu Phuoc Le, Mohab Safey El Din 

Publication date: 21 March 2022

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: We design a new algorithm for solving parametric systems having finitely many complex solutions for generic values of the parameters. More precisely, let $f=(f_1,ldots,f_m)subsetmathbbQ[y][x]$ with $y=(y_1,ldots,y_t)$ and $x=(x_1,ldots,x_n)$, $Vsubsetmathbb{C}^{t+n}$ be the algebraic set defined by $f$ and $pi$ be the projection $(y,x)oy$. Under the assumptions that $f$ admits finitely many complex roots for generic values of $y$ and that the ideal generated by $f$ is radical, we solve the following problem. On input $f$, we compute semi-algebraic formulas defining semi-algebraic subsets $S_1,ldots,S_l$ of the $y$-space such that $cu{p}_{i=1}^l{S}_i$ is dense in $mathbb{R}^t$ and the number of real points in $Vcapp{i}^{-1}(eta)$ is invariant when $eta$ varies over each $S_i$. This algorithm exploits properties of some well chosen monomial bases in the algebra $mathbbQ(y)[x]/I$ where $I$ is the ideal generated by $f$ in $mathbbQ(y)[x]$ and the specialization property of the so-called Hermite matrices. This allows us to obtain compact representations of the sets $S_i$ by means of semi-algebraic formulas encoding the signature of a symmetric matrix. When $f$ satisfies extra genericity assumptions, we derive complexity bounds on the number of arithmetic operations in $mathbbQ$ and the degree of the output polynomials. Let $d$ be the maximal degree of the $f_i$'s and $D=n(d-1)d^n$, we prove that, on a generic $f=(f_1,ldots,f_n)$, one can compute those semi-algebraic formulas with $$ operations in $mathbbQ$ and that the polynomials involved have degree bounded by $D$. We report on practical experiments which illustrate the efficiency of our algorithm on generic systems and systems from applications. It allows us to solve problems which are out of reach of the state-of-the-art.

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

Recommendations

• Solving parametric polynomial systems
• scientific article; zbMATH DE number 1263377
• Complexity of solving parametric polynomial systems
• Complexity of the resolution of parametric systems of polynomial equations and inequations
• Hermite's method of separation of solutions of systems of algebraic equations and its applications

zbMATH Keywords

computational algebraic geometryreal algebraic geometrypolynomial systemsreal rootssemialgebraic sets

Mathematics Subject Classification ID

Semialgebraic sets and related spaces (14P10) Computational aspects and applications of commutative rings (13P99) Computational real algebraic geometry (14Q30) Real and complex fields (12Dxx)

Cites Work

• FGb: A Library for Computing Gröbner Bases
• A complete algorithm for automated discovering of a class of inequality-type theorems
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Classification of the perspective-three-point problem, discriminant variety and real solving polynomial systems of inequalities
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• Solving zero-dimensional systems through the rational univariate representation
• Computing parametric geometric resolutions
• Title not available (Why is that?)
• Sharp estimates for triangular sets
• A Gröbner free alternative for polynomial system solving
• An open problem on metric invariants of tetrahedra
• Solving parametric polynomial systems
• A theorem on refining division orders by the reverse lexicographic order
• Degrevlex Gröbner bases of generic complete intersections.
• Title not available (Why is that?)
• On the complexity of the generalized MinRank problem
• Basic algebraic geometry 1. Varieties in projective space. Translated from the Russian by Miles Reid
• Real quantifier elimination is doubly exponential
• Title not available (Why is that?)
• Title not available (Why is that?)
• Semi-Algebraic Local-Triviality in Semi-Algebraic Mappings
• The complexity of quantifier elimination and cylindrical algebraic decomposition
• Generic sequences of polynomials
• On the stability of Gröbner bases under specializations
• On the complexity of the \(F_5\) Gröbner basis algorithm
• A package for solving parametric polynomial systems
• Automated Deduction in Geometry
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• On the bit complexity of finding points in connected components of a smooth real hypersurface
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Plane geometry and convexity of polynomial stability regions
• Equi-Cevaline points of triangles
• Signatures in algebra, topology and dynamics
• Determinantal Sets, Singularities and Application to Optimal Control in Medical Imagery
• Smooth points on semi-algebraic sets

Cited In (3)

• Machine learning the real discriminant locus
• On real roots counting for non-radical parametric ideals
• Semi-algebraic description of the equilibria of dynamical systems

Uses Software

• FGb
• Kronecker
• RAGlib
• DISCOVERER
• ISOLATE

This page was built for publication: Solving parametric systems of polynomial equations over the reals through Hermite matrices

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