A comparison of splitting field calculators

方程式 f=0 の Gaolis 群の元の陽な表示（置換や同型写像）の取得には「分解体の定義多項式」と「 primitive element による f の根の多項式表示」の利用が古典的です．そこで今回は，幾つかの計算機代数システムについて，当該処理を担当する関数によるサンプルの処理時間を比較します．

比較する関数は
・mp9 on maxima（Trager の方法による自作関数です）
・splitfield on maxima（Trager の方法による組み込み関数ですが，現在のマニュアルには載っていません）
・SplittingField，FactorsPolynomialAlgExt on GAP（それぞれ Radiroot，Alnuth パッケージの関数です）
・SplittingField on Magma（online の Magma Calculator での実行です）
・nfsplitting，nfisincl on PARI（本命です）
・sp on Asir（逐次拡大は魅力的ですが，．．．）

入力サンプルは，セットＡが以下のもの，セットＢが x^i-2 (i=2,3,...) です．

      [[1,x^2-2],[2,x^3-3*x-1],[3,x^4-2],[4,x^4+x^2-1],[5,x^4-2*x^3+2*x^2+2],
       [6,x^4+2*x^3+3*x^2+4*x+5],[7,x^4+x+1],[8,x^5-2],[9,x^5-5*x+12],
       [10,x^5+20*x+32],[11,x^5+11*x+44],[12,x^5+x^4-4*x^3-3*x^2+3*x+1],
       [13,x^5+100*x^2+1000],[14,x^6+x^3+1],[15,x^6-2],[16,x^5-5*x^3+5*x-5],
       [17,x^6+x^3+7],[18,x^6-3*x^4+1],[19,x^6+x^4-9],[20,x^6+x^4-8],
       [21,x^6+x^4-x^2+5*x-5],[22,x^7+7*x^3+7*x^2+7*x-1],
       [23,x^7-14*x^5+56*x^3-56*x+22],[24,x^7-2],
       [25,x^8-2*x^6-x^4+7*x^2-5*x+1],[26,x^9+x^8+3*x^6+3*x^3-3*x^2+5*x-1],
       [27,x^12-3],[28,x^7-14*x^5+56*x^3-56*x+22],
       [29,
        x^15-x^14-14*x^13+13*x^12+78*x^11-66*x^10-220*x^9+165*x^8+330*x^7
            -210*x^6-252*x^5+126*x^4+84*x^3-28*x^2-8*x+1]]

実験結果です．

・mp9 on maxima
セットＡ（21 で挫折）　Evaluation took 99.2830 seconds (107.5700 elapsed) using 7036.517 MB.
セットＢ（i=7 で挫折）　Evaluation took 0.0900 seconds (0.4580 elapsed) using 9.523 MB.

・splitfield on maxima
セットＡ（21 で挫折）　Evaluation took 121.7320 seconds (126.9250 elapsed) using 9229.759 MB.
セットＢ（i=7 で挫折）　Evaluation took 0.1750 seconds (0.1760 elapsed) using 57.411 MB.

・SplittingField，FactorsPolynomialAlgExt on GAP
セットＡ
x:=Indeterminate(Rationals,"x");P:=[x^2-2,...];
Rt0:=Runtimes();for i in [1..29] do
p:=P[i];sp:=SplittingField(p);FactorsPolynomialAlgExt(sp,p); od;
Rt:=Runtimes();Rt.user_time-Rt0.user_time;
17.215 seconds.
セットＢ（i=13 で挫折）
x:=Indeterminate(Rationals,"x");
Rt0:=Runtimes();for i in [1..12] do
p:=x^i-2;sp:=SplittingField(p);FactorsPolynomialAlgExt(sp,p); od;
Rt:=Runtimes();Rt.user_time-Rt0.user_time;
21.110 seconds.

・SplittingField on Magma
セットＡ　
R:=PolynomialRing(IntegerRing());P:=[x^2-2,...];
for i:=1 to 29 do sp:=SplittingField(P[i]); end for;
Total time: 3.020 seconds.
セットＢ（i=19で挫折）
R:=PolynomialRing(IntegerRing());
for i:=2 to 18 do sp:=SplittingField(x^i-2); end for;
Total time: 57.450 seconds.

・nfsplitting，nfisincl on PARI
セットＡ
P=[x^2-2,...];
for(i=1,29,p=P[i];sp=nfsplitting(p);nfisincl(p,subst(sp,x,a)));
time = 772 ms.
セットＢ　
for(i=1,18,p=x^i-2;sp=nfsplitting(p);nfisincl(p,subst(sp,x,a)));
time = 13,509 ms.
for(i=19,30,p=x^i-2;sp=nfsplitting(p);nfisincl(p,subst(sp,x,a)));
time = 10min, 56,209 ms.

・sp on Asir
セットＡ
load("sp")$P=[x^2-2,...]$T=time()[0]$N=0$while(N<29){print([N]);sp(P[N]);N++;}$time()[0]-T;
2.29462 seconds.
セットＢ（i=20で挫折）
T=time()[0]$N=2$while(N<=19){print([N]);sp(x^N-2);N++;}$time()[0]-T;
4462.29 seconds.