Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecomposable sparse polynomial systems
87
0
0.0
(
0
)
Added by
Frank Sottile
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Macaulay2 package DecomposableSparseSystems implements methods for studying and numerically solving decomposable sparse polynomial systems. We describe the structure of decomposable sparse systems and explain how the methods in this package may be used to exploit this structure, with examples.
rate research
Read More
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 Esterovs 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.
In latest years, several advancements have been made in symbolic-numerical eigenvalue techniques for solving polynomial systems. In this article, we add to this list by reducing the task to an eigenvalue problem in a considerably faster and simpler way than in previous methods. This results in an algorithm which solves systems with isolated solutions in a reliable and efficient way, outperforming homotopy methods in overdetermined cases. We provide an implementation in the proof-of-concept Julia package EigenvalueSolver.jl.
We consider the problem of computing homogeneous coordinates of points in a zero-dimensional subscheme of a compact, complex toric variety $X$. Our starting point is a homogeneous ideal $I$ in the Cox ring of $X$, which in practice might arise from homogenizing a sparse polynomial system. We prove a new eigenvalue theorem in the toric compact setting, which leads to a novel, robust numerical approach for solving this problem. Our method works in particular for systems having isolated solutions with arbitrary multiplicities. It depends on the multigraded regularity properties of $I$. We study these properties and provide bounds on the size of the matrices involved in our approach in the case where $I$ is a complete intersection.
We propose a new algorithm for numerical path tracking in polynomial homotopy continuation. The algorithm is `robust in the sense that it is designed to prevent path jumping and in many cases, it can be used in (only) double precision arithmetic. It is based on an adaptive stepsize predictor that uses Pade techniques to detect local difficulties for function approximation and danger for path jumping. We show the potential of the new path tracking algorithm through several numerical examples and compare with existing implementations.
The usual univariate interpolation problem of finding a monic polynomial f of degree n that interpolates n given values is well understood. This paper studies a variant where f is required to be composite, say, a composition of two polynomials of degrees d and e, respectively, with de=n, and therefore d+e-1 given values. Some special cases are easy to solve, and for the general case, we construct a homotopy between it and a special case. We compute a geometric solution of the algebraic curve presenting this homotopy, and this also provides an answer to the interpolation task. The computing time is polynomial in the geometric data, like the degree, of this curve. A consequence is that for almost all inputs, a decomposable interpolation polynomial exists.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
