Алгоритм FGLM
FGLM — один из основных алгоритмов , компьютерной алгебры названный в честь его создателей Фожера , Джанни , Лазара и Мора . Они представили свой алгоритм в 1993 году. Входными данными алгоритма является базис Грёбнера нульмерного идеала в кольце полиномов над полем относительно мономиального порядка и второго мономиального порядка . На выходе он возвращает базис Грёбнера идеала относительно второго порядка. Алгоритм является фундаментальным инструментом компьютерной алгебры и реализован в большинстве систем компьютерной алгебры . Сложность равна FGLM O ( nD 3 ), где n — количество переменных многочленов, а D — степень идеала. [1] Существует несколько обобщений и различных применений FGLM. [2] [3] [4] [5] [6]
Ссылки
[ редактировать ]- ^ Ж. К. Фожер; П. Джанни; Д. Лазард; Т. Мора (1993). «Эффективное вычисление нульмерных базисов Грёбнера путем изменения порядка» . Журнал символических вычислений . 16 (4): 329–344. дои : 10.1006/jsco.1993.1051 .
- ^ Миддеке, Йоханнес (1 января 2012 г.). «Вычислительный взгляд на нормальные формы матриц рудных полиномов». ACM-коммун. Вычислить. Алгебра . 45 (3/4): 190–191. дои : 10.1145/2110170.2110182 . ISSN 1932-2240 . S2CID 14396484 .
- ^ Гердт, вице-президент; Янович, Д.А. (01 марта 2003 г.). «Реализация алгоритма FGLM и поиск корней полиномиальных инволютивных систем». Программирование и компьютерное программное обеспечение . 29 (2): 72–74. дои : 10.1023/А:1022992514981 . ISSN 0361-7688 . S2CID 17851647 .
- ^ Фожер, Жан-Шарль; Моу, Чэньци (01 мая 2017 г.). «Разреженные алгоритмы FGLM». Журнал символических вычислений . 80, Часть 3: 538–569. arXiv : 1304.1238 . дои : 10.1016/j.jsc.2016.07.025 . S2CID 149627 .
- ^ Ликарди, Сандра; Мора, Тео (1 января 1994 г.). «Имплицитизация гиперповерхностей и кривых с помощью Primbasissatz и преобразования базиса». Материалы международного симпозиума по символическим и алгебраическим вычислениям - ISSAC '94 . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 191–196. дои : 10.1145/190347.190416 . ISBN 978-0897916387 . S2CID 14584685 .
- ^ Борхес-Кинтана, М.; Борхес-Тренар, Массачусетс; Мартинес-Моро, Э. (20 февраля 2006 г.). «Общая основа применения методов FGLM к линейным кодам». Прикладная алгебра, алгебраические алгоритмы и коды, исправляющие ошибки . Конспекты лекций по информатике. Том. 3857. стр. 76–86. arXiv : math/0509186 . дои : 10.1007/11617983_7 . ISBN 978-3-540-31423-3 . S2CID 13427304 .