algorithm - 最小タイル順序

Question

タイルの並べ替え問題の最小化:

次の対称 9x9 行列、N 粒子間の N^2 相互作用があるとします。

(1,2) (2,9) (4,5) (4,6) (5,8) (7,8), 

これらは対称的な相互作用であるため、以下が存在することを暗黙のうちに意味します。

(2,1) (9,2) (5,4) (6,4) (8,5) (8,7),

私の問題では、それらがマトリックス形式で配置されているとします。ここでは、上の三角形のみが表示されます。

t       0     1     2     (tiles)
  #   1 2 3 4 5 6 7 8 9   
  1 [ 0 1 0 0 0 0 0 0 0 ]
0 2 [ x 0 0 0 0 0 0 0 1 ]
  3 [ x x 0 0 0 0 0 0 0 ]
  4 [ x x x 0 1 1 0 0 0 ] 
1 5 [ x x x x 0 0 0 1 0 ]
  6 [ x x x x x 0 0 0 0 ]
  7 [ x x x x x x 0 1 0 ]
2 8 [ x x x x x x x 0 0 ]
  9 [ x x x x x x x x 0 ] (x's denote symmetric pair)

3x3 タイルで計算される操作があり、少なくとも 1 つの 1 を含む 3x3 はすべて計算する必要があります。上記の例では、少なくとも 5 つのタイルが必要です: (0,0)、(0,2)、(1,1)、(1,2)、(2,2)

ただし、入力を並べ替えて、3 番目と 9 番目の列 (および対称行列であるため行も) を入れ替えると、次のようになります。

t       0     1     2
  #   1 2 9 4 5 6 7 8 3 
  1 [ 0 1 0 0 0 0 0 0 0 ]
0 2 [ x 0 1 0 0 0 0 0 0 ]
  9 [ x x 0 0 0 0 0 0 0 ]
  4 [ x x x 0 1 1 0 0 0 ] 
1 5 [ x x x x 0 0 0 1 0 ]
  6 [ x x x x x 0 0 0 0 ]
  7 [ x x x x x x 0 1 0 ]
2 8 [ x x x x x x x 0 0 ]
  3 [ x x x x x x x x 0 ] (x's denote symmetric pair)

これで、(0,0)、(1,1)、(1,2)、(2,2) の 4 つのタイルを計算するだけで済みます。

一般的な問題:

NxN 疎行列が与えられた場合、計算する必要がある TxT タイルの数を最小限に抑えるための並べ替えを見つけます。N が T の倍数であると仮定します。最適ではあるが実行不可能な解は、N! 入力順序の順列。

ヒューリスティックについては、帯域幅最小化ルーチン (Reverse CutHill McKee など)、Tim Davis の AMD ルーチンを試しましたが、これまでのところ役に立ちませんでした。ここでは、対角化が正しいアプローチではないと思います。

サンプルの開始マトリックスを次に示します。

http://proteneer.com/misc/out2.dat

ヒルベルト曲線:

RCM:

モートン曲線:

Answer 1

あなたが試すことができるいくつかのよく知られたオプションがあります（それらのいくつかはあなたが持っていますが、それでも）：

• （逆）Cuthill-McKeeは行列の帯域幅を減らし、エントリを対角線に近づけました。
• 近似画像最小次数-軽量の塗りつぶしを減らす並べ替え。
• スパースLU/LL'分解（METIS、SCOTCH）の塗りつぶしを減らす並べ替え-計算量が非常に多い。
• 空間充填曲線の並べ替え（これらの行の何か）
• 2Dの場合は四分木、3Dの場合は八分木-ある意味で空間充填曲線と同様に、粒子を四分木/八分木に割り当て、後で四分木/八分象限に従って番号を付けます。
• 自己回避ウォークは、構造化されたグリッドで使用され、すべてのポイントが1回だけ訪問されるような順序でグリッドポイントをトラバースします。
• スパース行列エントリのブロックに関する多くの研究は、スパース行列-ベクトル乗算のコンテキストで行われました。研究者の多くは、その目的のために適切な並べ替えを見つけようとしました（私はその主題について完全な概要を持っていませんが、例えばこの論文を見てください）

それらはすべて、マトリックス内の構造を見つける傾向があり、ある意味でゼロ以外のエントリをグループ化します。粒子を扱うと言うので、粒子の相互作用の空間的な局所性のために、接続グラフはある意味で「局所的」であることを意味します。この場合、これらの方法が有効に役立つはずです。

もちろん、それらは問題の正確な解決策を提供しません:)しかし、実際には非常に優れた並べ替えが得られるため、まさにそのような場合に一般的に使用されます。あなたが試した方法が失敗したとはどういう意味ですか？最適な解決策を見つけることを期待していますか？確かに、それらはランダム行列の順序付けと比較して状況を改善します。

編集簡単にいくつかの写真を見てみましょう。20ノードのブリック要素で構成される3D構造化デカルトメッシュを作成しました。メッシュのサイズを自分のものと同じになるように一致させました（〜1000ノード）。また、行ごとのゼロ以外のエントリの数はそれほど遠くありません（私の場合は51-81、あなたの場合は59-81ですが、どちらも分布が大きく異なります）下の写真は、非周期的メッシュのRCMとMETISの並べ替えを示しています（左）、および完全なxyz周期性を持つメッシュの場合（右）：

次の図は、METISを使用して並べ替えられた同じマトリックスと塗りつぶしを減らす並べ替えを示しています

違いは顕著です-周期性の悪影響は明らかです。これで、マトリックスがRCMとMETISで並べ替えられました

おお。あなたには問題があります:)まず、私のrcmに何か問題があると思います。私のものは異なって見えるからです;）また、この特定のマトリックスに基づく並べ替えについて、一般的で意味のあることを結論付けることはできないと確信しています。これは、システムサイズが非常に小さく（約10x10x10ポイント未満）、パーティクル間に比較的長距離の相互作用があるように見えるためです。したがって、このような小さなシステムに周期性を導入すると、構造化された場合に見られるよりも、並べ替えにはるかに強い悪影響があります。

