ID: math/9809071

Solving Degenerate Sparse Polynomial Systems Faster

September 14, 1998

View on ArXiv

Similar papers 3

A Polyhedral Method to Compute All Affine Solution Sets of Sparse Polynomial Systems

October 15, 2013

86% Match
Danko Adrovic, Jan Verschelde
Symbolic Computation
Algebraic Geometry
Combinatorics

To compute solutions of sparse polynomial systems efficiently we have to exploit the structure of their Newton polytopes. While the application of polyhedral methods naturally excludes solutions with zero components, an irreducible decomposition of a variety is typically understood in affine space, including also those components with zero coordinates. We present a polyhedral method to compute all affine solution sets of a polynomial system. The method enumerates all factors ...

Find SimilarView on arXiv

Yet another eigenvalue algorithm for solving polynomial systems

May 18, 2021

86% Match
Matías R. Bender, Simon Telen
Numerical Analysis
Numerical Analysis
Symbolic Computation
Algebraic Geometry

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. We design an algorithm which solves systems with isolated solutions reliably and efficiently. In overdetermined cases, it reduces the task to an eigenvalue problem in a simpler and considerably faster way than in previous methods, and it can outperform the homotopy continuation approach. We provide many examples...

Find SimilarView on arXiv

Solving polynomial systems via homotopy continuation and monodromy

September 28, 2016

86% Match
Timothy Duff, Cvetelina Hill, Anders Jensen, Kisun Lee, ... , Sommars Jeff
Algebraic Geometry
Mathematical Software

We study methods for finding the solution set of a generic system in a family of polynomial systems with parametric coefficients. We present a framework for describing monodromy based solvers in terms of decorated graphs. Under the theoretical assumption that monodromy actions are generated uniformly, we show that the expected number of homotopy paths tracked by an algorithm following this framework is linear in the number of solutions. We demonstrate that our software implem...

Find SimilarView on arXiv

Toric Eigenvalue Methods for Solving Sparse Polynomial Systems

June 18, 2020

86% Match
Matías R. Bender, Simon Telen
Algebraic Geometry
Symbolic Computation

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 ...

Find SimilarView on arXiv

Solving sparse polynomial systems using Groebner bases and resultants

May 19, 2022

86% Match
Matías R. Bender
Symbolic Computation
Algebraic Geometry

Solving systems of polynomial equations is a central problem in nonlinear and computational algebra. Since Buchberger's algorithm for computing Gr\"obner bases in the 60s, there has been a lot of progress in this domain. Moreover, these equations have been employed to model and solve problems from diverse disciplines such as biology, cryptography, and robotics. Currently, we have a good understanding of how to solve generic systems from a theoretical and algorithmic point of ...

Find SimilarView on arXiv

Numerically computing real points on algebraic sets

May 31, 2011

85% Match
Jonathan D. Hauenstein
Algebraic Geometry
Numerical Analysis

Given a polynomial system f, a fundamental question is to determine if f has real roots. Many algorithms involving the use of infinitesimal deformations have been proposed to answer this question. In this article, we transform an approach of Rouillier, Roy, and Safey El Din, which is based on a classical optimization approach of Seidenberg, to develop a homotopy based approach for computing at least one point on each connected component of a real algebraic set. Examples are p...

Find SimilarView on arXiv

A General Solver Based on Sparse Resultants

January 27, 2012

85% Match
Ioannis Z. Emiris
Symbolic Computation
Numerical Analysis
Commutative Algebra

Sparse (or toric) elimination exploits the structure of polynomials by measuring their complexity in terms of Newton polytopes instead of total degree. The sparse, or Newton, resultant generalizes the classical homogeneous resultant and its degree is a function of the mixed volumes of the Newton polytopes. We sketch the sparse resultant constructions of Canny and Emiris and show how they reduce the problem of root-finding to an eigenproblem. A novel method for achieving this ...

Find SimilarView on arXiv

Polynomial Equations: Theory and Practice

October 10, 2022

85% Match
Simon Telen
Algebraic Geometry
Numerical Analysis
Numerical Analysis
Optimization and Control

Solving polynomial equations is a subtask of polynomial optimization. This article introduces systems of such equations and the main approaches for solving them. We discuss critical point equations, algebraic varieties, and solution counts. The theory is illustrated by many examples using different software packages.

Find SimilarView on arXiv

Paramotopy: Parameter homotopies in parallel

April 11, 2018

85% Match
Daniel J. Bates, Danielle Brake, Matthew Niemerg
Algebraic Geometry

Numerical algebraic geometry provides a number of efficient tools for approximating the solutions of polynomial systems. One such tool is the parameter homotopy, which can be an extremely efficient method to solve numerous polynomial systems that differ only in coefficients, not monomials. This technique is frequently used for solving a parameterized family of polynomial systems at multiple parameter values. Parameter homotopies have recently been useful in several areas of a...

Find SimilarView on arXiv

Polar Varieties and Efficient Real Equation Solving: The Hypersurface Case

September 6, 1996

85% Match
B. Bank, M. Giusti, J. Heintz, ... , Mbakop G. M.
Algebraic Geometry

The objective of this paper is to show how the recently proposed method by Giusti, Heintz, Morais, Morgenstern, Pardo \cite{gihemorpar} can be applied to a case of real polynomial equation solving. Our main result concerns the problem of finding one representative point for each connected component of a real bounded smooth hypersurface. The algorithm in \cite{gihemorpar} yields a method for symbolically solving a zero-dimensional polynomial equation system in the affine (and ...

Find SimilarView on arXiv