The computation of Gröbner bases using an alternative algorithm

Publication date 30 January 2001

algebras of solvable type algorithms graded rings Gröbner bases polynomial ideals Pommaret bases term orders

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Ordinary and skew polynomial rings and semigroup rings (16S36) Graded rings and modules (associative rings and algebras) (16W50) Computational aspects of associative rings (general theory) (16Z05) Symbolic computation and algebraic computation (68W30)

Review text

The author presents a generalization of Pommaret bases to the class of algebras of solvable type. The notions of Pommaret bases and Gröbner bases are very closely related. Their principal difference lies in distinct notions of divisibility. Gröbner bases are connected with the ordinary notion of divisibility of the terms, (monomials of the polynomial ring). In order to define the notion of a Pommaret basis, let \(\sqsubseteq\) be an arbitrary linear order on the set \(X\) of variables, then \(u\mid_Pv\) iff there is \(s\) such that \(su=v\) and there is \(i\) between 1 and \(n\) such that all the letters appearing in \(s\) are smaller or equal to \(X_i\) and all the letters appearing in \(u\) are bigger or equal to \(X_i\), (with respect to the order \(\sqsubseteq\)). This order on \(X\) is not necessarily compatible with the term order. The following definition is usual, and central for the paper. Definition: Let \(I\subseteq R\) be an ideal (of the polynomial ring), \(F\subseteq I\) a subset of \(I\) and \(\prec\) an admissible term order. The subset \(F\) is called a Gröbner (resp. Pommaret) basis of \(I\) with respect to \(\prec\) if and only if for every \(0\neq g\in I\) there exists \(f\in F\) such that \(\text{lt}(f)\mid\text{lt}(g)\) (resp. \(\text{lt}(f)\mid_P\text{lt}(g)\)). These notions are extended for the class of algebras called algebras of solvable type. In order to do this the author looks at the associated graded ring with the ideal which defines the algebra of solvable type, the notion of Gröbner basis with respect to the graded structure is defined, and the notion of Pommaret basis is extended to this case. One of the main theorems of the paper is theorem 1, which relates Gröbner bases and Pommaret bases. An algorithm for computing Pommaret bases is given, and using it, the author gives an alternative algorithm for computing Gröbner bases. The paper also makes various discussions on the termination time of the algorithms, and ends with some very nice concluding remarks. For the entire collection see [Zbl 0897.00036].

Recommendations

Cited in

(11)

This page was built for publication: The computation of Gröbner bases using an alternative algorithm

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