Solving Polynomial Systems via Truncated Normal Forms

DOI10.1137/17M1162433zbMATH Open1401.65054arXiv1711.04543WikidataQ129194210 ScholiaQ129194210MaRDI QIDQ4689237FDOQ4689237

Marc van Barel, Bernard Mourrain, Simon Telen

Publication date: 15 October 2018

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Abstract: We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C. We propose a general algebraic framework to find the solutions and to compute the structure of the quotient ring R/I from the null space of a Macaulay-type matrix. The affine dense, affine sparse, homogeneous and multi-homogeneous cases are treated. In the presented framework, the concept of a border basis is generalized by relaxing the conditions on the set of basis elements. This allows for algorithms to adapt the choice of basis in order to enhance the numerical stability. We present such an algorithm and show numerical results.

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

zbMATH Keywords

computational algebraic geometrynormal formspolynomial systemsresultantnumerical linear algebraMacaulay matrixmultiplication maps

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Computational aspects in algebraic geometry (14Q99) Numerical computation of roots of polynomial equations (65H04)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polymake and Lattice Polytopes
• Algorithm 795
• Introduction to Toric Varieties. (AM-131)
• Numerically solving polynomial systems with Bertini
• The Geometry of Syzygies
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Signature-based algorithms to compute Gröbner bases
• Numerical Polynomial Algebra
• Generalized normal forms and polynomial system solving
• A Link between the Canonical Decomposition in Multilinear Algebra and Simultaneous Matrix Diagonalization
• Introduction to the solution of polynomial systems
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Newton polytopes and the Bezout theorem
• A Poisson formula for the sparse resultant
• A criterion for detecting m-regularity
• Solving polynomial equations. Foundations, algorithms, and applications
• H-bases for polynomial interpolation and system solving
• Stable normal forms for polynomial system solving
• Polynomial Equations and Convex Polytopes
• Subdivision methods for solving polynomial equations
• Multivariate polynomial system solving using intersections of eigenspaces.
• Matrices in elimination theory
• A new algorithm for computing certified numerical approximations of the roots of a zero-dimensional system
• Solving projective complete intersection faster
• Resultant over the residual of a complete intersection.
• Numerical solution of bivariate and polyanalytic polynomial systems
• A stabilized normal form algorithm for generic systems of polynomial equations

Cited In (13)

• 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
• A Fast Algorithm for Computing Macaulay Null Spaces of Bivariate Polynomial Systems
• NORMAL BGG SOLUTIONS AND POLYNOMIALS
• Sparse resultant-based minimal solvers in computer vision and their connection with the action matrix
• Systems of Polynomial Equations, Higher-Order Tensor Decompositions, and Multidimensional Harmonic Retrieval: A Unifying Framework. Part II: The Block Term Decomposition
• A normal form algorithm for tensor rank decomposition
• Analysis of normal-form algorithms for solving systems of polynomial equations
• Truncated normal forms for solving polynomial systems: generalized and efficient algorithms
• Moment matrices, border bases and real radical computation
• Numerical root finding via Cox rings
• Title not available (Why is that?)
• Solving p-adic polynomial systems via iterative eigenvector algorithms

Uses Software

• PHCpack
• polymake
• Bertini
• Tensorlab

This page was built for publication: Solving Polynomial Systems via Truncated Normal Forms

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