FGLM アルゴリズムはある順序に関する可換環の Groebner 基底を別の順序に関する Groebner 基底に変換するアルゴリズムです。このアルゴリズムは、直接 Groebner 基底を計算する事が困難な場合によく用いられます。

FGLM コマンドは入力として単項式順序 T1 に関する Groebner 基底 G を取り、T2 に関する簡約 Groebner 基底に変換して出力します。第 1 引数 G が PolynomialIdeal だった場合で、T1 に関する Groebner 基底がまだわかっていないときは、先にそれを計算します。

G によって定義されるイデアルの複素数解は、有限個でなくてはなりません (IsZeroDimensional 参照)、そうでなくてはアルゴリズムが停止しません。この条件はオプション引数 stoppingcondition または truncationorder が指定されていたときはチェックされません (以下をご参照ください) 。また、G が Groebner 基底でなかったときはこのチェックは正確に行われません。

T1 と T2 は多項式環上の通常の単項式順序でなくてはなりません。よって 'plex_min' や 'tdeg_min' といった 'min' のついた順序を用いることができません。FGLM コマンドでは G が T1 に関する Groebner 基底かどうかのチェックは行いません。また、制限によって T2 は変数消去する行列順序を用いることができません i.e.: 行列順序の第 1 行目の要素は正でなくてはなりません。

オプション引数 characteristic=p は係数体の標数を定めます。特に指定がなければ 0 とされます。このオプションは G が PolynomialIdeal だったときは無視されます。係数膨張が激しい問題では、大きな素数 p を法とした FGLM アルゴリズムは有効でしょう。この構成法は本来の Groebner 基底の、p を法とした像を構成しますが、いくつかの応用のためにはこれで充分なことがあります。他のオプションは RationalUnivariateRepresentation を計算するためのものです。

オプション引数 truncationorder=n という指定は、非負整数 n に対して、全次数が n 以上になる項を計算に入れないようにします。この境界条件の指定は、0 次元イデアルでないものに対してもアルゴリズムの停止性を保証しますが、計算結果が T2 に関する Groebner 基底になっていない可能性があります。

オプション引数 stoppingcondition=f という指定は、一つの引数 m を取り、真偽値を返す関数 f に対して、現在計算している単項式 m が、条件 f(m)=true を満たしたときアルゴリズムが停止するようにします。このよく使われる例は変数消去 (以下を参照) ですが、他にも使用例があります。例えば、一定の時間を経過して部分的な結果しか得られない場合でもアルゴリズムが停止するようにする、というようなものです。

オプション引数 output=basislm は計算結果の基底を頭単項式と頭係数を含んだ形式にして出力するよう指定します。出力のリストの各要素は [leading coefficient, leading monomial, polynomial] の形です。

infolevel[FGLM] に正の整数を設定すると、FGLM コマンドは計算の経過や効率について逐一出力するようになります。

MultivariateCyclicVector コマンドは FGLM アルゴリズムの、非可換代数や加群への一般化です。

with(Groebner):

F := [x^3+x*y-y^2+1, y^3-x*y+x];

G := Basis(F, tdeg(x,y));

FGLM(G, tdeg(x,y), plex(x,y));

Basis(G, plex(x,y));

FGLM(G, tdeg(x,y), plex(y,x), stoppingcondition=(m->has(m,y)));

J. Faugere, P. Gianni, D. Lazard and T. Mora. "Efficient computation of zero-dimensional Grobner bases by change of ordering."  J. Symbolic Comput., 16 (1993), 329-344.