Parallelization of modular algorithms

DOI10.1016/J.JSC.2011.01.003MaRDI QIDQ2430024zbMATH OpenOpenAlexFDO

Authors Nazeran Idrees, Gerhard Pfister, Stefan Steidel

Publication date 5 April 2011

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

Full work available at URL https://arxiv.org/abs/1005.5663

zbMATH Keywords

decompositionGröbner basesmodular computationparallel computation

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to commutative algebra (13-04) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Numerical algorithms for computer arithmetic, etc. (65Y04) Parallel numerical computation (65Y05) Parallel algorithms in computer science (68W10) Symbolic computation and algebraic computation (68W30)

Abstract: In this paper we investigate the parallelization of two modular algorithms. In fact, we consider the modular computation of Gr"obner bases (resp. standard bases) and the modular computation of the associated primes of a zero-dimensional ideal and describe their parallel implementation in SINGULAR. Our modular algorithms to solve problems over Q mainly consist of three parts, solving the problem modulo p for several primes p, lifting the result to Q by applying Chinese remainder resp. rational reconstruction, and a part of verification. Arnold proved using the Hilbert function that the verification part in the modular algorithm to compute Gr"obner bases can be simplified for homogeneous ideals (cf. cite{A03}). The idea of the proof could easily be adapted to the local case, i.e. for local orderings and not necessarily homogeneous ideals, using the Hilbert-Samuel function (cf. cite{Pf07}). In this paper we prove the corresponding theorem for non-homogeneous ideals in case of a global ordering.

Review text

The title is a bit of an understatement, the results are also interesting without parallelisation. First, a modular algorithm for the computation of Gröbner bases is given. Its correctness was shown in [\textit{E. A. Arnold}, ``Modular algorithms for computing Gröbner bases, J. Symb. Comput. 35, No. 4, 403-419 (2003; Zbl 1046.13018)] for the homegeneous case and in [\textit{G.-M. Greuel, G. Pfister}, A Singular Introduction to Commutative Algebra. Berlin: Springer. (2007; Zbl 1133.13001)] for local orderings; here the case of global orderings is treated. Also, the paper contains a modular algorithm for the computation of associated primes of zero-dimensional ideals.

Recommendations

• Parallel modular computation of Gröbner and involutive bases
• Extended parallelism in the Gröbner basis algorithm
• A parallel implementation of Buchberger's algorithm over \(\mathbb{Z}_p\) for \(p\leq 31991\)
• Strategy-accurate parallel Buchberger algorithms
• Parallelization of an algorithm for computation of involutive Janet bases

Cites work

• A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic \(n\)-roots
• A p-adic approach to the computation of Gröbner bases
• A Singular Introduction to Commutative Algebra
• Computing the primary decomposition of zero-dimensional ideals
• Direct methods for primary decomposition
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Gröbner bases and primary decomposition of polynomial ideals
• scientific article; zbMATH DE number 5509903 (Why is no real title available?)
• scientific article; zbMATH DE number 62658 (Why is no real title available?)
• scientific article; zbMATH DE number 177873 (Why is no real title available?)
• scientific article; zbMATH DE number 1302473 (Why is no real title available?)
• Localization and primary decomposition of polynomial ideals
• Mapping integers and Hensel codes onto Farey fractions
• Modular algorithms for computing Gröbner bases.
• On lucky ideals for Gröbner basis computations
• On lucky primes
• P-adic reconstruction of rational numbers
• Radical computations of zero-dimensional ideals and real root counting.
• Solving polynomial equations. Foundations, algorithms, and applications
• Some comments on the modular approach to Gröbner-bases

Cited in

(18)

• Parallel algorithms for normalization
• Usage of modular techniques for efficient computation of ideal operations
• Parallel modular computation of Gröbner and involutive bases
• Modular techniques for noncommutative Gröbner bases
• On the modular computation of Gröbner bases with integer coefficients
• Computing and using minimal polynomials
• Verification of Gröbner basis candidates
• scientific article; zbMATH DE number 5799780 (Why is no real title available?)
• Solving via modular methods
• Gröbner bases of symmetric ideals
• Local to global algorithms for the Gorenstein adjoint ideal of a curve
• Ideals modulo a prime
• Theoretical and methodological bases of modular technology of parallel tabular computations using universal processors
• The use of bad primes in rational reconstruction
• Modular computations of standard bases for subalgebras
• An \(\mathfrak{m}\)-adic algorithm for bivariate Gröbner bases
• \textsf{f4ncgb}: high performance Gröbner basis computations in free algebras
• Modular algorithms for computing Gröbner bases in free algebras

Describes a project that uses

Uses Software

• SymbolicData
• SINGULAR
• PoSSo
• modstd.lib
• assprimeszerodim.lib

This page was built for publication: Parallelization of modular algorithms

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