Solving parametric systems of polynomial equations over the reals through Hermite matrices. (September 2022)

• Record Type: Journal Article
• Authors: Le, Huu Phuoc; Safey El Din, Mohab
• Is Part Of: Journal of symbolic computation. Volume 112(2022)
• Page Start: 25
• Page End: 61
• Publication Date: 2022-09
• Subjects: Real algebraic geometry -- Polynomial system solving -- Real root classification -- Hermite quadratic forms -- Gröbner bases; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2021.12.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We design a new algorithm for solving parametric systems of equations having finitely many complex solutions for generic values of the parameters. More precisely, let f = ( f 1, …, f m ) ⊂ Q [ y ] [ x ] with y = ( y 1, …, y t ) and x = ( x 1, …, x n ), V ⊂ C t × C n be the algebraic set defined by the simultaneous vanishing of the f i 's and π be the projection ( y, x ) → y . Under the assumptions that f admits finitely many complex solutions when specializing y to generic values and that the ideal generated by f is radical, we solve the following algorithmic problem. On input f, we compute semi-algebraic formulas defining open semi-algebraic sets S 1, …, S ℓ in the parameters' space R t such that ∪ i = 1 ℓ S i is dense in R t and, for 1 ≤ i ≤ ℓ, the number of real points in V ∩ π − 1 ( η ) is invariant when η ranges over S i . This algorithm exploits special properties of some well chosen monomial bases in the quotient algebra Q ( y ) [ x ] / I where I ⊂ Q ( y ) [ x ] is the ideal generated by f in Q ( y ) [ x ] as well as the specialization property of the so-called Hermite matrices which represent Hermite's quadratic forms. This allows us to obtain "compact" representations of the semi-algebraic sets S i by means of semi-algebraic formulas encoding the signature of a given symmetric matrix. When f satisfies extra genericity assumptions (such as regularity), we use the theory of Gröbner bases to derive complexity bounds both on the number of arithmetic operations in Q and the degree of the output polynomials. More precisely, letting d be the maximal degrees of the f i 's and D = n ( d − 1 ) d n, we prove that, on a generic input f = ( f 1, …, f n ), one can compute those semi-algebraic formulas using O ˜ ( ( t + D t ) 2 3 t n 2 t + 1 d 3 n t + 2 ( n + t ) + 1 ) arithmetic operations in Q and that the polynomials involved in these formulas have degree bounded by D . We report on practical experiments which illustrate the efficiency of this algorithm, both on generic parametric systems and parametric systems coming from applications since it allows us to solve systems which were out of reach on the current state-of-the-art.