Numerical root finding via Cox rings

DOI10.1016/J.JPAA.2020.106367MaRDI QIDQ2173863zbMATH OpenOpenAlexFDO

Authors Simon Telen

Publication date 17 April 2020

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

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

zbMATH Keywords

Cox ringmultiplication matrixsystems of polynomial equationstoric varieties

Mathematics Subject Classification ID

Toric varieties, Newton polyhedra, Okounkov bodies (14M25) Geometric aspects of numerical algebraic geometry (14Q65) Numerical computation of roots of polynomial equations (65H04) Numerical computation of solutions to systems of equations (65H10) Numerical solution of nonlinear eigenvalue and eigenvector problems (65H17)

Abstract: We present a new eigenvalue method for solving a system of Laurent polynomial equations defining a zero-dimensional reduced subscheme of a toric compactification $X$ of $(mathbbCsetminus0{)}^n$. We homogenize the input equations to obtain a homogeneous ideal in the Cox ring of $X$ and generalize the eigenvalue, eigenvector theorem for rootfinding in affine space to compute homogeneous coordinates of the solutions. Several numerical experiments show the effectiveness of the resulting method. In particular, the method outperforms existing solvers in the case of (nearly) degenerate systems with solutions on or near the torus invariant prime divisors.

Recommendations

• Computing Cox rings
• Deterministic root finding in finite fields
• Algorithm for calculating the roots of polynomials with coefficients in the ring of polynomials over an arbitrary integral domain
• scientific article; zbMATH DE number 833249
• Roots and coefficients of polynomials over finite fields
• Polynomial root-finding and polynomiography
• Roots and coefficients of multivariate polynomials over finite fields
• scientific article; zbMATH DE number 1488179
• Fast computation of the roots of polynomials over the ring of power series

Cites work

• A global view of residues in the torus
• A Polyhedral Method for Solving Sparse Polynomial Systems
• A stabilized normal form algorithm for generic systems of polynomial equations
• Algorithm 795
• Gröbner basis over semigroup algebras. Algorithms and applications for sparse polynomial systems
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• scientific article; zbMATH DE number 108068 (Why is no real title available?)
• scientific article; zbMATH DE number 1263319 (Why is no real title available?)
• scientific article; zbMATH DE number 1263401 (Why is no real title available?)
• scientific article; zbMATH DE number 729195 (Why is no real title available?)
• scientific article; zbMATH DE number 1736029 (Why is no real title available?)
• scientific article; zbMATH DE number 1069614 (Why is no real title available?)
• scientific article; zbMATH DE number 1504686 (Why is no real title available?)
• scientific article; zbMATH DE number 939816 (Why is no real title available?)
• scientific article; zbMATH DE number 1827070 (Why is no real title available?)
• scientific article; zbMATH DE number 835749 (Why is no real title available?)
• Introduction to the solution of polynomial systems
• Introduction to Toric Varieties. (AM-131)
• Irrational mixed decomposition and sharp fewnomial bounds for tropical polynomial systems
• Macaulay style formulas for sparse resultants
• Matrices in elimination theory
• Multigraded Castelnuovo-Mumford regularity
• Multigraded Hilbert functions and toric complete intersection codes
• Multigraded regularity: syzygies and fat points
• Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems
• Numerical algebraic geometry and algebraic kinematics
• Numerical solution of bivariate and polyanalytic polynomial systems
• Numerically solving polynomial systems with Bertini
• Polyhedral end games for polynomial continuation
• Polymake and Lattice Polytopes
• Polynomial Equations and Convex Polytopes
• Solving a sparse system using linear algebra
• Solving degenerate sparse polynomial systems faster
• Solving polynomial equations. Foundations, algorithms, and applications
• Solving polynomial systems by polyhedral homotopies
• Solving polynomial systems via truncated normal forms
• Stable normal forms for polynomial system solving
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Toric residue and combinatorial degree
• Toric varieties
• Towards Mixed Gröbner Basis Algorithms

Cited in

(8)

• Landau discriminants
• Systems of polynomial equations, higher-order tensor decompositions, and multidimensional harmonic retrieval: a unifying framework. Part I: the canonical polyadic decomposition
• Toric eigenvalue methods for solving sparse polynomial systems
• Koszul-type determinantal formulas for families of mixed multilinear systems
• Bayesian Integrals on Toric Varieties
• Polyhedral homotopies in Cox coordinates
• A normal form algorithm for tensor rank decomposition
• Yet another eigenvalue algorithm for solving polynomial systems

Describes a project that uses

Uses Software

• Macaulay2
• rootsb
• PHCpack
• Bertini

This page was built for publication: Numerical root finding via Cox rings

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