4

画像処理アルゴリズムの実装では、次の形式の大規模な線形システムを解く必要がA*x=bあります。

  • 行列A=L+Dは、ラプラシアン行列 L と対角行列 D の和です
  • ラプラシアン行列 L はスパースで、行ごとに約 25 個の非ゼロがあります
  • システムは大規模で、入力イメージ内のピクセルと同じ数の未知数があります (通常 > 100 万)。

ラプラシアン行列 L は、アルゴリズムの連続実行間で変化しません。前処理でこの行列を構築し、おそらくその因数分解を計算できます。対角行列 D と右辺ベクトル b は、アルゴリズムの実行ごとに変化します。

実行時にシステムを解決する最速の方法を見つけようとしています。前処理 (たとえば、L の因数分解を計算するため) に時間を費やすことは気にしません。

私の最初のアイデアは、L のコレスキー分解を事前に計算し、実行時に D の値で分解を更新し (cholupdate を使用してランク 1 を更新)、逆置換で問題をすばやく解決することでした。残念ながら、コレスキー分解は元の L 行列ほどスパースではなく、ディスクからロードするだけでもすでに 5.48 秒かかります。比較として、バックスラッシュを使用してシステムを直接解決するには 8.30 秒かかります。

私の行列の形状を考えると、前処理時間にどれだけ時間がかかっても、実行時の解決を高速化するために推奨する他の方法はありますか?

4

1 に答える 1

2

あなたがグリッドで作業していると仮定すると（画像について言及しているため-これは保証されていませんが）、精度よりも速度に関心があると仮定します（100万の未知数に対して5秒はすでに遅すぎるように見えるため）、いくつかのオプションがあります。

まず、Cholesky (+ reordering) などの正確な方法を忘れてください。因数分解を保存して複数の rhs で再利用できる場合でも、ケースでは扱いにくいと思われる巨大な行列を保存する必要がある可能性があります (逆 Cuthill McKee などで行/列を並べ替えていることを願っています)それ以外の場合-それは因数分解を大幅にスパース化します）。

境界条件に応じて、最初にpoisolvFFTを使用してポアソン問題を解くMatlabを試し、周期的な境界条件ではなくディリクレ境界条件が必要な場合は可能な再投影を試します。それは非常に高速ですが、あなたの問題には適切ではないかもしれません（あなたはラプラシアン行列+恒等のために25 nnzを持っていると述べています：なぜですか？それは高次のラプラス行列です。その場合、私が想定するよりも精度に関心があるかもしれません? それとも実際には、あなたが説明したものとは別の問題ですか ?)。

次に、画像と滑らかな問題に対して非常に高速なマルチグリッド ソルバーを試すことができます。各反復とマルチグリッドの各レベルに単純な緩和法を使用するか、より複雑な方法 (たとえば、事前条件付きの共役勾配パー レベル) を使用できます。または、マルチグリッドを使用せずに、より単純な前処理付き共役勾配 (または SSOR) を実行することもできます。近似解のみに関心がある場合は、完全に収束する前に反復を停止できます。

反復ソルバーに対する私の主張は次のとおりです。

  • おおよその問題が必要な場合は、収束前に停止できます
  • 他の結果を再利用してソリューションを初期化することもできます (たとえば、別の実行がビデオの別のフレームに対応する場合、前のフレームのソリューションを次のフレームの初期化として使用することは意味があります)。

もちろん、因数分解を事前計算、保存、および保持できる直接ソルバーも理にかなっています (ただし、行列が定数の場合、ランク 1 の更新に関するあなたの議論は理解できません)。ランタイム。しかし、これが問題の構造 (通常のグリッド、限られた精度の結果への関心の可能性など) を無視していることを考えると、フーリエのような方法やマルチグリッドなど、これらのケース用に設計された方法を選択します。両方の方法を GPU に実装して、より高速な結果を得ることができます (GPU はむしろ画像/テクスチャを処理するように調整されていることを思い出してください!)。

最後に、より数値解析に的を絞ったscicomp.stackexchangeから興味深い回答を得ることができます。

于 2013-02-01T23:57:00.060 に答える