Extended parallelism in the Gröbner basis algorithm

DOI10.1007/BF01379314MaRDI QIDQ685087zbMATH OpenOpenAlexFDO

Authors Stephen A. Schwab

Publication date 30 September 1993

Published in International Journal of Parallel Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01379314

zbMATH Keywords

Buchberger algorithmGröbner basesparallelismshared memory multiprocessors

Mathematics Subject Classification ID

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

Review text

The author presents an implementation of the Buchberger algorithm to compute Gröbner bases of an ideal in the polynomial ring utilizing two different forms of parallelism. A course-grain technique which expands and reduces \(S\)-polynomials in parallel and a fine-grain technique which uses reduction pipelines. An analysis of the implementation and a comparison to other parallel implementations is given.

Recommendations

• A parallel implementation of Buchberger's algorithm over \(\mathbb{Z}_p\) for \(p\leq 31991\)
• Parallel reduction of matrices in Gröbner bases computations
• Strategy-accurate parallel Buchberger algorithms
• Parallelization of the Buchberger algorithm
• scientific article; zbMATH DE number 1254280

Cites work

• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
• scientific article; zbMATH DE number 3649988 (Why is no real title available?)
• scientific article; zbMATH DE number 1273640 (Why is no real title available?)
• Notes on Gröbner bases
• On an installation of Buchberger's algorithm
• Some examples for solving systems of algebraic equations by calculating Gröbner bases
• The complexity of the word problems for commutative semigroups and polynomial ideals

Cited in

(21)

• A parallel implementation of Buchberger's algorithm over \(\mathbb{Z}_p\) for \(p\leq 31991\)
• A new efficient algorithm for computing Gröbner bases (F₄)
• Parallel computation of Gröbner bases on distributed memory machines
• Parallelization of an algorithm for computation of involutive Janet bases
• Continuously parameterized symmetries and Buchberger's algorithm
• Parallelization of the Buchberger algorithm
• Parallel modular computation of Gröbner and involutive bases
• Threaded Gröbner bases: a Macaulay2 package
• Construction of algorithms for parallel addition in expanding bases via extending window method
• Parallelization of modular algorithms
• Parallel algorithms for Gröbner-basis construction
• Parallel computation of Janet and Gröbner bases over rational numbers
• Parallel reduction of matrices in Gröbner bases computations
• scientific article; zbMATH DE number 1241620 (Why is no real title available?)
• scientific article; zbMATH DE number 1254280 (Why is no real title available?)
• Efficient techniques for performing an irregular computation on distributed memory machines
• scientific article; zbMATH DE number 1163445 (Why is no real title available?)
• On the correctness of a distributed memory Gröbner basis algorithm
• Massively parallel methods for free resolutions
• A MIMD implementation of the Buchberger algorithm for Boolean polynomials
• Efficiency estimate for distributed computation of Gröbner bases and involutive bases

Describes a project that uses

Uses Software

• PROTEUS

This page was built for publication: Extended parallelism in the Gröbner basis algorithm

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