В компьютерной алгебре , то алгоритм Faugère F4 , на Жане Чарльза Фогер , вычисляет базис Грёбнера в качестве идеала многовариантного кольца многочленов . Алгоритм использует те же математические принципы, что и алгоритм Бухбергера , но вычисляет множество нормальных форм за один раз, формируя в целом разреженную матрицу и используя быструю линейную алгебру для параллельного выполнения редукций.
Алгоритм Faugère F5 сначала вычисляет базис Грёбнера пары генераторных полиномов идеала. Затем он использует этот базис, чтобы уменьшить размер исходных матриц генераторов для следующего большего базиса:
Если G prev - это уже вычисленный базис Грёбнера ( f 2 ,…, f m ), и мы хотим вычислить базис Грёбнера ( f 1 ) + G prev, то мы построим матрицы, строки которых равны m f 1, такие что m является одночлен, не делящийся на главный член элемента группы G prev .
Эта стратегия позволяет алгоритму применять два новых критерия, основанных на том, что Фожер называет сигнатурами многочленов. Благодаря этим критериям алгоритм может вычислять базисы Грёбнера для большого класса интересных полиномиальных систем, называемых регулярными последовательностями , без упрощения одного полинома до нуля - наиболее трудоемкая операция в алгоритмах, вычисляющих базисы Грёбнера. Это также очень эффективно для большого количества нерегулярных последовательностей.
Реализации
Реализован алгоритм Faugère F4.
- в FGb - собственная реализация Фогера , которая включает интерфейсы для его использования из C / C ++ или Maple ,
- в системе компьютерной алгебры Maple , как опция method = fgb функции Groebner [gbasis]
- в системе компьютерной алгебры Magma ,
- в системе компьютерной алгебры SageMath ,
Учебные версии алгоритма Faugère F5 реализованы в [ ссылка ]
Приложения
Ранее неразрешимая проблема "циклической 10" была решена F5 [ необходима цитата ], как и ряд систем, связанных с криптографией; например HFE и C * . [ необходима цитата ]
Рекомендации
- Фогер, Ж.-К. (Июнь 1999 г.). «Новый эффективный алгоритм для вычисления базисов Грёбнера (F 4 )» (PDF) . Журнал чистой и прикладной алгебры . 139 (1): 61–88. DOI : 10.1016 / S0022-4049 (99) 00005-5 . ISSN 0022-4049 .
- Фогер, Ж.-К. (Июль 2002 г.). Новый эффективный алгоритм вычисления базисов Грёбнера без приведения к нулю (F 5 ) (PDF) . Труды Международного симпозиума 2002 года по символьным и алгебраическим вычислениям (ISSAC) . ACM Press. С. 75–83. CiteSeerX 10.1.1.188.651 . DOI : 10.1145 / 780506.780516 . ISBN 978-1-58113-484-1.
- Повторение алгоритма F5 Тилля Стегерса Фогера ( альтернативная ссылка ). Diplom-Mathematiker Thesis, руководитель Йоханнес Бухманн, Технический университет Дармштадта, сентябрь 2005 г. (отредактировано 27 апреля 2007 г.). Множество ссылок, включая ссылки на доступные реализации.
Внешние ссылки
- Домашняя страница Фожера (включает в себя оттиски дополнительных статей в формате pdf)
- Введение в алгоритм F4.