GPUのスパースコレスキー分解アルゴリズム

Question

スパースなコレスキー分解を計算するための並列アルゴリズムを誰に教えてもらえますか？ GPUでの実行に適している必要があります。 CUDA、OpenCL、または擬似コードの回答は高く評価されます。

Answer 1

一般に、直接スパースメソッドは、GPUにはあまり適していません。最良のダイレクトソルバー（ここではCHOLMOD、SuperLU、MUMPSなどのパッケージについて考える）は、L3 BLASを使用して処理できる密なサブブロックを生成するための戦略を使用しますが、ブロックのサイズと形状はGPU BLAS加速のために。それができないことを意味するものではなく、パフォーマンスの向上がその努力に値するものではないかもしれないということだけです。

あなたが疎なコレスキー分解について質問しているのを見て、私は行列が対称正定であると仮定しました。その場合、反復ソルバーの使用を検討することもできます。共役勾配法や他のKrylov部分空間法のいくつかを使用する単純なプリコンディショナーを使用して、多くの優れた実装があります。 CUDA用のCuspライブラリは、問題が反復可能なメソッドに適しているかどうかを調べる価値があります。 ViennaCLライブラリでは、OpenCLを探している場合も同様の機能を提供します。

Answer 2

ACM（SC'08とPPoPP '09は優れた会議です）の礼状を参照してください。

V.V. Volkov、J.W.Demmel。高密度線形代数を調整するためのGPUベンチマークSC'08。

Jung、J.H.、O'Leary、D.P.コレスキー分解と GPUでの線形プログラミングScholarly Paper、University of Maryland、2006.

G. Quintana-Orti、F. D. Igual、E. S. Quintana-Orti、R. A. van de Geijn。複数のハードウェアアクセラレータを備えたプラットフォーム上で高密度線形システムを解く。 PPoPP'09。

ACM Portal/DLを介してアクセスできない場合は、どこかオンラインである可能性があります。そうでなければ...私はおそらく、最も関連性の高いセクションの一部を引用して引用し、それを公正に使用することができます。

編集：

これを確認してください。

http://www.google.com/url?sa=t&source=web&cd=2&ved=0CB0QFjAB&url=http%3A%2F%2Fwww.netlib.org%2Flapack%2Flawnspdf%2Flawn223.pdf&rct=j&q=linpack%20gpu%20cholesky&ei=5nZOTtzCOYHAtgesmdSzBw&usg=AFQjCNGfQECpU6YJQhMRQYktlxpFKLFPjQ&cad=rja

EDIT2： "スパース" についての一部を逃しました。

オンラインで、ACM/IEEEで見ても、私が飛び出すことはほとんどありません。私が見ていることは有望だとは思わない...これは、GPUを使うことによる多くの利益がある計算ではないかもしれない。

Answer 3

マルチフロントアルゴリズムは、パラレルスパース因子分解の一般的な選択肢のようです。 MUMPSパッケージhereを確認してください。

私が理解しているように、コードはレベル3 BLASコール（DGEMMなど）を使用して、高性能を達成しています。 ではなくGPUを使用したい場合は、CUDA BLASなどのGPUベースのBLASの実装にリンクすることが可能かどうかを調査します。

高密度因子分解とは対照的に、疎行法は、浮動小数点作業に加えて無視できない量の整数作業を常に含んでいます（ただし浮動小数点は依然として支配的です）。私はGPU'sの専門家ではありませんが、はGPUよりも整数作業に適していますか？これは、GPUのアルゴリズム全体を実装することについての議論かもしれません...

希望することができます。

Answer 4

GPUでのスパース性のコルスキー分解は未解決の問題です。前述のLinear Programmingpaperでさえ、密なアルゴリズムを使用しますが、ほとんどの問題はまばらです。市販のLPソルバー市場は非常に競争が激しいですが、GPUをまだ多く使用している製品はありません。

Answer 5

UHM - 組み立てられていないハイパーマトリックスソルバーを参照してください。 1つのホスト上で複数のGPUを使用して、疎なコレスキー分解を計算できます。