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

Details:

 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 Length 20 File Language English Journal Journal of Pure and Applied Algebra Volume 205 Number 2 Pages 279-295 Publisher Elsevier Year 2006 Month May Edition 0 Translation No Refereed Yes
Webmaster