Sparse Matrix Solvers on the GPU (SIGGRAPH2003)

ふと、思い出したように論文を読んでみました。
たまにこうやって自分の方向性を探っていかないと馬鹿になりそうで怖いですね。

Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid
Webサイトはこちら

Abstract:
多くのコンピュータグラフィクスアプリケーションは、膨大な数値演算を必要とします。我々は、GPUを高性能な浮動小数点演算機能を備えたフル機能のストリーミングプロセッサとみなすことで、そのような演算がGPUで効率的に処理できることを示しました。我々は、疎行列共役勾配法とマルチグリッド法という、基本的で多くの分野に適用可能な演算を実装しました。NVIDIA製GeForceFXでの実装と検討は、メッシュのスムージングや、流体シミュレーション、solid mechanics(謎)などのリアルタイムアプリケーションにおいて大いに効果が期待されます。

論文の内容ですが、
　sparse matrix conjugate gradient solver( 疎行列共役勾配法？)
　regular-grid multigrid solver (マルチグリッド法)
という、2つの手法をGPUにマッピングしてみました、という内容。

メッシュスムージングでは、各頂点ごとに隣接する頂点のパラメータを用いて演算を行うのですが、この隣接情報を持つのが疎行列になります。メッシュの頂点をNとすると、NxNの行列が必要になり、その多くの要素には0が入ります（だから疎行列）。これを、0をパディングして消して、テクスチャCに押し込め、各頂点ごとに、テクスチャTへの参照を記述したテクスチャRを作ります。で、演算をするときは、C( T(u,v) ) というような間接参照で、隣接頂点のパラメータを取得します。
正直、数式の部分は理解しきれていないのですが、Shaderの処理部分だけみると、このテクスチャの間接参照を駆使して演算をしています。

流体シミュレーションでは、マルチグリッド法をGPUで実装しています。マルチグリッド法というのは、ここに資料がありますが、要は拡大縮小をしながらサンプリングするような感じだと思われます。やっぱり、ざっと読んだだけじゃよくわかりません。

両者とも、既にある手法をGPUにマッピングしたという感じなので、元の手法をまず理解しないと難しそうですね。「Computation on GPUs」っていうお題は、もとのComputationを理解するのが非常に手間がかかります。