Signature-based algorithms have brought large improvements in the performances of Gr\"obner bases algorithms for polynomial systems over fields. Furthermore, they yield additional data which can be used, for example, to compute the module of syzygies of an ideal or to compute coefficients in terms of the input generators. In this paper, we examine two variants of Buchberger's algorithm to compute Gr\"obner bases over principal ideal domains, with the addition of signatures. The first one is adapted from Kandri-Rody and Kapur's algorithm, whereas the second one uses the ideas developed in the algorithms by L. Pan (1989) and D. Lichtblau (2012). The differences in constructions between the algorithms entail differences in the operations which are compatible with the signatures, and in the criteria which can be used to discard elements. We prove that both algorithms are correct and discuss their relative performances in a prototype implementation in Magma.


翻译:基于签名的算法大大改进了列列“ obner 基础算法” 的性能。 此外, 这些算法还生成了额外的数据, 可用于计算理想的相交单元或计算输入生成器的系数。 在本文中, 我们检查了布奇伯格的两种变式算法, 用于计算主要理想域的 Gr\ “ obner 基础, 并添加了签名 。 第一种算法根据Kandri- Rody 和 Kapur 的算法进行了修改, 而第二种算法使用了L. Pan (1989年) 和 D. Lichtblau (2012年) 的算法中形成的想法。 算法的构造差异导致与签名兼容的操作和可用于丢弃元素的标准的差异。 我们证明两种算法都是正确的, 并在Magma 的原型实施中讨论它们的相对性能 。

0
下载
关闭预览

相关内容

专知会员服务
161+阅读 · 2020年1月16日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
The Completion of Covariance Kernels
Arxiv
0+阅读 · 2021年7月15日
Learning in the Frequency Domain
Arxiv
11+阅读 · 2020年3月12日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员