Algorithm for efficiently computing a Groebner basis with high probability

高概率高效​​计算 Groebner 基的算法

• 批准号: 23654035
• 负责人: NORO Masayuki
• 金额: $ 1.58万
• 依托单位: Kobe University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Challenging Exploratory Research
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23654035/
• 关键词: 応用数学; 計算代数; グレブナー基底; モジュラー計算; 分散並列計算; modular計算; 有限体

We found that the cost of integer-rational number conversion in the procedure forcomputing Groebner bases over the rationals by combining modular Groebner bases by Chinese remainder theorem can be reduced by converting all the polynomials with the same degree together.In order to show the correctness of a Groebner basis candidate, we developed an algorithm which computes an exact generating relation for each element in the candidate. We first compute a generating relation over a finite field. Then we replace the coefficients with variables to obtain a huge system of linear equations. By using the information obtained by solving the system over the finite field, we can reduce the size of the system and the solution is made unique. Then we can apply Hensel lifting for solving the system and we can efficiently solve the system.

我们发现，通过中国剩余定理组合模Groebner基来计算有理数上的Groebner基的过程中，整数-有理数转换的成本可以通过将所有相同次数的多项式一起转换来减少。为了证明Groebner基候选的正确性，我们开发了一种算法，该算法为候选中的每个元素计算精确的生成关系。我们首先计算有限域上的生成关系。然后我们用变量代替系数，得到一个庞大的线性方程组。通过利用有限域上求解系统所获得的信息，我们可以减小系统的规模，并且使解唯一。然后，我们可以应用Hensel提升来求解该系统，我们可以有效地解决该系统。

项目成果

Groebner Bases - Statistics and Software Systems

Groebner 基地 - 统计和软件系统

• 发表时间: 2013
• 作者: M. Noro;et al
• 通讯作者: et al

Modular 計算の応用によるイデアル諸演算の計算法と検証法について

关于应用模计算的理想运算的计算和验证方法

• 发表时间: 2012
• 作者: S. Kinoshita;M. Iwamoto;K. Tateishi;N.J. Suematsu;and D. Ueyama;野呂正行
• 通讯作者: 野呂正行

グレブナー道場

格雷布纳道场

• 发表时间: 2011
• 作者: 野呂正行;他
• 通讯作者: 他

グレブナー基底候補の高速生成法とその検証について

Gröbner候选基的高速生成方法及其验证

• 发表时间: 2013
• 作者: 野呂正行;横山和弘
• 通讯作者: 横山和弘

matrix 1F1 が対角領域で満たす微分方程式系について

关于矩阵1F1在对角线区域满足的微分方程组

• 发表时间: 2013
• 作者: K. Suzuno;A. Tomoeda;and D. Ueyama;野呂正行
• 通讯作者: 野呂正行