Stable normal forms for polynomial system solving

Abstract

This paper describes and analyzes a method for computing border bases of a zero-dimensional ideal $I$. The criterion used in the computation involves specific commutation polynomials and leads to an algorithm and an implementation extending the one provided in [MT'05]. This general border basis algorithm weakens the monomial ordering requirement for \grob bases computations. It is up to date the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and new representation that do not fit into the previous categories. With this formalism we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This new feature for a symbolic algorithm has a huge impact on the practical efficiency as it is illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.

Cited by in corpus (12)

• Flat families by strongly stable ideals and a generalization of Groebner bases
• Stable polynomial division and essential normality of graded Hilbert modules
• Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization
• Truncated Normal Forms for Solving Polynomial Systems: Generalized and Efficient Algorithms
• The Hilbert scheme of points and its link with border basis
• Border bases and order ideals: a polyhedral characterization
• Toric Border Bases
• Recognizing Graph Theoretic Properties with Polynomial Ideals
• Unconstraint global polynomial optimization via Gradient Ideal
• Global Newton Iteration over Archimedean and non-Archimedean Fields
• Chapter 10: Algebraic Algorithms
• Border bases for lattice ideals