A fast algorithm for Gröbner basis conversion and its applications

DOI10.1006/JSCO.1999.0416MaRDI QIDQ1588033zbMATH OpenOpenAlexFDO

Authors Quoc-Nam Tran

Publication date 28 February 2001

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/389b985f9edcfe7f58ab1a95cb2b13381982462e

zbMATH Keywords

basic conversionGröbner walkterm orders

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Symbolic computation and algebraic computation (68W30)

Review text

The Gröbner walk method converts a Gröbner basis by partitioning the computation of the basis into several smaller computations following a path in the Gröbner fan of the ideal generated by the system of equations. Typically, the target point of the walking path leads to initial forms of great numbers of terms. Up to now, the best way to avoid this was to choose the point heuristically. In this paper, the author improves the Gröbner walk method by giving a deterministic procedure to vary this target point in order to ensure the generality of the position (that means that the initial forms have always a few terms). The author uses a bound for the total degree of the polynomials in a Gröbner basis due to \textit{T. W. Dubé} [SIAM J. Comput. 19, 750-773 (1990; Zbl 0697.68051)] and a result which relates weight vectors to term orders [\textit{D. Eisenbud}, Commutative algebra. With a view towards algebraic geometry, Graduate Texts Math. 150 (1995; Zbl 0819.13001)]. Then he proves the main theorem of the paper which states that, given any admisible term order, a particular weight vector which represents the Gröbner cone of an ideal with respect to this term order can be found deterministically. Afterwards, the author proposes an algorithm for basic conversion and shows many examples and applications of his method. The method is said to be much faster than the direct computation of the reduced Gröbner basis with respect to the pure lexicographic term order using Buchberger algorithm.

Recommendations

• On the walk
• Converting bases with the Gröbner walk
• The generic Gröbner walk
• scientific article; zbMATH DE number 1163445
• A randomized variant of the Gröbner Walk
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• scientific article; zbMATH DE number 1163429
• A modified LLL algorithm for change of ordering of Gröbner basis
• An extension of Buchberger's algorithm to compute all reduced Gröbner bases of a polynomial ideal
• scientific article; zbMATH DE number 4214184

Cites work

• Converting bases with the Gröbner walk
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Equations for the projective closure and effective Nullstellensatz
• Hilbert functions and the Buchberger algorithm
• scientific article; zbMATH DE number 3941661 (Why is no real title available?)
• scientific article; zbMATH DE number 1189068 (Why is no real title available?)
• scientific article; zbMATH DE number 1254280 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 1120551 (Why is no real title available?)
• scientific article; zbMATH DE number 967945 (Why is no real title available?)
• scientific article; zbMATH DE number 3036380 (Why is no real title available?)
• Implicit representation of parametric curves and surfaces
• On the complexity of Gröbner bases conversion
• Surface/surface intersection
• The orthocentric simplex as an extreme simplex
• The Structure of Polynomial Ideals and Gröbner Bases
• Tracing surface intersections

Cited in

(15)

• Converting bases with the Gröbner walk
• On the walk
• A comparison of unrestricted dynamic Gröbner basis algorithms
• Gröbner systems conversion
• A new Gröbner basis conversion method based on stabilization techniques
• Efficient Groebner walk conversion for implicitization of geometric objects
• Ideal-specific elimination orders form a star-shaped region
• A new class of term orders for elimination
• The generic Gröbner walk
• Universal characteristic decomposition of radical differential ideals
• Gröbner fans of \(x\)-homogeneous ideals in \(R [\![ t ]\!][x]\)
• A randomized variant of the Gröbner Walk
• scientific article; zbMATH DE number 1163445 (Why is no real title available?)
• Computing the radical of an ideal in positive characteristic
• A new algorithm for Gröbner bases conversion

This page was built for publication: A fast algorithm for Gröbner basis conversion and its applications

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