A new efficient algorithm for computing Grobner bases (F4)
A new efficient algorithm for computing Grobner bases (F4)
复制标题
DOI：
10.1016/s0022-4049(99)00005-5
复制
发表时间：
1999-06-17
影响因子：
0.8
通讯作者：
Faugére, JC
中科院分区：
文献类型：
--
作者：
Faugére, JC
本文介绍一种新的计算Grobner基的有效算法。为了避免尽可能多的中间计算，该算法计算连续截断Grobner基地，它取代了经典的多项式减少发现在Buchberger算法的同时减少几个多项式。这种强大的减少机制是通过符号预计算和稀疏线性代数方法的广泛使用。本文综述了当前计算机代数中使用的线性代数技术以及来自数值领域的其他方法。一些以前难以处理的问题（循环9），以及经验比较的第一个实现该算法与其他知名的程序。这种比较非常注意方法问题。本文中使用的所有基准测试和CPU时间都经常更新，并可在Web页面上获得。即使新算法没有改善最坏情况下的复杂度，它是几倍的速度比以前的实现整数和模p计算。(C)1999年由Elsevier Science B.V.出版，版权所有。
This paper introduces a new efficient algorithm for computing Grobner bases. To avoid as much intermediate computation as possible, the algorithm computes successive truncated Grobner bases and it replaces the classical polynomial reduction found in the Buchberger algorithm by the simultaneous reduction of several polynomials. This powerful reduction mechanism is achieved by means of a symbolic precomputation and by extensive use of sparse linear algebra methods. Current techniques in linear algebra used in Computer Algebra are reviewed together with other methods coming from the numerical field. Some previously untractable problems (Cyclic 9) are presented as well as an empirical comparison of a first implementation of this algorithm with other well known programs. This comparison pays careful attention to methodology issues. All the benchmarks and CPU times used in this paper are frequently updated and available on a Web page. Even though the new algorithm does not improve the worst case complexity it is several times faster than previous implementations both for integers and module p computations. (C) 1999 Published by Elsevier Science B.V. All rights reserved.