Toric eigenvalue methods for solving sparse polynomial systems

DOI10.1090/MCOM/3744zbMATH Open1502.14122arXiv2006.10654OpenAlexW3035846117MaRDI QIDQ5097381FDOQ5097381

Authors: Matías R. Bender, Simon Telen 

Publication date: 23 August 2022

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: 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 appearing in our approach when $I$ is a complete intersection.

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

Recommendations

• A Polyhedral Method for Solving Sparse Polynomial Systems
• Polynomial eigenvalue solver based on tropically scaled Lagrange linearization
• scientific article; zbMATH DE number 2092194
• Polynomial eigenvalue problems: theory, computation, and structure
• scientific article; zbMATH DE number 3874487
• scientific article; zbMATH DE number 2142706
• Computing isolated roots of sparse polynomial systems in affine space
• Sparse tensor approximation of parametric eigenvalue problems
• Solving degenerate sparse polynomial systems faster
• Solving \(p\)-adic polynomial systems via iterative eigenvector algorithms

zbMATH Keywords

toric varietiesCox ringssymbolic-numeric algorithmsparse polynomial systemssolving polynomial systemseigenvalue theorem

Mathematics Subject Classification ID

Toric varieties, Newton polyhedra, Okounkov bodies (14M25) Numerical computation of solutions to systems of equations (65H10) Numerical computation of roots of polynomial equations (65H04)

Cites Work

• HomotopyContinuation.jl: a package for homotopy continuation in Julia
• 3264 and all that. A second course in algebraic geometry
• Title not available (Why is that?)
• Introduction to Toric Varieties. (AM-131)
• Title not available (Why is that?)
• Using Algebraic Geometry
• Condition. The geometry of numerical algorithms
• Numerically solving polynomial systems with Bertini
• Title not available (Why is that?)
• Title not available (Why is that?)
• Toric varieties
• Title not available (Why is that?)
• Gröbner bases of ideals defined by functionals with an application to ideals of projective points
• Title not available (Why is that?)
• Title not available (Why is that?)
• Numerical Polynomial Algebra
• Introduction to the solution of polynomial systems
• Multigraded regularity: syzygies and fat points
• Multigraded Hilbert functions and toric complete intersection codes
• Multigraded Castelnuovo-Mumford regularity
• An octanomial model for cubic surfaces
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• A Polyhedral Method for Solving Sparse Polynomial Systems
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Solving polynomial equations. Foundations, algorithms, and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of sparse elimination
• Title not available (Why is that?)
• Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems
• Matrices in elimination theory
• Solving a sparse system using linear algebra
• Castelnuovo Mumford regularity with respect to multigraded ideals
• Multigraded regularity: Coarsenings and resolutions
• Multigraded regularity, \(a^{*}\)-invariant and the minimal free resolution
• Codimension theorems for complete toric varieties
• Title not available (Why is that?)
• Applications of polynomial systems. With contributions by Carlos D'Andrea, Alicia Dickenstein, Jonathan Hauenstein, Hal Schenck, and Jessica Sidman
• The regularity of points in multi-projective spaces.
• Immaculate line bundles on toric varieties
• A stabilized normal form algorithm for generic systems of polynomial equations
• On the complexity of computing Gröbner bases for weighted homogeneous systems
• Solving polynomial systems via truncated normal forms
• Stickelberger and the Eigenvalue Theorem
• Virtual resolutions for a product of projective spaces
• Towards Mixed Gröbner Basis Algorithms
• Truncated normal forms for solving polynomial systems: generalized and efficient algorithms
• Numerical root finding via Cox rings
• Gröbner basis over semigroup algebras. Algorithms and applications for sparse polynomial systems
• Solving \(p\)-adic polynomial systems via iterative eigenvector algorithms

Cited In (9)

• Complexity of sparse polynomial solving: homotopy on toric varieties and the condition metric
• Toric Sylvester forms
• Title not available (Why is that?)
• Landau discriminants
• A Fast Algorithm for Computing Macaulay Null Spaces of Bivariate Polynomial Systems
• Polyhedral homotopies in Cox coordinates
• Dimension results for extremal-generic polynomial systems over complete toric varieties
• Solving a sparse system using linear algebra
• Polynomial families of quantum semisimple coajoint orbits via deformed quantum enveloping algebras

Uses Software

• HomotopyContinuation

This page was built for publication: Toric eigenvalue methods for solving sparse polynomial systems

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