最小瓦片排序

Question

最小瓦片排序

algorithmpermutationcombinatoricssparse-matrix

4

最小化瓷砖重排问题：

假设我有以下对称的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:

莫顿曲线：

- proteneer

刚想到的一个想法（还没喝第一杯咖啡，所以别期望太高）- 如果贪心重排序算法不是最优的，模拟退火通常可以得到良好的结果。也就是说，对于每个可能的“移动”（列/行），你能得到多少改进？ - Rafe

通常情况下，单个列/行交换很难（几乎不可能）提高得分，其中得分是要计算的TxT瓷砖数量。在现实情况下，大多数瓷砖已经至少有两个1。单次交换可能永远无法移除一个瓷砖。更好的评分函数肯定会有所帮助。 - proteneer

@BobBryan 更好的说明方法是考虑一个元组的邻居列表：(1,2) (2,9) (4,5) (4,6) (5,8) (7,8)，这些都是对称的，因此它隐含地意味着存在一个 (2,1) (9,2) (5,4) 等等。两个矩阵都代表了这个邻居列表。 - proteneer

@proteneer：当您说莫顿曲线时，能否更具体一些？这是Z顺序莫顿曲线还是将4个希尔伯特曲线拼接在一起形成的以美国数学家命名的莫顿曲线？ - Micromega

@Chiyou 通过交错3组位生成的Z-Order曲线 - proteneer

显示剩余5条评论

2个回答

0

你可以寻找像kd-tree、R-tree、quadtree或者空间填充曲线这样的数据结构。特别是空间填充曲线可以帮助减少维度，重新排序瓦片，从而向网格添加一些新信息。对于9x9网格，最好研究Peano曲线。Z顺序Morton曲线更适用于2的幂次方网格。

- Micromega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- angainor · Accepted Answer

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

(反转)卡瑟尔-麦基算法可以减少矩阵的带宽，使得条目靠近对角线。
近似最小度数算法 - 一种轻量级的填充减少重排序算法。
稀疏LU/LL'分解的填充减少重排序(METIS, SCOTCH) - 计算量较大。
空间填充曲线重排序(类似于这些内容)
二维问题使用四叉树或三维问题使用八叉树 - 您将粒子分配给四叉树/八叉树，然后根据四叉树/八叉树ID编号，类似于空间填充曲线。
自避行走算法用于在结构化网格上遍历网格点，使得所有点仅被访问一次。
在稀疏矩阵向量乘法的背景下，对稀疏矩阵条目进行分块的研究很多。许多研究人员尝试找到好的重排序方法（我对该主题没有完美的概述，但请查看这篇论文）。

所有这些方法都倾向于在您的矩阵中找到结构，并以某种方式对非零条目进行分组。由于您说您处理粒子，这意味着由于粒子相互作用的空间局部性，您的连通图在某种意义上是“本地的”。在这种情况下，这些方法应该很有用。

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

编辑让我简要介绍一下几张图片。我创建了一个由20节点砖元素组成的3D结构化笛卡尔网格。我匹配了网格的大小，使其类似于您的（~1000个节点）。此外，每行非零条目的数量不太远（我这里是51-81，您这里是59-81，但两者具有非常不同的分布）下面的图片显示了非周期网格（左侧）和具有完全x-y-z周期性的网格（右侧）的RCM和METIS重新排序： RCM reordering

下一张图片展示了使用METIS和填充减少重新排序后的相同矩阵。

metis reordering

差异显著 - 周期性造成的不良影响十分明显。现在，您的矩阵已经通过RCM和METIS重新排序。

enter image description here

哇，你有一个问题 :) 首先，我认为你的rcm有些问题，因为我的看起来不同 ;) 另外，我确定你不能根据这个特定的矩阵得出任何有关重新排序的一般且有意义的结论。这是因为你的系统规模非常小（少于大约10x10x10个点），而且你的粒子之间似乎存在相对较长程的相互作用。因此，在这样一个小系统中引入周期性比在我的结构化情况下看到的重新排序效果更加强烈。

我建议从关闭周期性开始寻找好的重新排序方法。一旦你有了一个令你满意的重新排序，再引入周期性相互作用。在你展示的系统中，几乎没有什么东西除了周期性：因为它非常小，并且你的相互作用相对较长程，至少与我的网格相比如此。在更大的系统中，周期性对模型中心的影响会更小。

虽然较小，但仍然是负面的。也许你可以改变周期性的方法？而不是在矩阵中明确包含周期性连接，可以构造和重新排序一个没有这些连接的矩阵，并引入将周期性粒子绑定在一起的显式方程，例如：

V_particle1 = V_particle100

或者换句话说

V_particle1 - V_particle100 = 0

将这些方程式添加到矩阵的末尾。这种方法称为Lagrange乘数法。以下是我的系统的演示。

enter image description here

你可以保留非周期系统的重新排序，而周期性连接则局限在矩阵末尾的一个块中。当然，你也可以将其用于任何其他重新排序。

下一个想法是，你从重新排序的非周期系统开始，并通过将它们添加到它们映射到的行中来明确消除周期节点的矩阵行。当然，你还应该消除列。

这取决于你对矩阵的操作方式。例如，拉格朗日乘数在对角线上引入了0 - 并非所有求解器都喜欢那样做。

无论如何，这是非常有趣的研究。我认为，由于问题的特殊性质（据我所知 - 在3D中不规则放置的粒子，具有相当长程的相互作用），很难对矩阵条目进行分组。但我非常好奇你最终会做什么。请告诉我！