Отправить статью по E-mail 
НОВОЕ — ЭТО ХОРОШО ЗАБЫТОЕ СТАРОЕ. ОПТИМИЗАЦИЯ АЛГОРИТМА F4
- Авторы: Стёпкин С.М.1
-
Учреждения:
- Яндекс
- Выпуск: Том 65, № 3 (2025)
- Страницы: 338-346
- Раздел: ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
- URL: https://ogarev-online.ru/0044-4669/article/view/293543
- DOI: https://doi.org/10.31857/S0044466925030082
- EDN: https://elibrary.ru/HSPLUZ
- ID: 293543
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Базис Грёбнера — фундаментальное понятие в вычислительной алгебре. F4 — один из самых быстрых алгоритмов для вычисления базиса Грёбнера. В этой статье мы обсудим процесс написания эффективного алгоритма F4 с нуля. Несмотря на то, что работа посвящена алгоритмам из области вычислительной алгебры, некоторые из представленных здесь результатов и идей могут иметь применение за пределами предметной области. В целом, теорию, описанную ниже, можно рассматривать как абстракцию, по мере ее продвижения по тексту. Это связано с тем, что в тексте на самом деле речь идет не о самом алгоритме F4, а скорее о возможностях профилирования, нетрадиционных методах и выборе подходящей модели памяти. Мы приведем примеры неэффективного использования стандартной библиотеки, напомним фундаментальные принципы оптимизации, и постараемся максимально эффективно применить их для реализации самого быстрого алгоритма F4, используя нетрадиционные подходы. Библ. 10. Фиг. 5. Табл. 1.
Ключевые слова
Список литературы
- 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.
Дополнительные файлы
