Computing critical points for invariant algebraic systems. (May 2023)

• Record Type: Journal Article
• Authors: Faugère, Jean-Charles; Labahn, George; Safey El Din, Mohab; Schost, Éric; Vu, Thi Xuan
• Is Part Of: Journal of symbolic computation. Volume 116(2023)
• Page Start: 365
• Page End: 399
• Publication Date: 2023-05
• Subjects: Polynomial systems solving -- Invariant algebraic systems -- Determinantal systems -- Critical points -- Computational complexity; 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.2022.10.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: Let K be a field and ( f 1, …, f s, ϕ ) be multivariate polynomials in K [ x 1, …, x n ] (with s < n ) each invariant under the action of S n, the group of permutations of { 1, …, n } . We consider the problem of computing the critical points of ϕ restricted to the algebraic set V ( f ), where f = ( f 1, …, f s ) . This is the same as computing the points at which f vanishes and the Jacobian matrix associated to ( f 1, …, f s, ϕ ) is rank deficient, provided that this set is finite. We exploit the invariance properties of the input to split the solution space according to the orbits of S n . This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in d s, ( n + d d ) and ( n s + 1 ) where d is the maximum degree of the input polynomials. When d, s are fixed, this is polynomial in n while when s is fixed and d ≃ n this yields an exponential speed-up with respect to the usual polynomial system solving algorithms.