グレブナー基底の並列計算と連立代数方程式
スポンサーリンク
概要
- 論文の詳細を見る
有理数体上の多項式イデアルのグレブナー基底(標準基底)の並列算法を提案し,それを用いた連立代数方程式の代数的解法を論じる.多項式イデアルのグレプナー基底の計算は従来の算法では大きな中間式膨張を引き起こすことがしばしばだが,最近,筆者らによって中国剰余定理に基づくモジュラ算法が提案され,中間式膨張問題が解決された.本論で提案する並列算法はこのモジュラ算法の並列化であり,簡単な構造の並列計算機(いわゆるモジュラ型並列計算機)で実行でき,しかも並列プロセッサ数にほぼ逆比例して計算時間が減少する理想的なものである.このことを実際的問題に対する逐次計算機上でのタイミング・データで実証する.本アルゴリズムはモジュラ型であるから,プログラミングの若干の工夫により,逐次計算機上でも擬似並列的に実行可能であり,そのための算法も提示する.これらの算法は連立代数方程式の代数的解法に直ちに応用できるが,その場合には問題の特殊性を利用した効率化が可能であり,それを指摘する.
- 一般社団法人情報処理学会の論文
- 1989-12-15
著者
関連論文
- 行列の有理標準形の一計算法(数式処理と数学研究への応用)
- modular 算法による多項式GCD計算について(数式処理と数学研究への応用)
- Euclid環上の因数分解およびGCDについて : 格子算法の応用
- コンピュータ環論 (数式処理)
- 超 LSI 用電子ビーム露光法
- 計算機による数式処理と物理学への応用
- 計算機による数式処理の現状
- グレブナー基底の並列計算と連立代数方程式
- ブール方程式による併存到達可能性解析 (情報の記憶と利用に関する理論的研究)
- 同値律をみたす述語による関係データモデル従属性の一般化について (情報の記憶と利用に関する理論的研究)
- PSI上の数式処理システムSAM
- 4. 数式処理と数値計算の融合による精度保証 (精度保証付き数値計算とその応用)
- PC-PRS GCD算法の改良(数式処理と数学研究への応用)
- 大特集「数式処理」の編集にあたって
- 数式処理の歴史と将来の展望 (数式処理)
- 国産数式処理システムGALにおけるパターンマッチング(数式処理と数学研究への応用)
- INTERNAL REPRESENTATIONS OF FORMULAS IN JAPANESE COMPUTER ALGEBRA SYSTEM GAL(Formula Manipulation and Its Applications to Mathematical Study)
- 多変数多項式の近似因数分解算法の解析(数式処理と数学研究への応用)
- 多変数多項式の近似的 GCD と悪条件連立代数方程式への応用
- 多変数多項式の近似的GCDとその応用(数式処理と数学研究への応用)
- 数式処理システムGALにおける数学公式データベース