2

次の問題を解決する最速の方法を探しています。

3D グリッド内の格子点の体積が与えられると、いくつかの点b_i(境界) が を満たしf(b_i)=0、別の点a_0が を満たしf(a_0)= 1ます。

他のすべてのポイント (非境界) は、周囲の 26 ポイントの線形結合です。たとえば、私はしたいことができます

f(i, j, k)= .05*f(i+1, j, k)+.1*f(i, j+1, k)+.07*f(i, j, k+1)+...

係数の合計は に.05+.1+.07+...なり1ます。私の目的は、ボリューム内のf(x_i)すべてを解決することです。x_i

現在、私は基本的にボリュームの境界を初期化し、周囲の 26 点の加重平均を各点に割り当て、繰り返す逐次過緩和 (SOR) 法を使用しています。SOR メソッドは、f(x_i)最新の反復f(x_i)後と前の反復後の組み合わせを使用するだけです。

サイズが 102x102x48 前後の 3D グリッドでこの問題を解決するより速い方法を誰かが知っているかどうか疑問に思っていました。SOR は現在、必要なレベルに収束するのに約 500 ～ 1000 回の反復が必要です (使用する係数によって異なります)。私は、matlab、idl、および c++ を最も喜んで使用します。問題を線形システムに変換し、行列法 (BCGSTAB など) を使用する場合と比較して、SOR がどのくらい速いかを知っている人はいますか? また、どのメソッドが最も効果的に (そして簡単に) 並列化されるでしょうか? 私は 250 コアのクラスターにアクセスでき、mpi と c++ を使用して SOR メソッドを並列化しようとしましたが、思ったほどの速度向上は見られませんでした (理想は 100 倍程度です)。この問題の解決をスピードアップするためのアイデアをいただければ幸いです。ありがとう。

4

2 に答える 2

3

マルチスレッドに慣れている場合は、SOR に赤黒スキームを使用すると、かなりの速度向上が得られます。2D の問題では、チェッカーボードを想像してください。赤い四角は黒い四角 (およびおそらくそれ自体) にのみ依存するため、すべての赤い四角を並行して更新し、すべての黒の四角について繰り返すことができます。これは単純な順序付けよりも収束に時間がかかりますが、複数のスレッドに作業を分散できることに注意してください。

共役勾配法は、通常、SOR よりも高速に収束します (私の記憶が正しければ、約 1 桁)。私は BCGSTAB を使用したことはありませんが、GMRES が非対称問題でうまく機能したことを覚えています。おそらく、どちらも前処理の恩恵を受けることができます。

並列化の機会に関しては、ほとんどの CG タイプのメソッドでは、行列とベクトルの積を計算するだけでよいA*xため、完全な行列を作成する必要はありません。これはおそらく各反復の最大のコストであるため、マルチスレッドを検討する必要があります。

これに関する 2 つの良い参考文献は、Golub と Van Loan、およびTrefethen と Bauです。後者ははるかに読みやすい IMHO です。

それが役立つことを願っています...

于 2011-07-08T06:40:01.760 に答える
2

私は（私が思うに）正確な解決策を持っていますが、それは長くなるかもしれません. 主な問題は、非常に大きな (そして願わくば疎な) 行列での計算です。

Nボリュームにポイントがあるとしましょう。p1...pNこれらの点を呼びましょう。あなたが探しているのはf(p1)...f(pN)

ポイントを取りましょうpi。それは26の隣人を持っています。それらを呼びましょうpi-1...pi-26。pi各ポイントから線形結合の係数にアクセスできると思います。それらを呼びましょう（「そのj番目の隣人へci-1...ci-j...ci-26のポイントの線形結合の係数」のために）pi

さらにうまくやりましょう。これは、空間内のすべてpiのポイントの線形結合であると考えることができます。ただし、それらのほとんど (26 を除く) は 0 に等しくなります。係数 があります。ci-1...ci-N

N*Nこれらのci-j係数の大きな行列を作成できるようになりました:

+---------------------    -------+   
|  0  | c1-2 | c1-3 | ... | c1-N |   |f(p1)|    |f(p1)|
+---------------------    -------+   |     |    |     |
| c2_1|   0  | c2-3 | ... | c1-N |   |f(p2)|    |f(p2)|
+---------------------    -------+ * .     . =  .     .
|                                |   .     .    .     .
.                                .   .     .    .     .
+---------------------    -------+   .     .    .     .
| cN-1| cN-2 | cN-3 | ... |   0  |   |f(pN)|    |f(pN)|
+---------------------    -------+

すばらしい！あなたが探している解は、固有値 1 に対応する固有ベクトルの 1 つです!

(疎行列の場合) 固有ベクトルを効率的に計算する最適化された行列ライブラリを使用し、それが既に並列化されていることを願っています!

編集：面白い、あなたの投稿を読み直したところ、BCGSTABソリューションを提供したようです...申し訳ありません！^^

再編集：実際、よくわかりませんが、「双共役勾配安定化法」について話しているのですか？勾配降下法を行っている場合、あなたが話している線形法が表示されないため...

再編集 : 私は数学が大好きです =) sum of the ci = 11 が実際には固有値であるという条件を考えれば、それを証明することさえできます。対応する空間の次元はわかりませんが、少なくとも1です！

于 2011-07-07T14:35:48.637 に答える