Computing border bases

DOI10.1016/J.JPAA.2005.07.006MaRDI QIDQ819794zbMATH OpenOpenAlexFDO

Publication date 29 March 2006

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpaa.2005.07.006

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Numerical computation of solutions to systems of equations (65H10) Symbolic computation and algebraic computation (68W30)

Review text

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.

Recommendations

Cites work

Cited in

(34)

This page was built for publication: Computing border bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q819794)