周期性をオフにして、適切な並べ替えの検索を開始します。満足のいく並べ替えができたら、定期的なやり取りを導入します。あなたが示したシステムでは、周期性しかありません。それは非常に小さく、少なくとも私のメッシュと比較して、相互作用がかなり長距離であるためです。はるかに大規模なシステムでは、周期性によるモデルの中心への影響は小さくなります。

小さいですが、それでもマイナスです。多分あなたは周期性へのあなたのアプローチを変えることができますか？周期的な接続性をマトリックスに明示的に含める代わりに、それらを含まないマトリックスを作成して並べ替え、周期的な粒子を結合する明示的な方程式を導入します。例：

V_particle1 = V_particle100

または言い換えれば

V_particle1 - V_particle100 = 0

行列の最後にこれらの方程式を追加します。この方法は、ラグランジュ乗数と呼ばれます。これが私のシステムを探す方法です

非周期システムの並べ替えを維持すると、周期的な接続性がマトリックスの最後のブロックにローカライズされます。もちろん、他の再注文にも使用できます。

次のアイデアは、並べ替えられた非周期システムから始めて、周期ノードの行列行を、それらがマップされている行に追加することによって明示的に削除することです。もちろん、列も削除する必要があります。

これらを使用できるかどうかは、マトリックスで何をするかによって異なります。たとえば、ラグランジュ乗数は対角線上に0を導入します-そのようなすべてのソルバーではありません。

とにかく、これは非常に興味深い研究です。問題の詳細（私が理解しているように、3Dで不規則に配置された粒子、かなり長距離の相互作用）のために、マトリックスエントリをグループ化することは非常に困難だと思います。しかし、私はあなたが最終的に何をするのか非常に興味があります。私にお知らせください！

Answer 2

kd-tree、R-tree、quadtree、空間充填曲線などのデータ構造を探すことができます。特に空間充填曲線は、寸法を縮小し、タイルを並べ替えることでグリッドに新しい情報を追加できるため、役立ちます。9x9 グリッドでは、ペアノ曲線を調べるのがおそらく良いでしょう。z オーダーのモートン曲線は、2 乗グリッドの方が優れています。