数值線形代数における前処理と数式処理における固有多項式計算の高速実装について

摘要

数値線形代数における前処理として，数値不安定性のため，現代ではどなたも利用していないが，ガウスの消去法により，直接法として上Hessenberg行列への変換を行うアルゴリズムが存在する．一方で，数式処理における固有多項式計算では，有限体を用いるために，剰余算の少ないクリロフ部分空間法を用いたものが有効である．上Hessenberg行列への変換を可能にするものと，ブロックコンパニオン行列への変換を許すことで，より高速化したものが考えられる．数値計算における直接法として上Hessenberg行列への変換をおこなうアルゴリズムの演算の順序を変更することにより，数式処理におけるクリロフ部分空間法を用いた上Hessenberg行列への変換と完全に一致することを紹介する．