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 的 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)

现在我只需要计算 4 个图块：(0,0)、(1,1)、(1,2)、(2,2)。

一般问题：

给定一个 NxN 稀疏矩阵，找到一个重新排序以最小化必须计算的 TxT 瓦片的数量。假设 N 是 T 的倍数。通过尝试 N 可以找到最优但不可行的解决方案！输入排序的排列。

对于启发式方法，我尝试了带宽最小化例程（例如 Reverse CutHill McKee）、Tim Davis 的 AMD 例程，但到目前为止都无济于事。我不认为对角化是正确的方法。

这是一个示例起始矩阵：

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

希尔伯特曲线：

RCM：

莫顿曲线：

Answer 1

您可以尝试几个众所周知的选项（其中一些您有，但仍然）：

• （反向）Cuthill-McKee减少了矩阵带宽，使条目靠近对角线。
• Approximage 最小度数- 一种轻量级的减少填充的重新排序。
• 稀疏 LU/LL' 分解（ METIS，SCOTCH ）的填充减少重新排序- 计算量很大。
• 空间填充曲线重新排序（这些行中的内容）
• 用于 2D 的四叉树或用于 3D 问题的八叉树 - 您将粒子分配给四边形/八分圆，然后根据四边形/八分圆 id 对它们进行编号，在某种意义上类似于空间填充曲线。
• Self Avoiding Walk用于结构化网格以遍历网格点，以便所有点仅访问一次
• 在稀疏矩阵向量乘法的背景下，已经进行了大量关于阻塞稀疏矩阵条目的研究。许多研究人员试图为此目的找到良好的重新排序（我没有关于该主题的完美概述，但请看一下例如这篇论文）

所有这些都倾向于在您的矩阵中找到结构，并且在某种意义上将非零条目分组。既然你说你处理粒子，这意味着你的连接图在某种意义上是“局部的”，因为粒子相互作用的空间局部性。在这种情况下，这些方法应该很有用。

当然，它们并没有提供问题的确切解决方案 :) 但是它们通常用于这种情况，因为它们在实践中产生了非常好的重新排序。我想知道你说你尝试的方法失败了是什么意思？您希望找到最佳解决方案吗？当然，与随机矩阵排序相比，它们改善了这种情况。

编辑让我简单地看几张照片。我创建了一个由 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、四叉树或空间填充曲线这样的数据结构。尤其是空间填充曲线可以提供帮助，因为它可以减少维度并重新排列图块，从而可以向网格添加一些新信息。使用 9x9 网格，查看 peano 曲线可能会很好。z 阶莫顿曲线更适合 2 个网格的功率。