Parallelization of Modular Algorithms
arXiv:1005.5663 · doi:10.1016/j.jsc.2011.01.003
Abstract
In this paper we investigate the parallelization of two modular algorithms. In fact, we consider the modular computation of Gröbner 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öbner 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.
16 pages
Cited by in corpus (7)
- Parallel algorithms for normalization
- Groebner bases of symmetric ideals
- Local to global algorithms for the Gorenstein adjoint ideal of a curve
- The use of Bad Primes in Rational Reconstruction
- Gröbner Bases over Algebraic Number Fields
- Modular Techniques for Effective Localization and Double Ideal Quotient
- On modular computation of Groebner bases with integer coefficients