改善策と問題点
前々回の記事( http://ehito.hatenablog.com/entry/2019/04/11/193241 )で述べた方法では, 以降をただ つの を見付けるために生成していますが,実は を得た段階で,それが に属する場合には,先述の通り拡大を行わず,属さない場合,つまり, が となる係数 をもつ場合には,その Lagrange Resolvent
の中に でないものがあるので,それを とすることができます.
この方法では,全ての係数を生成するのは に直結した のみで,後は つの係数 に対する処理となり,相応の高速化が期待できるように思えます.
ところが,この を定義通りに計算すると, は の基本対称式の つゆえ, となる 上の多項式 があり, の準同型性から, なので, に対応する の根を の に代入したもの,つまり,最も悪い場合には, の次数のおよそ 乗の次数の多項式(しかも係数は分子分母の桁数が大変なことになっている既約分数)の簡約整理が必要となります.
これまでのところ
【1】前々回の記事のままの実装
【2】上記の改善策による実装
そして
【3】上記の に対する次数よりも大きな次数の項を消去しながら を簡約整理する実装
の処理時間は,サイズの小さな問題では【2】が短く,大きな問題では【1】が短く,【3】はその中間といった実験結果を得ています.