高速剰余変換による多数桁乗算(アルゴリズム理論)
スポンサーリンク
概要
- 論文の詳細を見る
多数桁乗算に関する計算アルゴリズムを提案する.そのアルゴリズムは高速フーリエ変換(FFT)に剰余理論を取り込んだ方法を基礎にした.基礎とする方法を高速剰余変換(Fast Modulo Transformation, FMT)と名付ける.FMTは1の原始n乗根ωの上に作成したもので,複素数だけでなく整数でも定義できる.ωを複素数にするとFMTはFFTと同じ計算式になる.FMTは剰余理論に基づいているため多数桁乗算への応用に対する見通しが良い.多数桁乗算へのFMTの応用として整数FMT,巡回乗算,2段階FMT,複素FMTの直接利用および分割乗算を示す.整数FMTによる巡回乗算は±1の巡回だけでなく自然数αに対して±αで巡回する乗算も可能と判明した.さらに,多数桁乗算の入力値をm個に分割し,互いに異なるm個の自然数αを用いて,±αで巡回する2m個の分割した乗算から元め多数桁乗算を復元することが可能となる.多数桁乗算に2段階FMTおよび分割乗算を利用すると使用メモリ量を大きく削減できる.
- 2003-12-15
著者
関連論文
- 級数に基づく多数桁計算の演算量削減を実現する分割有理数化法
- 拡張Strassen法による連立一次方程式の精度保証 (数値解析と新しい情報技術)
- Strassen のアルゴリズムによる行列乗算の高速精度保証 (微分方程式の数値解法と線形計算)
- ベクトル計算機による RSA 暗号ふるいの高速化 (科学技術計算アルゴリズムの数理的基盤と展開)
- 多数桁分割乗算の高速計算法(数値計算)
- 有限要素法用ICCG法の並列化方法 (偏微分方程式の数値解法とその周辺)
- ベクトル計算機向きICCG法(並列数値計算アルゴリズムとその周辺)
- 拡張ストラッセン法の連立1次方程式への応用 (数値解析と新しい情報技術)
- 行列乗算におけるストラッセンの方法の拡張(数値計算アルゴリズムの研究)
- 対称用改訂CR法の収束性(数値解析と科学計算)
- ナビエストークス方程式への連立ILUCGS法適用結果(数値解析と科学計算)
- スーパーコンピュータ"HITAC S-810"による拡散方程式の数値計算(スーパーコンピュータのための数値計算アルゴリズムの研究)
- 移流拡散方程式に対するベクトル計算機向きPCG法(大型の線形計算に関するアルゴリズムの研究)
- CG法と同時逆反復法の組合せによる固有値計算(数値計算のアルゴリズムの研究)
- ベクトル計算機向き不完全三角分解 (数値計算のアルゴリズムの研究)
- スツルム・同時逆反復法 (数値計算のアルゴリズムの研究)
- 高速剰余変換による多数桁乗算(アルゴリズム理論)
- 有限要素法による連立一次方程式のベクトル・並列向き反復解法(数値解析とそのアルゴリズム)
- 多数桁分割乗算の高速計算法
- 反復解法による連立一次方程式の数値解の高速精度保証
- 多倍長精度の値を係数とする行列の高速乗算方式 (偏微分方程式の数値解法とその周辺II)
- 単調な疎行列における連立一次方程式の高速精度保証 (偏微分方程式の数値解法とその周辺II)