|Title||Computing border bases|
|Author(s)|| Achim Kehrein, Martin Kreuzer|
|Type||Article in Journal|
|Abstract||This 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.
|Keywords||border basis, Gröbner basis, Buchberger's algorithm, zero-dimensional ideal|
|Journal||Journal of Pure and Applied Algebra|