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

DOI10.1016/J.JSC.2021.12.002MaRDI QIDQ2117425zbMATH OpenOpenAlexWikidataFDO

Authors Huu Phuoc Le, Mohab Safey El Din

Publication date 21 March 2022

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

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

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)

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• ISOLATE
• DISCOVERER
• RAGlib
• Kronecker
• FGb

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)