- 著者
-
竹内 純一
萬 淳一
- 雑誌
- 全国大会講演論文集
- 巻号頁・発行日
- vol.46, pp.57-58, 1993-03-01
通常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の演算速度を達成した.また,誤差の面でも実用上問題が無いことが分かった.