密グラフにおける全点対間最短経路アルゴリズムの高速化
スポンサーリンク
概要
- 論文の詳細を見る
通常の行列乗算におけるスカラー乗算と加算をそれぞれスカラー加算と最小値演算で置き換えた行列乗算は,全点対間最短経路問題などへの応用がある.最近,この演算に対し,最悪計算量は変わらないが実用的には通常の方法よりも高速な計算手法が提案された.本稿では,この手法をさらに改良し SIMD 命令を利用した高速化を可能にする.これを利用することにより,全点対間最短経路問題をフロイド・ワーシャル法よりも高速に解くことができることも示す.
- 2011-05-09