代数体上の線型方程式系の求解
今回の冪根拡大の構成では，中間体上の線型方程式系（連立一次方程式）を解くことが一つの柱となっています（ http://ehito.hatenablog.com/entry/2019/04/11/193241 ）．それは例えば，定義多項式が
c5^4+c5^3+c5^2+c5+1, e1^2+10, e2^5+((-3750*c5^3)-3750*c5^2-1875)*e1-3125*c5^3+9375*c5^2+6250*c5+3125
である体 Q(c5,e1,e2) 上で
(((10*a4-2*a3+30*a2-70*a1+360)*e1-10*a4-20*a3-150*a2-100*a1-600)*c5^3
+((10*a4-14*a3+30*a2-90*a1+360)*e1-30*a4-20*a3-50*a2-100*a1-1000)
*c5^2+(((-16*a3)-160*a1)*e1-40*a4-200*a2-1600)*c5
+(5*a4-8*a3+15*a2-80*a1+180)*e1-240*e2-20*a4-10*a3-100*a2+250*a1-800)
/240,
(((2*a4-20*a3-10*a2-140*a1+40)*e1-20*a4-60*a3-100*a2+100*a1-800)*c5^3
+((4*a4-20*a3-20*a2-140*a1+80)*e1-20*a4-100*a2+200*a1-800)*c5^2
+((6*a4-30*a2+120)*e1-60*a3+300*a1)*c5
+(3*a4-40*a3-15*a2-120*a1+60)*e1-48*e2^2-60*a4-30*a3-100*a2+150*a1
-2000)
/48,
-(((125*a4+10*a3+575*a2+750*a1+4900)*e1
+150*a4-450*a3+250*a2-2750*a1+5000)
*c5^3
+((125*a4-30*a3+575*a2-250*a1+4900)*e1
-250*a4-450*a3-1750*a2-2750*a1-11000)
*c5^2+(((-20*a3)+500*a1)*e1-100*a4-1500*a2-6000)*c5
+(100*a4-10*a3+100*a2+250*a1+3200)*e1+48*e2^3-50*a4-600*a3-750*a2
-4000*a1-3000)
/48,
-(((450*a4+1000*a3+3750*a2+3000*a1+21000)*e1
-1500*a3-5000*a2-7500*a1-10000)
*c5^3
+((400*a4+1000*a3+3000*a1+12000)*e1-5000*a3-5000*a2-10000*a1-10000)
*c5^2+((850*a4+3750*a2+33000)*e1-6500*a3-17500*a1)*c5
+(425*a4-1000*a3+1875*a2-1000*a1+16500)*e1+48*e2^4-2500*a4-3250*a3
-12500*a2-8750*a1-100000)
/48
の零点 [a4,a3,a2,a1] を（少なくとも一つ）求めるといった処理であり，ツールとしては，Nemo/Julia シリーズ AbstractAlgebra.jl の solve_left ( https://nemocas.github.io/AbstractAlgebra.jl/latest/matrix/#AbstractAlgebra.Generic.solve_left-Union{Tuple{T},%20Tuple{MatElem{T},MatElem{T}}}%20where%20T%3C:RingElem )
Welcome to Nemo version 0.14.1
Nemo comes with absolutely no warranty whatsoever
Welcome to
_ _ _
| | | | | |
| |__| | ___ ___| | _____
| __ |/ _ \/ __| |/ / _ \
| | | | __/ (__| < __/
|_| |_|\___|\___|_|\_\___|
Version 0.6.2 ...
... which comes with absolutely no warranty whatsoever
(c) 2015-2019 by Claus Fieker, Tommy Hofmann and Carlo Sircana
julia> MXl2=MXl[2];
julia> MX=matrix(MXl[4],MXl2,MXl2,MXl[1]);
julia> cx=matrix(MXl[4],1,MXl2,MXl[3]);
julia> @time xx=solve_left(MX,cx);
1.407416 seconds (611.78 k allocations: 29.782 MiB, 1.75% gc time)
および，maxima の algebraic モードでの linsolve と fast_linsolve
(%i11) (map(lambda([s],tellrat(s[1])),DP),algebraic:on,linsolve(sAL1,AL0))$ Evaluation took 0.0040 seconds (0.0040 elapsed) using 1.843 MB. (%i12) (map(lambda([s],tellrat(s[1])),DP),algebraic:on,fast_linsolve(sAL1,AL0))$ Assuming entries of type ANY-MACSYMA Starting to solve. There are 4 equations with 4 unknowns occurring. The value of (SP-TYPE-OF-ENTRIES SP-MAT) is ANY-MACSYMA The dimension of the solution space is 0 Evaluation took 0.0040 seconds (0.0040 elapsed) using 1.186 MB.
があります．
これらのうち solve_left は最近公開されたもので，高速 arithmetic で知られる Nemo シリーズゆえ相応のパフォーマンスが期待され，従来の hnf_with_transform と can_solve_left_reduced_triu の組み合わせよりは高速化していますが，サイズの大きな問題に対する処理速度は maxima の fast_linsolve が優位であり，例えば，47 分多項式を入力とする処理に現れる，文字列としてのサイズが 405801 バイト（上記の例は 1087 バイト）の方程式系の場合，
julia> @time xx=solve_left(MX,cx); 80.273864 seconds (65.62 M allocations: 31.598 GiB, 1.47% gc time)
に対し，無印の linsolve では
(%i14) (map(lambda([s],tellrat(s[1])),DP),algebraic:on,linsolve(sAL1,AL0))$ Evaluation took 458.1150 seconds (472.1600 elapsed) using 92401.623 MB.
そして，
(%i15) (map(lambda([s],tellrat(s[1])),DP),algebraic:on,fast_linsolve(sAL1,AL0))$ Assuming entries of type ANY-MACSYMA Starting to solve. There are 22 equations with 22 unknowns occurring. The value of (SP-TYPE-OF-ENTRIES SP-MAT) is ANY-MACSYMA The dimension of the solution space is 0 Evaluation took 54.8670 seconds (56.4100 elapsed) using 20716.948 MB.
となります．
