FGLMアルゴリズム

FGLMはコンピュータ代数の主要なアルゴリズムの 1 つで、設計者のFaugère、Gianni、Lazard、Moraにちなんで名付けられました。彼らは 1993 年にアルゴリズムを発表しました。アルゴリズムの入力は、単項式順序と 2 番目の単項式順序に関する体上の多項式環の0 次元イデアルのグレブナー基底です。出力として、2 番目の順序に関するイデアルのグレブナー基底を返します。このアルゴリズムはコンピュータ代数の基本的なツールであり、ほとんどのコンピュータ代数システムに実装されています。FGLMの計算量はO ( nD ³ )です。ここで、nは多項式の変数の数、D はイデアルの次数です。^[1] FGLM にはいくつかの一般化とさまざまなアプリケーションがあります。^[2]^[3]^[4]^[5]^[6]

参考文献

^ JC Faugère; P. Gianni; D. Lazard; T. Mora (1993). 「順序変更によるゼロ次元グレブナー基底の効率的計算」Journal of Symbolic Computation . 16 (4): 329–344. doi : 10.1006/jsco.1993.1051 .
^ Middeke, Johannes (2012-01-01). 「Ore 多項式の行列の正規形の計算的観点」ACM Commun. Comput. Algebra . 45 (3/4): 190–191. doi :10.1145/2110170.2110182. ISSN 1932-2240. S2CID 14396484.
^ Gerdt, VP; Yanovich, DA (2003-03-01). 「FGLM アルゴリズムの実装と多項式インボリューティブシステムの根の検出」.プログラミングとコンピュータソフトウェア. 29 (2): 72–74. doi :10.1023/A:1022992514981. ISSN 0361-7688. S2CID 17851647.
^ Faugère, Jean-Charles; Mou, Chenqi (2017-05-01). 「スパース FGLM アルゴリズム」. Journal of Symbolic Computation . 80, Part 3: 538–569. arXiv : 1304.1238 . doi :10.1016/j.jsc.2016.07.025. S2CID 149627.
^ Licciardi, Sandra; Mora, Teo (1994-01-01). 「Primbasissatz と基底変換による超曲面と曲線の暗黙化」.記号および代数計算に関する国際シンポジウム - ISSAC '94 の議事録。ニューヨーク、ニューヨーク、米国: ACM。pp. 191–196。doi : 10.1145 /190347.190416。ISBN 978-0897916387.S2CID 14584685 。
^ Borges-Quintana, M.; Borges-Trenard, MA; Martínez-Moro, E. (2006-02-20). 「線形コードに FGLM 技術を適用するための一般的なフレームワーク」。応用代数、代数アルゴリズム、およびエラー訂正コード。コンピュータサイエンスの講義ノート。第 3857 巻。pp. 76–86。arXiv : math/0509186。doi :10.1007/ 11617983_7。ISBN 978-3-540-31423-3. S2CID 13427304。

[1] JC Faugère; P. Gianni; D. Lazard; T. Mora (1993). 「順序変更によるゼロ次元グレブナー基底の効率的計算」Journal of Symbolic Computation . 16 (4): 329–344. doi : 10.1006/jsco.1993.1051 .

[2] Middeke, Johannes (2012-01-01). 「Ore 多項式の行列の正規形の計算的観点」ACM Commun. Comput. Algebra . 45 (3/4): 190–191. doi :10.1145/2110170.2110182. ISSN 1932-2240. S2CID 14396484.

[3] Gerdt, VP; Yanovich, DA (2003-03-01). 「FGLM アルゴリズムの実装と多項式インボリューティブシステムの根の検出」.プログラミングとコンピュータソフトウェア. 29 (2): 72–74. doi :10.1023/A:1022992514981. ISSN 0361-7688. S2CID 17851647.

[4] Faugère, Jean-Charles; Mou, Chenqi (2017-05-01). 「スパース FGLM アルゴリズム」. Journal of Symbolic Computation . 80, Part 3: 538–569. arXiv : 1304.1238 . doi :10.1016/j.jsc.2016.07.025. S2CID 149627.

[5] Licciardi, Sandra; Mora, Teo (1994-01-01). 「Primbasissatz と基底変換による超曲面と曲線の暗黙化」.記号および代数計算に関する国際シンポジウム - ISSAC '94 の議事録。ニューヨーク、ニューヨーク、米国: ACM。pp. 191–196。doi : 10.1145 /190347.190416。ISBN 978-0897916387.S2CID 14584685 。

[6] Borges-Quintana, M.; Borges-Trenard, MA; Martínez-Moro, E. (2006-02-20). 「線形コードに FGLM 技術を適用するための一般的なフレームワーク」。応用代数、代数アルゴリズム、およびエラー訂正コード。コンピュータサイエンスの講義ノート。第 3857 巻。pp. 76–86。arXiv : math/0509186。doi :10.1007/ 11617983_7。ISBN 978-3-540-31423-3. S2CID 13427304。