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

Details:

   
TitleComputing border bases
Author(s) Achim Kehrein, Martin Kreuzer
TypeArticle in Journal
AbstractThis paper presents several algorithms that compute border bases of a
zero-dimensional ideal. The first relates to the FGLM algorithm as it
uses a linear basis transformation. In particular, it is able to
compute border bases that do not contain a reduced Gröbner basis.
The second algorithm is based on a generic algorithm by Bernard
Mourrain originally designed for computing an ideal basis that need
not be a border basis. Our fully detailed algorithm
computes a border basis of a zero-dimensional
ideal from a given set of generators. To obtain concrete instructions
we appeal to a degree-compatible term ordering $\sigma$ and hence
compute a border basis that contains the reduced $\sigma$-Gröbner basis.
We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations
of the Border Basis Algorithm which reduce the dimensions of the
linear algebra subproblems.
Keywordsborder basis, Gröbner basis, Buchberger's algorithm, zero-dimensional ideal
Length20
File
LanguageEnglish
JournalJournal of Pure and Applied Algebra
Volume205
Number2
Pages279-295
PublisherElsevier
Year2006
MonthMay
Edition0
Translation No
Refereed Yes
Webmaster