Modular Algorithms for Computing Minimal Associated Primes and Radicals of Polynomial Ideals
Modular Algorithms for Computing Minimal Associated Primes and Radicals of Polynomial Ideals
复制标题
计算多项式理想的最小关联素数和根式的模块化算法
DOI：
10.1145/3208976.3209014
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Noro Masayuki
中科院分区：
文献类型：
--
作者：
Aoyama Toru;Noro Masayuki
本文提出了计算域Q上多项式环中理想的极小伴随素元和域上多项式环中理想的根的算法。他们将中国剩余定理（CRT）应用于Laplagne算法，该算法计算最小相关素数而不产生冗余分量并计算根式。CRT从一个对象在商环模某些理想中的模象重构一个对象。在Laplagne算法中，理想通过将某些变量作为参数而在有理函数域上分解。在我们的新算法中，我们计算了给定理想I=的最小伴随素数和< φ（G）>的根< G >，其中φ是参数的替换映射.然后，我们通过对< φ（G）>的极小相伴素数和根应用CRT，构造了I的极小相伴素数和根的候选者。为了使这种方法正确地工作，每个模分量的形状必须与理想的相应分量的形状相一致，以计算最小相关素数，并且给定理想的模图像的根必须与给定理想的根的模图像相一致，以进行根计算。前者以高概率实现，因为在Q上的多元不可约多项式在以高概率用整数替换变量之后保持不可约，而后者除了有限数目的模之外都实现。
In this paper, we propose algorithms for computing minimal associated primes of ideals in polynomial rings over Q and computing radicals of ideals in polynomial rings over a field. They apply Chinese Remainder Theorem (CRT) to Laplagne's algorithm which computes minimal associated primes without producing redundant components and computes radicals. CRT reconstructs an object in a ring from its modular images in the quotient rings modulo some ideals. In Laplagne's algorithm, ideals are decomposed over rational function fields by regarding some variables as parameters. In our new algorithms, we compute the minimal associated primes and the radical of < φ(G) > for a given ideal I= < G >, where φ is a substitution map for a parameter. Then we construct candidates of the minimal associated primes and the radical of I by applying CRT for those of < φ(G) >'s. In order for this method to work correctly, the shape of each modular component must coincide with that of the corresponding component of the ideal for computations of minimal associated primes, and radicals of modular images of given ideals must coincide with modular images of radicals of given ideals for radical computations. The former is realized with a high probability because a multivariate irreducible polynomial over Q remains irreducible after a substitution of integers for variables with a high probability and the latter is realized except for a finite number of moduli.
登录
查看更多内容
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Shohei Tateishi;Hidetoshi Matsui and Sadanori Konishi;K. Yokoyama
通讯作者：
K. Yokoyama
模块化算法的并行化
DOI：
10.1016/j.jsc.2011.01.003
发表时间：
2010
期刊：
J. Symb. Comput.
影响因子：
--
作者：
Nazeran Idrees;G. Pfister;S. Steidel
通讯作者：
S. Steidel
论 Gröbner 基础计算的幸运理想
DOI：
10.1016/0747-7171(92)90018-y
发表时间：
1992
期刊：
J. Symb. Comput.
影响因子：
--
作者：
G. Pauer
通讯作者：
G. Pauer
DOI：
--
发表时间：
2006
期刊：
--
影响因子：
--
作者：
Santiago Laplagne
通讯作者：
Santiago Laplagne