氏名: 間瀬 義人 (289634423)
論文題目: 多項式剰余列の安定な生成法の改良
論文概要
2つの多項式F、Gから多項式剰余列を求めるには、従来Euclid算法が用いられ
るが、浮動小数点演算の下での剰余列の生成は数値的に不安定である。特に、剰余列
生成の過程で不正規に近い状態になったとき、Euclid算法では隣接する剰余列
要素から次の剰余列要素を計算するため桁落ちが生じる。
そこで数値計算の立場から多項式剰余列の安定な生成法について研究が行なわ
れ、
Givens回転を用いた剰余列の生成法が考えられた。この算法は多項式を行ベクトルと
見た時に、直交変換の繰り返しによる行列のQR分解であるので数値的に安定である。
しかし多項式F、Gの次数がともにnのときの両算法の計算量を比較すると、
Euclid算法がnの2乗に比例するのに対し、この算法ではnの3乗に比例していること
がわかった。この問題点を解決するためにアルゴリズムを次のように改良した。
剰余列要素を求める反復過程において、途中に現れる剰余列要素から再出発する。
この再出発の際に混入する丸め誤差の影響がなるべく小さくなるように、拡張剰余
列を用いた評価を行ない、安定に再出発できる剰余列要素の組を見つける。また、
この改良による算法の安定性と計算量の変化について検証した。
目次に戻る