疎な多変数多項式の拡張Hensel構成の効率化 (数式処理とその周辺分野の研究)

HANDLE Web Site オープンアクセス

書誌事項

タイトル別名
  • ソナ タヘンスウ タコウシキ ノ カクチョウ HENSEL コウセイ ノ コウリツカ スウシキ ショリ ト ソノ シュウヘン ブンヤ ノ ケンキュウ
  • Enhancing the Extened Hensel Construction of Sparse Multivariate Polynomials (Computer Algebra and Related Topics)
  • 疎な多変数多項式の拡張Hensel構成の効率化

この論文をさがす

抄録

筆者らは2000年、拡張Hensel構成の初期因子を多項式とすることで、従変数の原点で主係数が0となり且つ従変数に関して疎な多変数多項式の因数分解法を提案した。一般Hensel構成に基づく算法では従変数の原点移動が必要で、項数が増大して計算効率が著しく低下するが、筆者らの算法では原点移動は必要なく、計算効率の低下は避けられる。しかし、主変数に関して高次かつ疎な場合は依然として未解決だった。本稿では未解決点も含め算法を抜本的に改善する。従来の拡張Hensel構成算法は、一般Hensel構成と同様、Moses-Yun補間式を用いて構成を行う。拡張Hensel構成では、Moses-Yun補間式は従変数に関して有理式となり、計算に非常に時間がかかる。Hensel因子の計算も、有理式を扱うので複雑でしかも重い。本稿で提案する算法はMoses-Yun補間式を全く用いず、初期因子を生成元とするグレブナー基底を用いる。ただし、初期因子が3個以上の場合でも2個づつの組に分割して計算する。旧算法では、分母因子の候補は初期因子の終結式で、分子多項式と簡約されて小さな分母因子になるが、新しい算法では分母因子の候補はグレブナー基底の最小順位の多項式で、終結式より遥かに小さいので以後の計算が軽い。さらに、分母多項式をシステム記号で置き換え有理式を多項式化するので、計算が一層効率化される。まだ小規模な例題でテストしただけだが、テスト結果は非常によい。

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