Stable normal forms for polynomial system solving

The 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 ones in [B. Mourrain, Ph. Trébuchet, Generalised normal forms and polynomial system solving, in: M. Kauers (Ed.), Proc. Intern. Symp. on Symbolic and Algebraic Computation, ACM Press, New-York, 2005, pp. 253–260]. This general border basis algorithm weakens the monomial ordering requirement for Gröbner bases computations. It is currently the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and a new representation that does 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 feature has a huge impact on practical efficiency, as illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.