Parallelization of Modular Algorithms
Parallelization of Modular Algorithms
复制标题
模块化算法的并行化
DOI：
10.1016/j.jsc.2011.01.003
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Steidel
中科院分区：
文献类型：
--
作者：
Nazeran Idrees;G. Pfister;S. Steidel
本文研究了两种模算法的并行化问题。事实上，我们考虑了Gröbner基的模计算(Resp.标准基)和零维理想的相关素数的模计算，并用奇异描述它们的并行实现。我们求解Q上问题的模算法主要由三部分组成：对多个素数p取模p的问题，应用中国剩余算法将结果提升到q。合理重建)，以及验证。Arnold利用Hilbert函数证明了对于齐次理想，计算Gröbner基的模算法中的验证部分可以简化。阿诺德，2003)。使用希尔伯特-塞缪尔函数，证明的思想可以很容易地适用于局部情况，即局部排序，而不一定是齐次理想。Pfister，2007)。本文在整体序的情况下，证明了非齐次理想的相应定理。
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 for solving problems over Q mainly consist of three parts: solving the problem modulo p for several primes p, lifting the result to Q by applying the Chinese remainder algorithm (resp. rational reconstruction), and verification. Arnold proved using the Hilbert function that the verification part in the modular algorithm for computing Gröbner bases can be simplified for homogeneous ideals (cf. Arnold, 2003). 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. Pfister, 2007). In this paper we prove the corresponding theorem for non-homogeneous ideals in the case of a global ordering.