- Код статьи
- S0044466925030082-1
- DOI
- 10.31857/S0044466925030082
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 65 / Номер выпуска 3
- Страницы
- 338-346
- Аннотация
- Базис Грёбнера — фундаментальное понятие в вычислительной алгебре. F4 — один из самых быстрых алгоритмов для вычисления базиса Грёбнера. В этой статье мы обсудим процесс написания эффективного алгоритма F4 с нуля. Несмотря на то, что работа посвящена алгоритмам из области вычислительной алгебры, некоторые из представленных здесь результатов и идей могут иметь применение за пределами предметной области. В целом, теорию, описанную ниже, можно рассматривать как абстракцию, по мере ее продвижения по тексту. Это связано с тем, что в тексте на самом деле речь идет не о самом алгоритме F4, а скорее о возможностях профилирования, нетрадиционных методах и выборе подходящей модели памяти. Мы приведем примеры неэффективного использования стандартной библиотеки, напомним фундаментальные принципы оптимизации, и постараемся максимально эффективно применить их для реализации самого быстрого алгоритма F4, используя нетрадиционные подходы. Библ. 10. Фиг. 5. Табл. 1.
- Ключевые слова
- вычислительная алгебра алгоритм F4 профилирование оптимизации
- Дата публикации
- 17.09.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 15
Библиография
- 1. Buchberger B. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal // Ph. D. Thesis, Math. Inst., University of Innsbruck, 1965.
- 2. 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.
- 3. 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.
- 4. 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.
- 5. Peifer D. The F4 Algorithm. 2017.
- 6. Gebauer R., Moller H. M. On an installation of Buchberger’s algorithm // J. of Symbolic computation. 1988. V. 6. № 2–3. P. 275–286.
- 7. Hong H., Perry J. Are Buchberger’s criteria necessary for the chain condition? // J. of Symbolic Computation. 2007. V. 42. № 7. P. 717–732.
- 8. 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.
- 9. Dube T. W. The structure of polynomial ideals and Gro¨bner bases // SIAM Journal on Computing. 1990. V. 19. № 4. P. 750–773.
- 10. 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.
