Алгоритм FGLM

FGLM является одним из основных алгоритмов в компьютерной алгебре , названных в честь его дизайнеров, Faugère , Джанни, Лазара и Мора . Они представили свой алгоритм в 1993 году. Входом алгоритма является базис Грёбнера нульмерного идеала в кольце многочленов над полем относительно мономиального порядка и второго мономиального порядка ; На выходе он возвращает базис Грёбнера идеала относительно второго порядка. Алгоритм является фундаментальным инструментом компьютерной алгебры и был реализован в большинствесистемы компьютерной алгебры . Сложность из FGLM является O ( нП ³ ), где п есть число переменных полиномов и D является степенью идеала. ^[1] Существует несколько обобщений и различных приложений для FGLM. ^[2]^[3]^[4]^[5]^[6]

Ссылки [ править ]

^ JC Faugère; П. Джанни; Д. Лазард; Т. Мора (1993). «Эффективное вычисление нульмерных базисов Гребнера путем изменения порядка». Журнал символических вычислений . 16 (4): 329–344. DOI : 10.1006 / jsco.1993.1051 .
^ Middeke, Johannes (2012-01-01). "Вычислительный взгляд на нормальные формы матриц многочленов Руды". ACM Commun. Comput. Алгебра . 45 (3/4): 190–191. DOI : 10.1145 / 2110170.2110182 . ISSN 1932-2240 .
^ Гердт, В.П .; Янович Д.А. (01.03.2003). «Реализация алгоритма FGLM и поиск корней полиномиальных инволютивных систем». Программирование и софт . 29 (2): 72–74. DOI : 10,1023 / A: 1022992514981 . ISSN 0361-7688 .
^ Faugère, Жан-Шарль; Мо, Ченци (2017-05-01). «Редкие алгоритмы FGLM». Журнал символических вычислений . 80, Часть 3: 538–569. arXiv : 1304.1238 . DOI : 10.1016 / j.jsc.2016.07.025 .
^ Licciardi, Сандра; Мора, Тео (1994-01-01). Неявность гиперповерхностей и кривых с помощью примбасиссаца и базисного преобразования . Труды Международного симпозиума по символьным и алгебраическим вычислениям . ISSAC '94. Нью-Йорк, Нью-Йорк, США: ACM. С. 191–196. DOI : 10.1145 / 190347.190416 . ISBN 978-0897916387.
^ Borges-Quintana, M .; Боржес-Тренар, Массачусетс; Мартинес-Моро, Э. (20 февраля 2006 г.). Общие принципы применения методов FGLM к линейным кодам . Прикладная алгебра, алгебраические алгоритмы и коды с исправлением ошибок . Конспект лекций по информатике. 3857 . С. 76–86. arXiv : math / 0509186 . DOI : 10.1007 / 11617983_7 . ISBN 978-3-540-31423-3.

Эта статья по алгебре незавершена . Вы можете помочь Википедии, расширив ее .

[1] JC Faugère; П. Джанни; Д. Лазард; Т. Мора (1993). «Эффективное вычисление нульмерных базисов Гребнера путем изменения порядка». Журнал символических вычислений . 16 (4): 329–344. DOI : 10.1006 / jsco.1993.1051 .

[2] Middeke, Johannes (2012-01-01). "Вычислительный взгляд на нормальные формы матриц многочленов Руды". ACM Commun. Comput. Алгебра . 45 (3/4): 190–191. DOI : 10.1145 / 2110170.2110182 . ISSN 1932-2240 .

[3] Гердт, В.П .; Янович Д.А. (01.03.2003). «Реализация алгоритма FGLM и поиск корней полиномиальных инволютивных систем». Программирование и софт . 29 (2): 72–74. DOI : 10,1023 / A: 1022992514981 . ISSN 0361-7688 .

[4] Faugère, Жан-Шарль; Мо, Ченци (2017-05-01). «Редкие алгоритмы FGLM». Журнал символических вычислений . 80, Часть 3: 538–569. arXiv : 1304.1238 . DOI : 10.1016 / j.jsc.2016.07.025 .

[5] Licciardi, Сандра; Мора, Тео (1994-01-01). Неявность гиперповерхностей и кривых с помощью примбасиссаца и базисного преобразования . Труды Международного симпозиума по символьным и алгебраическим вычислениям . ISSAC '94. Нью-Йорк, Нью-Йорк, США: ACM. С. 191–196. DOI : 10.1145 / 190347.190416 . ISBN 978-0897916387.

[6] Borges-Quintana, M .; Боржес-Тренар, Массачусетс; Мартинес-Моро, Э. (20 февраля 2006 г.). Общие принципы применения методов FGLM к линейным кодам . Прикладная алгебра, алгебраические алгоритмы и коды с исправлением ошибок . Конспект лекций по информатике. 3857 . С. 76–86. arXiv : math / 0509186 . DOI : 10.1007 / 11617983_7 . ISBN 978-3-540-31423-3.

[1]