Алгоритм FGLM - FGLM algorithm

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

Рекомендации

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