研究中の数値計算

      2004/03/01 後 保範 (Ushiro Yasunori)
      2006/08/18 更新
 現在最も時間を使っている研究から順に掲載。●印の考案又は実行した項目も新しい順に掲載。
研究成果の簡単な説明及びFORTRANとCの原理プログラムを順に掲載。
 多数桁π計算プログラム多数桁計算基本ルーチン
本格的なプログラムは金田研究室 から他のプログラムと合わせて公開する予定。
研究に関するコメント、質問等は y@aushiro.jp まで。

1. RSA暗号解読(多数桁因数分解)

 多数桁の高速計算アルゴリズムの研究が一段落したので、2005年から10年計画で RSA暗号解読
のための多数桁素因数分解の高速アルゴリズムの考案とプログラム作成に取り組む。
目標は10年後に1024ビットRSA暗号を解読可能にするアルゴリズムの考案及びプログラム作成。
2年後(2008年)に素因数分解の世界記録達成(10進換算232桁)を目標に追加。
●MBPS2の試作プログラムを作成中。
改訂多重基底多項式篩法 (MBPS2, Multiple Base Polynomial Sieve 2nd)を考案。
多重基底多項式篩法 (MBPS, Multiple Base Polynomial Sieve)を考案。
●考案した一般数体ふるい法(GNFS)に代わるアルゴリズム、 多項式ふるい法(PS) の計算量の評価。
●独自考案アルゴリズム(ふるい法系)のプログラム化と性能評価及びアルゴリズムの改善。
GNFS (一般数体ふるい法)の習得と自作プログラム化及びPC,WS,並列コンピュータで性能評価。
●MPQSの改良アルゴリズムの考案とPC,WS.並列コンピュータでの性能評価。
複素多項式2次ふるい法(MPQS)のPC,WS.並列コンピュータでの性能評価。

2. 多数桁の高速計算

 高速フーリエ変換(FFT)及び百五減算(中国剰余定理)で多数桁乗算(畳み込み演算)と高精度な
行列演算、及び三角関数等の有理数級数の値を高精度で計算することを目的とした研究。
乗算と関数は数百桁〜数百兆桁までを、行列計算は数十桁〜数十万桁程度までを対象とする。

FMTの応用と して、Diskを使用した超多数桁の分割乗算プログラムの試作評価完了。
 スーパーコンではメモリ量の数十倍の桁数で、PCでは数百倍の桁数の乗算の効率的実行。
●対称行列の固有値、固有ベクトルの厳密解をFMTで高速計算する方式を検討中。
●連立一次方程式の厳密解を FMTで高速計算する方式を検討中。
●FFTと百五減算を合体させた 高速剰余変換(FMT)考案
●高精度な値を係数とする疎行列の反復解法に百五減算及びFFTを適用する方法を考案。
●上位FFTは加減算とシフトだけによる2段階のFFTを利用した多数桁の乗算方式を考案。
●高精度な値を係数とする百五減算及びFFTによる 密行列の乗算方式を考案。
連分数の計算及び 基底変換にも適用できるようにDRM法を拡張。
入力値が高精度 な有理数級数関数値の計算にも適用できるようにDRM法を拡張。
●高精度な有理数級数関数の値を高速に計算するDRM法 (Divide and Rationalize Method)を考案。

3. Navire-Stokes方程式の原理解析

●7題難問の1つExistance & Smoothness ot the Navier-Stokes Equationに差分法で挑戦中
●スタガード格子と風上差分で「丸め誤差を対称に保った角柱周りの流れ解析」を評価中
●通常格子の中心差分で「丸め誤差を対称に保った角柱周りの流れ解析」に成功
●角柱周りの流れ解析で、中心差分と風上差分及び通常格子とスタガード格子の分割数と
 解析可能レイノルズ数を評価。風上差分とスタガード格子は2003年の後ゼミの 卒業研究
佐久間詔子 さんと丸山由美子さんが評価した。

4. 円周率世界記録を達成

●2002/11/24に東京大学 金田康正教授他と共同で世界記録を 6倍更新し、10進1兆2411億桁、
16進1兆307億桁を達成した。

 2001/10に東大SR8000/MPPで2公式を用いて16進数5000億桁(10進数6000億桁対応)に 挑戦
プログラムミスがあり16進数の359,712,809,450桁以降が一致しないことが判明。
2ヶ月間机上での原因推定とパソコンを使用した再現シミュレーションで原因判明。
誤りの発生桁を同期で俳優の原田大二郎特別招聘教授(明治大学)が残酷な人にはお灸よこれ!
「ザンコクナ(3597)ヒトには(128)オキュウよ(094)これ(50)」と語呂合わせを作成。

5. 密行列の乗算の演算量の削減方法 (Ushiro Method)

 大次元密行列の連立一次方程式及び固有値計算の高速化を目的とした研究。

●ストラッセンの方法を拡張して演算量を  3/4に削減するアルゴリズム(Ushiro Method)を考案。
●演算量を3/4に削減する実密行列と転置行列の乗算にUshiro Methodを拡張。
●複素密行列の乗算では演算量が 9/16に削減できるようUshiro Methodを拡張。
複数回の適用では2回目以降はストラッセンの方法を適用する。
ストラッセンの方法の方法より、必要ワークメモリが少なくできる。

6. ダイレクトスパースソルバー

●構造解析(1節点3自由度が多い)を意識した高速化アルゴリズム研究中。対称及び非対称用。

7. 大次元行列の精度保証計算

 現在は連立一次方程式の解の精度保証。将来は数値シミュレーション全体に適用が目標。

●拡散方程式で発生する 単調行列(Monotone Matrix)の反復解法による計算解の精度保証。
●構造解析に適用可能な対称行列の直接解法による計算解の精度保証。

 理工学研究科荻田武史講師、理工学部大石進一教授と共同研究。荻田講師がアルゴリズムを考案。

8. 連立一次方程式及び固有値計算の反復解法

 差分法及び有限要素法から発生する大次元スパース行列への適用方式を研究。

●有限要素法で離散化した不規則な疎行列反復解法の並列化向き前処理方式を考案。
●有限要素法で離散化した不規則な疎行列の不完全LU分解方式を考案。
Ushiroのパラメータと名付けたMICCG法の安定化パラメータを考案。
●対称疎行列の少数個の固有値、固有ベクトルを求めるCG法による固有値計算方式を考案。

9. ベクトル化及び並列化方式

●不規則な疎行列に対するハイパープレーン化方式を考案しベクトル化及び並列化に適用。
●規則的な疎行列に対するハイパープレーン法によるベクトル化及び並列化方式の考案。

9. 有限要素法及び差分法による解析

連立反復解法をナビェストーク方程式へ直接適用する方法の評価。
●偏微分方程式を高級言語で記述する方式の適用評価。