代数体上の線型方程式系の求解
今回の冪根拡大の構成では,中間体上の線型方程式系(連立一次方程式)を解くことが一つの柱となっています( 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.
となります.