Solving decomposable sparse systems

DOI10.1007/S11075-020-01045-XzbMATH Open1473.65059arXiv2001.04228OpenAlexW3118309125MaRDI QIDQ2048838FDOQ2048838

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

Publication date: 24 August 2021

Published in: Numerical Algorithms (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

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)\)

Uses Software

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

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)