CUDA を使用して、非線形最小二乗ソルバーで連立方程式を解きたいと思います。これらの方法については、こちらからダウンロードできる優れた小冊子で説明されています。
私の問題のヤコビ行列は疎で下三角です。これらのメソッドで利用できる CUDA のライブラリはありますか? または、小冊子からこれらのメソッドを自分でプログラムする必要がありますか?
Gauss-Newton 非線形最小二乗ソルバー、Levenberg-Marquardt または Powell 法ソルバーは CUDA ライブラリ (無料または非無料) で利用できますか?
CUDA での準ニュートン最適化ルーチンの単純な実装の可能性を指摘する前に、準ニュートン オプティマイザーがどのように機能するかについて説明します。
N 個の実変数xの関数fを考え、特定の点xiの周りで 2 次展開を行います。
ここで、Aはヘッセ行列です。
点xiから始まる最小値を見つけるために、ニュートンの方法は次の強制で構成されます。
これには
そして、これはヘッセ行列の逆数を知ることを意味します。さらに、機能が確実に低下するように、更新方向
そのようなものであるべきです
つまり、
上記の不等式によれば、ヘッセ行列は明確な正でなければなりません。残念ながら、ヘッセ行列は、特にfの最小値から遠く離れて、必ずしも明確な正であるとは限りません。そのため、ヘッセ行列の逆行列を使用すると、計算負荷が高くなるだけでなく、手順が最小値からさらに値が増加する領域に向かって押し出され、有害になる可能性があります。fの。一般的に言えば、準ニュートン法、つまりヘッセ行列の逆関数の近似を使用する方が便利です。これは、明確な正を維持し、反復がヘッセ行列自体の逆関数に収束した後に反復を更新します。準ニュートン法の大まかな正当化は次のとおりです。検討
と
2 つの方程式を引くと、ニュートン手順の更新規則が得られます。
準ニュートン手順の更新規則は次のとおりです。
ここで、Hi+1は、ヘッセ行列の逆行列を近似し、ステップごとに更新する前述の行列です。
Hi+1の更新にはいくつかのルールがありますが、この点については詳しく説明しません。Broyden-Fletcher-Goldfarb-Shannoによって提供される非常に一般的なスキームですが、多くの場合、Polak-Ribiéreスキームで十分に効果的です。
CUDA 実装は、従来のNumerical Recipesアプローチと同じ手順に従うことができますが、次のことを考慮してください。
1) CUDA Thrust または cuBLAS を使用すると、ベクトル演算と行列演算を効果的に実行できます。2) 制御ロジックは CPU で実行できます。3) ルート ブラケットとルートの発見を含むラインの最小化は、CPU で実行でき、GPU のコスト関数と勾配の評価のみを加速します。
上記のスキームにより、未知数、勾配、およびヘッセ行列を、ホストからデバイスへと移動する必要なく、デバイス上に保持できます。
また、線の最小化を並列化する試みも提案されているいくつかのアプローチが文献で利用可能であることにも注意してください。
Y. Fei、G. Rong、B. Wang、W. Wang、「GPU 上の並列 L-BFGS-B アルゴリズム」、Computers & Graphics、vol. 40, 2014, pp. 1-9.
このgithub ページlinminでは、完全な CUDA 実装が利用可能で、を採用した Numerical Recipes アプローチを一般化mkbrakしdbrent、GPU 並列ケースに適用します。このアプローチは Polak-Ribiére のスキームを実装していますが、他の準ニュートン最適化問題に簡単に一般化できます。
これも見てください: libflameには、BLAS および LAPACK ライブラリによって提供される多くの操作の実装が含まれています。
現在、CUDA プラットフォームを使用して非線形最小二乗ソルバーを使用して連立方程式を解くことを実装するライブラリで利用できる手順はありません。これらのアルゴリズムは、スパース行列を使用して線形代数を実装する他のライブラリの助けを借りて、ゼロから作成する必要があります。また、上記のコメントで述べたように、cuBLAS ライブラリは線形代数に役立ちます。
まだ答えを探している人のために、これはスパース行列用です: OpenOF、「GPU でのスパース非線形最小二乗最適化のフレームワーク」
CPU に対する g2o とは、GPU に対するものです。