Computing border bases (Q819794)

The authors continue their investigation of border bases [see, e.g., J. Pure Appl. Algebra 196, No. 2--3, 251--270 (2005; Zbl 1081.13011)] of zerodimensional ideals. Although containing more elements, in many applications border bases are computationally more feasible than Gröbner bases. In FGLM-like Gröbner conversion algorithms border bases with respect to a ``hard'' term order are computed given a Gröbner basis with respect to a ``cheap'' term order. For an ideal \(I\) in a polynomial ring \(P=k[x_1,\dots,x_n]\) over a field \(k\), a minimal reduced Gröbner basis provides unique \(k\)-linear representations of non standard monomials \(m\in LT(I)\) as linear combinations of standard ones \(m\in O=T\setminus LT(I)\) in \(P/I\). Border bases generalize this approach to arbitrary order ideals \(O\subset T\) such that there is a \(k\)-linear decomposition \(P=I\oplus \langle O\rangle_k\). The main result of the paper under review is an algorithm, that computes a border basis \(G=\{g_1,\dots,g_\nu\}\) for a zerodimensional ideal \(I\) given by arbitrary generators \(F=\{f_1,\dots,f_s\}\) that, in particular, do not necessarily form a Gröbner basis with respect to another term order. It works roughly as follows: Fix a degree-compatible term order \(\sigma\). For finite dimensional \(k\)-subspaces \(W\subset L\subset P\) define \(W^+=W+x_1W+\dots+x_nW\), \(W_{i+1}=W_i^+\cap L\) and \(W_L=\bigcup_{i\geq 0} W_i\) the \(L\)-stable span of \(W\). A \(\sigma\)-reduced \(k\)-basis of \(W_L\) with pairwise different leading terms can be computed by induction on \(i\). This defines a notion of standard and non standard terms as usual. If applied to the \(k\)-span of \(F\) within the \(k\)-span \(L\) of \(T_{\leq d}\) for \(d\geq \max_{i=1,\dots,s}\deg(f_i)\) this yields an order ideal \(O\subset T_{\leq d}\) of standard terms. If its border \(\partial O\) is contained in \(L\) then the border basis is complete. Otherwise increase \(d\) and update the data. The algorithm terminates since \(I\) is (known to be) zerodimensional. Some improvements using spans within more tight hulls are discussed.