Strassenの行列積アルゴリズムのSX-3上でのインプリメント

スポンサーリンク

概要

• 論文の詳細を見る

• 通常N次正方行列の積を計算するには,2N^3回の浮動小数点演算が必要となるが,1969年にV.Strassenは,分割統治法(divide and conqure)という方略を再帰的に適用することにより,4.7N^<2.81>回の浮動小数点演算で行列積が求められることを示した.このアルゴリズムは計算量のオーダを下げるが,係数が増加するため行列のサイズがある程度大きくないと実際には計算量が減らない.また,アルゴリズムが自然なものに比べ複雑であり,誤差の点で不利であること等の理由から,ほとんど実用に供されることがなかった.しかしながら,近年計算機のハードウェアが発達し,大規模な行列の演算が実用的な時間で計算出来るようになるとともに,実用化される例が現れている.こうしたことから,NECのスーバーコンピュータSX-3上でも,Starassenのアルゴリズムをインプリメントしてみた.一般に,SX-3のようなベクトル計算機の場合,行列のサイズが小さいとベクトル化の利点が活かしにくいため,演算速度が下がる.このため,行列を小行列に分割して計算するStrassenのアルゴリズムでは,必要な演算量を減らしても実行時間が減るとは限らない.しかしながら,評価実験の結果,Strrassenのアルゴリズムにより,行列積の演算時間が最大約15%削減されることが分かった,特に2048次の行列では,見かけ上約5.9GFLOPSの演算速度を達成した.また,誤差の面でも実用上問題が無いことが分かった.

• 一般社団法人情報処理学会の論文
• 1993-03-01

著者

• 竹内 純一

  Nec C&cメディア研究所

• 萬 淳一

  Nec C&c 情報研究所

関連論文

• Strassenの行列積アルゴリズムのSX-3上でのインプリメント
• 5C-6 S400対応IEEE1394長距離アダプタの開発
• Bayes 方式によるMinimax符号
• 証拠の強さと信頼度を考慮した日本語同形異音語の読み分け
• MDL原理によるLaplace型推定量の導出と確率的PAC学習モデルによるその性能評価

スポンサーリンク