Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleStable normal forms for polynomial system solving
Author(s) Bernard Mourrain, Philippe Trebuchet
TypeArticle in Journal
AbstractThe 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. 253260]. 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.
KeywordsMultivariate polynomial, Quotient algebra, Normal form, Border basis, Root-finding, Symbolic-numeric computation
URL http://www.sciencedirect.com/science/article/pii/S0304397508006427
JournalTheoretical Computer Science
Pages229 - 240
NoteSymbolic-Numerical Computations
Translation No
Refereed No