最小化磁贴重新排序问题：
假设我有以下对称的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公司：
莫顿曲线：
最佳答案
有几个众所周知的选择你可以尝试（其中一些你有，但仍然）：
(Reverse) Cuthill-McKee减少矩阵带宽，使条目接近对角线。
Approximage Minimum Degree-重量轻的填充物减少了重新排序。
稀疏lu/ll'分解的填充减少重排序（METIS，SCOTCH）-相当重的计算量。
空间填充曲线重新排序（在these lines中）
二维四叉树或三维问题的oct树-将粒子指定给四叉/八叉，然后根据四叉/八叉ID对其进行编号，在某种意义上类似于空间填充曲线。
Self Avoiding Walk用于结构化网格，以仅访问一次所有点的顺序遍历网格点
在稀疏矩阵矢量乘法的背景下，对稀疏矩阵的分块问题进行了大量的研究。许多研究人员已经试图找到好的重新排序的目的（我没有对这个主题的完美概述，但有一个看看，例如this paper）
所有这些都倾向于在矩阵中找到结构，并在某种意义上对非零项进行分组。因为你说你处理粒子，这意味着你的连通图在某种意义上是“局部的”，因为粒子相互作用的空间局部性。在这种情况下，这些方法应该很有用。
当然，它们并不能提供问题的精确解决方案：）但是它们通常用于这种情况，因为它们在实践中产生了非常好的重新排序。我想知道你说你尝试的方法失败是什么意思？你希望找到最佳的解决方案吗？当然，与随机矩阵排序相比，它们改善了这种情况。
编辑让我简单地浏览几张图片。我创建了一个由20个节点砖元素组成的三维结构笛卡尔网格。我匹配网格的大小，使其与您的网格相似（约1000个节点）。此外，每行的非零条目数也不算太远（在我的情况下是51-81，在你的情况下是59-81，但是两者的分布都非常不同），下面的图片显示了非周期网格（左）和完全x-y-z周期网格（右）的rcm和metis重排序：
下图显示了使用metis和fill reduceing重新排序的相同矩阵
差别是惊人的——周期性的不良影响是显而易见的。现在你的矩阵用rcm和metis重新排序
真的。你有一个问题：）首先，我认为你的RCM有问题，因为我的看起来不一样；）而且，我确信你不能得出任何关于基于这个特定矩阵的任何重新排序的一般和有意义的结论。这是因为你的系统尺寸很小（小于大约10x10x10个点），而且你的粒子之间似乎有相对长的相互作用。因此，在这样的小系统中引入周期性对重新排序的负面影响要比在我的结构化案例中看到的强得多。
我将通过关闭周期性来开始搜索良好的重新排序。一旦你有一个满足你的重新排序，引入周期性的交互作用。在你展示的系统中，几乎只有周期性：因为它非常小，而且你的交互作用相当长，至少和我的网格相比。在大得多的系统中，周期性对模型中心的影响较小。
更小，但仍然是负数。也许你可以改变你对周期性的看法？与其在矩阵中显式地包含周期连接，不如构造和重新排序不包含这些的矩阵，并引入将周期粒子绑定在一起的显式方程，例如：
V_particle1 = V_particle100
或者换句话说
V_particle1 - V_particle100 = 0
把这些方程加到矩阵的末尾。这种方法叫做拉格朗日乘子法。这是我的系统的外观
保持非周期系统的重新排序，周期连接在矩阵末尾的块中局部化。当然，您可以将其用于任何其他重新排序。
下一个想法是从重新排序的非周期系统开始，通过将周期节点的矩阵行添加到映射到的行中，显式地消除它们。当然，还应该删除列。
你能否使用这些取决于你对矩阵做了什么。例如，拉格朗日乘子在对角线上引入0-不是所有的解算器都是这样。
无论如何，这是一项非常有趣的研究。我认为，由于你的问题的特殊性（据我所知，不规则地在3d中放置粒子，具有相当长的交互作用），使得矩阵项的分组非常困难。但我很好奇你最后会做什么。请告诉我！