最小瓷砖订购 [英] Minimum Tile Ordering

问题描述

假如我有如下对称9x9的矩阵，N粒子之间的N ^ 2交互：

Suppose I had the following symmetric 9x9 matrix, N^2 interactions between N particles:

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

这些都是对称的相互作用，因此它含蓄地暗示着存在：

These are symmetric interactions, so it implicitly implies that there exists:

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

在我的问题，假设它们被排列成矩阵形式，只有上部三角形示出其中：

In my problem, suppose they are arranged in matrix form, where only the upper triangle is shown:

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)

我有一些操作是真实计算在3×3的瓷砖，并且包含至少一个单1必须完全计算任何的3x3。上面的例子中，需要至少5瓦：（0,0），（0,2），（1,1），（1,2），（2,2）

I have some operation that's computed in 3x3 tiles, and any 3x3 that contains at least a single 1 must be computed entirely. The above example requires at least 5 tiles: (0,0), (0,2), (1,1), (1,2), (2,2)

不过，如果我换第3和第9列（而且随着自对称矩阵的行）由permutating我输入：

However, if I swap the 3rd and 9th columns (and along with the rows since its a symmetric matrix) by permutating my input:

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）

Now I only need to compute 4 tiles: (0,0), (1,1), (1,2), (2,2).

一般问题：

给定的N×N的稀疏矩阵，找到一个重新排序，以最小化的TXT瓦片必须计算的数目。假设N为T.最优，但不可行的倍数，溶液可以通过尝试从上述N找到！输入顺序的排列。

Given an NxN sparse matrix, finding an re-ordering to minimize the number of TxT tiles that must be computed. Suppose that N is a multiple of T. An optimal, but unfeasible, solution can be found by trying out the N! permutations of the input ordering.

有关启发式，我已经试过带宽最小化程序（如反向CutHill麦基），蒂姆·戴维斯的AMD套路，至今无果。我不认为对角化是正确的做法在这里。

For heuristics, I've tried bandwidth minimization routines (such as Reverse CutHill McKee), Tim Davis' AMD routines, so far to no avail. I don't think diagonalization is the right approach here.

下面是一个示例出发矩阵：

Here's a sample starting matrix:

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

希尔伯特曲线：

Hilbert Curve:

RCM：

RCM:

莫顿曲线：

Morton Curve:

推荐答案

有几个著名的选项，你可以尝试（其中一些你有，但仍）：

There are several well-known options you can try (some of them you have, but still):

• （反向）Cuthill - 麦基减少矩阵带宽，保持条目接近对角线。
• Approximage最小度 - 重量轻补平泻重新排序。
• 补平泻重新排序稀疏LU / LL'分解（ METIS ， 苏格兰威士忌） - 相当重计算
• 在空间填充曲线重新排序（东西这些行的）
• 四树木2D或辛树三维问题 - 你根据四/八分区ID，类似的空间感填充曲线分配颗粒四边形/八分圆，后来它们编号
。
• 自回避行走用于结构化网格遍历网格点的先后次序所有点都仅去过一次
• 大量的研究阻断稀疏矩阵项已在稀疏矩阵向量乘法的背景下完成的。许多研究人员试图找到很好的重新排序为目的（我没有在这个问题上完美的概述，但是看看如<一个href="http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CB4QFjAA&url=http%3A%2F%2Fwww.sandia.gov%2F~apinar%2Fpapers%2FSC99.pdf&ei=kpdlUMG9MaTO4QSimYHYBg&usg=AFQjCNHc2sywnUJ3C07B3tJJ_cy6LiVt5A&sig2=pdfw0_yXrIN1ENUDsyt8dQ&cad=rja"相对=nofollow>本文）

• (Reverse) Cuthill-McKee reduced the matrix bandwidth, keeping the entries close to the diagonal.
• Approximage Minimum Degree - a light-weight fill-reducing reordering.
• fill-reducing reordering for sparse LU/LL' decomposition (METIS, SCOTCH) - quite computationally heavy.
• space filling curve reordering (something in these lines)
• quad-trees for 2D or oct-trees for 3D problems - you assign the particles to quads/octants and later number them according to the quad/octant id, similar to space filling curves in a sense.
• Self Avoiding Walk is used on structured grids to traverse the grid points in such order that all points are only visited once
• a lot of research in blocking of the sparse matrix entries has been done in the context of Sparse Matrix-Vector multiplication. Many of the researchers have tried to find good reordering for that purpose (I do not have the perfect overview on that subject, but have a look at e.g. this paper)

所有那些往往会发现结构在基体和在某种意义上组非零的条目。既然你说你处理的颗粒，这意味着你的连接图是因为粒子相互作用的空间局部性在一定意义上的本地。在这种情况下，这些方法应该是很好的利用。

All of those tend to find structure in your matrix and in some sense group the non-zero entries. Since you say you deal with particles, it means that your connectivity graph is in some sense 'local' because of spatial locality of the particle interactions. In this case these methods should be of good use.

当然，他们不提供这个问题的精确解:)但他们究竟在这种情况下，常用的，因为它们产生非常好的reorderings在实践中。我不知道你说你试过失败的方法是什么意思？你期望找到最佳的解决方案？当然，它们改善情况相比，随机矩阵排序

