Parallelization of modular algorithms
From MaRDI portal
Parallel numerical computation (65Y05) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Parallel algorithms in computer science (68W10) Numerical algorithms for computer arithmetic, etc. (65Y04) Software, source code, etc. for problems pertaining to commutative algebra (13-04)
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.
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
- 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?)
- A Singular Introduction to Commutative Algebra
- 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
- 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
- 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
(17)- Usage of modular techniques for efficient computation of ideal operations
- Computing and using minimal polynomials
- 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
- Gröbner bases of symmetric ideals
- Parallel algorithms for normalization
- Local to global algorithms for the Gorenstein adjoint ideal of a curve
- Verification of Gröbner basis candidates
- Modular computations of standard bases for subalgebras
- Solving via modular methods
- \textsf{f4ncgb}: high performance Gröbner basis computations in free algebras
- Ideals modulo a prime
- Theoretical and methodological bases of modular technology of parallel tabular computations using universal processors
- An \(\mathfrak{m}\)-adic algorithm for bivariate Gröbner bases
- The use of bad primes in rational reconstruction
- scientific article; zbMATH DE number 5799780 (Why is no real title available?)
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)
