Academic
Publications
Computing border bases

Computing border bases,10.1016/j.jpaa.2005.07.006,Journal of Pure and Applied Algebra,Achim Kehrein,Martin Kreuzer

Computing border bases   (Citations: 17)
BibTex | RIS | RefWorks Download
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 σ and hence compute a border basis that contains the reduced σ-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.
Journal: Journal of Pure and Applied Algebra - J PURE APPL ALG , vol. 205, no. 2, pp. 279-295, 2006
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...This seriousness forced European researchers to study the so-called “border bases” [9,10,5], see also [2]...

    Tateaki Sasakiet al. Term Cancellations in Computing Floating-Point Gröbner Bases

    • ...We also generalize the Border Basis Algorithm ([9]) to the approximate setting and study the approximate membership problem for zero-dimensional polynomial ideals...
    • ...there exist close-by polynomials which define an ideal I P such that dimR(P/I) > 0), find a border basis of the smallest nearby ideal I. The idea to solve this task is similar to the idea underlying the approximate Buchberger-M¨oller algorithm: use the SVD to make the usual border basis algorithm (see [9], Props...
    • ...[9], Prop. 18) the vector space V is repeatedly replaced by...
    • ...The last ingredient we need is an approximate version of the computation of a stable span explained in [9], Prop...
    • ...Proof. The method of the proof of [9], Prop...
    • ...Combining the preceding steps, we can formulate an approximate version of the Border Basis Algorithm [9], Prop...
    • ...18 in [9] and to add the following observation: The set O of terms computed in step B6 is indeed an order ideal...
    • ...As mentioned in [9], this algorithm can be optimized substantially...
    • ...As mentioned in [9], this algorithm can be optimized substantially. In particular, the proof of [9], Prop...
    • ...This result is in good numerical agreement with the exact result in [9], Ex. 20...

    Daniel Heldtet al. Approximate computation of zero-dimensional polynomial ideals

    • ...Kehrein and Kreuzer, et al, gave characterizations of border bases in an algebraist’s view [7, 8]. Inspired by Faug`ere’s F4 and F5 [13, 14] and Mourrain’s generic algorithm [4], Kehrein and Kreuzer present an algorithm to compute border bases for zero dimensional ideals with respect to (abbr. w.r.t.) a specified term order [10]...
    • ...We remark that for a zero dimensional ideal I, the border basis in our definition is the same as that of [1, 7, 10] (with the relations discussed in remark 2.4)...
    • ...As for the difference between our algorithms and Kehrein and Kreuzer’s, one could reference Example 19 in [10]...

    Yufu Chenet al. Border bases of positive dimensional polynomial ideals

    • ...The Approximate Buchberger-Mller (ABM) algorithm is presented, a new algorithm derived from the classical BM algorithm - see [2], [8], and [1] - calculating Grbner -, Border - see [4], [5] - and Macaulay - see [9], [10] - Basis for the Approximate Vanishing Ideal...

    Hennie Poulisse. Computational communicative algebra

    • ...At that time, the notion of border basis was not fully established, and the following articles provided the first concise framework: [17, 18, 19, 22]...
    • ...For an extensive coverage of border bases we refer to [19, 17, 18, 22]...
    • ...For an extensive coverage of border bases we refer to [19, 17, 18, 22]. Our exposition here follows that of [18]...
    • ...Tn with tjLT(g) we have t 2 Og is a reduced ( -)Gröbner basis [18]...

    SEBASTIAN POKUTTAet al. ON THE CONNECTION OF THE SHERALI-ADAMS CLOSURE AND BORDER BASES

Sort by: