浮動小数グレブナー基底の安定な算法を目指して (数式処理とその周辺分野の研究)

Abstract

本稿は浮動小数を係数とする多変数多項式イデアルのグレブナー基底計算を扱う。この種の計算では初期誤差の伝播拡大を徹底的に抑止することが必要で、過去20年以上も世界の研究者が取り組んだが、満足できる算法は未だ存在しない。数値計算では1958年に発表されたHouseholder消去が、誤差の伝播拡大の抑止に極めて有効なことが知られている。そこで本稿では、Householder消去を用いて算法の安定化を試みる。グレブナー基底計算の全体あるいは一部は、関連する多項式の係数ベクトルを行とする行列(簡約行列と呼ぶ)の消去に帰着できる。簡約行列はHouseholder消去により安定に消去されると思うだろうが、簡約行列は不規則に疎で、Householder消去には悪設定(ill-posed)なことが多く、良設定化(well-posing)を如何に行うかが問題である。本稿では、L-簡約とS-多項式生成を行う際に、これら演算の引数となる多項式以外の多項式を簡約行列にスタビライザ(stabilizer)として入れることで良設定化を図る。浮動小数演算では多くのL-簡約とS-多項式が巨大誤差の原因なので危険だが、それらもスタビライザとしては使用できる ; そのようなL-簡約とS-多項式をゴースト(ghost)と命名した。ゴーストは筆者の算法では重要な役割を果たす。算法はまだ未完成なので、本稿では準備計算と今後の方針について述べる。