Email this article 
THE NEW IS THE WELL-FORGOTTEN OLD — F4 ALGORITHM OPTIMIZATION
- Authors: Styopkin S.M.1
-
Affiliations:
- Yandex
- Issue: Vol 65, No 3 (2025)
- Pages: 338-346
- Section: Optimal control
- URL: https://journals.rcsi.science/0044-4669/article/view/293543
- DOI: https://doi.org/10.31857/S0044466925030082
- EDN: https://elibrary.ru/HSPLUZ
- ID: 293543
Cite item
Open Access
Access granted
Subscription Access
Abstract
The Grobner basis is a fundamental concept in computational algebra. F4 is one of the fastest algorithms for computing Grobner basis. In this paper, we will discuss the process of writing effective F4. Despite the fact that this work focuses on algorithms from computational algebra, some of the results and ideas presented here may have broader applications beyond this specific subject area. In general, the theory described below can be regarded as an abstraction, as it progresses through the text. This is because the text is not actually about the F4 algorithm itself, but rather about the power of profiling, unconventional techniques, and selecting the appropriate memory model. We will provide examples of inefficient usage of the standard library, recall the fundamental principles of optimization in order to apply them as efficiently as possible to obtain the fastest F4 algorithm, using non-traditional approaches.
Keywords
References
- Buchberger B. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal // Ph. D. Thesis, Math. Inst., University of Innsbruck, 1965.
- Faugere J. C. A new efficient algorithm for computing Gro¨bner bases (F4) // J. of pure and applied algebra. 1999. V. 139. № 1–3. P. 61–88.
- Boyer B. GBLA: Gro¨bner basis linear algebra package // Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. 2016. P. 135–142.
- Perry J. An extension of Buchberger’s criteria for Gro¨bner basis decision // LMS Journal of Computation and Mathematics. 2010. V. 13. P. 111–129.
- Peifer D. The F4 Algorithm. 2017.
- Gebauer R., Moller H. M. On an installation of Buchberger’s algorithm // J. of Symbolic computation. 1988. V. 6. № 2–3. P. 275–286.
- Hong H., Perry J. Are Buchberger’s criteria necessary for the chain condition? // J. of Symbolic Computation. 2007. V. 42. № 7. P. 717–732.
- Hong H., Perry J. Corrigendum to? Are Buchberger? s criteria necessary for the chain condition?? // J. of Symbolic Computation. 2008. V. 43. № 3. P. 233.
- Dube T. W. The structure of polynomial ideals and Gro¨bner bases // SIAM Journal on Computing. 1990. V. 19. № 4. P. 750–773.
- Mayr E. W., Meyer A. R. The complexity of the word problems for commutative semigroups and polynomial ideals // Advances in mathematics. 1982. V. 46. № 3. P. 305–329.
Supplementary files