Of course, they do not provide the exact solution to the problem :) But they are commonly used in exactly such cases because they yield very good reorderings in practice. I wonder what do you mean by saying the methods you tried failed? Do you expect to find the optimum solution? Surely, they improve the situation compared to a random matrix ordering.

修改请允许我简要经历了几张照片。我创建了一个三维结构化笛卡尔网格的20节点块单元组成。我匹配网格的大小，以便它是类似于你（〜1000个节点）。此外，每行是不是太离谱的非零条目数（在我的情况51-81，你的情况59至81，但两者有非常不同的分布）下图显示RCM的图片和METIS reorderings对于非周期网格（左）和网状完全XYZ周期（右）：

Edit Let me briefly go through a few pictures. I have created a 3D structured cartesian mesh composed of 20-node brick elements. I matched the size of the mesh so that it is similar to yours (~1000 nodes). Also, number of non-zero entries per row are not too far off (51-81 in my case, 59-81 in your case, both however have very different distributions) The pictures below show RCM and METIS reorderings for non-periodic mesh (left), and for mesh with complete x-y-z periodicity (right):

下图为同一矩阵使用梅蒂斯人和补平泻重新排序重新排序

Next picture shows the same matrix reordered using METIS and fill-reducing reordering

区别是巨大的 - 周期性的不利影响是显而易见的。现在，你的矩阵重新排序与RCM和METIS

The difference is striking - bad impact of periodicity is clear. Now your matrix reordered with RCM and METIS

WOW。你有:)首先一个问题，我觉得有什么不对您的RCM，因为我的是不同的;）另外，我敢肯定，你不能断定任何东西一般意义的有关基于这个特殊矩阵中的任何重新排序。这是因为你的系统尺寸非常小（小于约10x10x10分），你似乎有你的颗粒之间相对长程相互作用。因此，引入周期性成这样的小系统上重新排序比被认为是在我的结构的情况下更强大的负面影响。

WOW. You have a problem :) First of all, I think there is something wrong with your rcm, because mine looks different ;) Also, I am certain that you can not conclude anything general and meaningful about any reordering based on this particular matrix. This is because your system size is very small (less than roughly 10x10x10 points), and you seem to have relatively long-range interactions between your particles. Hence, introducing periodicity into such small system has a much stronger bad effect on reordering than is seen in my structured case.

我会通过关闭周期开始寻找一个很好的重新排序。一旦你有一个重新排序满足你，引入定期互动。在你表现出的系统，几乎没有任何的但的周期：因为它是非常SMaL公司因为你的互动是相当长的距离，至少比我的网格。在更大的系统周期性会对模型的中心的较小的效果。

I would start the search for a good reordering by turning off periodicity. Once you have a reordering that satisfies you, introduce periodic interactions. In the system you showed there is almost nothing but periodicity: because it is very smal and because your interactions are fairly long-range, at least compared to my mesh. In much larger systems periodicity will have a smaller effect on the center of the model.

较小，但仍为负值。也许你可以改变你的方法，以周期性？相反，明确包括矩阵定期连通性的，建造和重新排列矩阵没有这些，引入明确的微分方程的周期颗粒结合在一起，例如：

Smaller, but still negative. Maybe you could change your approach to periodicity? Instead of including periodic connectivities explicitly in the matrix, construct and reorder a matrix without those and introduce explicit equations binding the periodic particles together, e.g.:

V_particle1 = V_particle100

或者换句话说

or in other words

V_particle1 - V_particle100 = 0

和添加这些方程在你的矩阵的末端。这种方法被称为拉格朗日乘子。下面是它如何查找我的系统

and add those equations at the end of your matrix. This method is called the Lagrange multipliers. Here is how it looks for my system

您保持非周期性系统的重新排序和周期性连通性是在基体的端部定位于一块。当然，你可以将其用于任何其它reorderings。

You keep the reordering of the non-periodic system and the periodic connectivities are localized in a block at the end of the matrix. Of course, you can use it for any other reorderings.

接下来想法是开​​始时使用重排序非周期系统和明确地消除用于定期节点矩阵中的行通过将其添加到他们被映射到的行。当然，你也应该消除列。

The next idea is you start with a reordered non-periodic system and explicitly eliminate matrix rows for the periodic nodes by adding them into the rows they are mapped onto. You should of course also eliminate the columns.

您是否可以使用这些取决于你怎么做你的矩阵。拉格朗日乘子例如在对角线引进0 - 样，并非所有的解决者。

Whether you can use these depends on what you do with your matrix. Lagrange multiplier for example introduce 0 on the diagonal - not all solvers like that..

无论如何，这是非常有趣的研究。我想是因为你的问题的具体情况是（我的理解是 - 不规则地放置粒子3D，具有相当长程相互作用）变得非常困难组矩阵元素。但我你最终做的非常好奇。请让我知道！

Anyway, this is very interesting research. I think that because of the specifics of your problem (as I understand it - irregularly placed particles in 3D, with fairly long-range interactions) make it very difficult to group the matrix entries. But I am very curious what you end up doing. Please let me know!

这篇关于最小瓷砖订购的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！