Solving decomposable sparse systems

DOI10.1007/S11075-020-01045-XMaRDI QIDQ2048838zbMATH OpenOpenAlexFDO

Authors Taylor Brysiewicz, Jose Israel Rodriguez, Thomas Yahl, Frank Sottile

Publication date 24 August 2021

Published in Numerical Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Galois grouphomotopy continuationsparse polynomial systems

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20)

Abstract: Amendola et al. proposed a method for solving systems of polynomial equations lying in a family which exploits a recursive decomposition into smaller systems. A family of systems admits such a decomposition if and only if the corresponding Galois group is imprimitive. When the Galois group is imprimitive we consider the problem of computing an explicit decomposition. A consequence of Esterov's classification of sparse polynomial systems with imprimitive Galois groups is that this decomposition is obtained by inspection. This leads to a recursive algorithm to solve decomposable sparse systems, which we present and give evidence for its efficiency.

Recommendations

• Decomposable sparse polynomial systems
• Affine solution sets of sparse polynomial systems
• Computing isolated roots of sparse polynomial systems in affine space
• Solving degenerate sparse polynomial systems faster
• Deformation techniques for sparse systems

Cites work

• scientific article; zbMATH DE number 5995255 (Why is no real title available?)
• scientific article; zbMATH DE number 50337 (Why is no real title available?)
• scientific article; zbMATH DE number 3479762 (Why is no real title available?)
• scientific article; zbMATH DE number 3514184 (Why is no real title available?)
• scientific article; zbMATH DE number 3992817 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• scientific article; zbMATH DE number 960150 (Why is no real title available?)
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Algorithm 795
• Algorithm 921: alphaCertified: certifying solutions to polynomial systems
• Coefficient-parameter polynomial continuation
• Computational invariant theory
• Finding all solutions to polynomial systems and other systems of equations
• Galois groups of enumerative problems
• Galois theory for general systems of polynomial equations
• Interfacing with PHCpack
• Mixed volume techniques for embeddings of Laman graphs
• Monodromy of projective curves
• Polyhedral end games for polynomial continuation
• Solving polynomial systems via homotopy continuation and monodromy
• The Cheater’s Homotopy: An Efficient Procedure for Solving Systems of Polynomial Equations
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• The number of roots of a system of equations
• Unmixing the mixed volume computation

Cited in

(7)

• Finding sparse systems of parameters
• Sparse trace tests
• Using monodromy to recover symmetries of polynomial systems
• Galois/Monodromy Groups for Decomposing Minimal Problems in 3D Reconstruction
• The Maximum Likelihood Degree of Sparse Polynomial Systems
• Decomposable sparse polynomial systems
• Classification of Schubert Galois groups in \(Gr(4, 9)\)

Describes a project that uses

Uses Software

• DecomposableSparseSystems
• libtropicana
• MonodromySolver
• PHCpack
• alphaCertified
• PHCpack

This page was built for publication: Solving decomposable sparse systems

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