Loading...
Please wait, while we are loading the content...
Similar Documents
A new efficient algorithm for computing Gröbner bases (F4)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Faugère, Jean-Charles |
| Copyright Year | 1999 |
| Abstract | 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 modulo p computations. |
| Starting Page | 61 |
| Ending Page | 88 |
| Page Count | 28 |
| File Format | PDF HTM / HTML |
| DOI | 10.1016/S0022-4049(99)00005-5 |
| Volume Number | 139 |
| Alternate Webpage(s) | https://www.risc.jku.at/research/theorema/Groebner-Bases-Bibliography/gbbib_files/publication_502.pdf |
| Alternate Webpage(s) | http://modular.fas.harvard.edu/129-05/refs/faugere_f4.pdf |
| Alternate Webpage(s) | https://doi.org/10.1016/S0022-4049%2899%2900005-5 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
