Fill-reducing for regular 9-point stencil grid

When using 9-point stencil finite difference or finite element method, every vertex has 8 neighbors except ones on the boundary. In the picture in previous blog, every smallest square is a clique in 9-point grid. Regular 9-point grid is what Nested Dissection was invented for originally[1]. 5-point grid and 9-point grid are quite different for fill-reducing. As the benchmark shows, MESHND performs very well except the very small grids for 9-point grid. Though MESHND is so good in this condition, further improvement can be achieved.
9-point grid
For fill-reducing, minimal separators are essential[2]. Original Nested Dissection, which MESHND implemented, uses horizontal or vertical lines as separators and for every subgraph, heuristically the line dividing the subgraph equally is chosen. Considering MESHND is so good for 9-point grid, it is acceptable to restrict the separators to be horizontal or vertical lines. But it is better to choose the line resulting minimum fill-in directly.

In the grid, a rectangle C_0, whose neighbor is S_0, can be separated into two smaller rectangles C_1 and C_2 by a horizontal or vertical line S. Compared with fill-in, nonzeros in the factorization can be calculated more straightforward. The minimum nonzeros of C_0
\mathrm{mnz}(C_0) = \min_S \left(\mathrm{nz}(S)+\mathrm{mnz}(C_1)+\mathrm{mnz}(C_2)\right)
\mathrm{nz}(S) is the nonzeros of S
\mathrm{nz}(S) = \mathrm{tr}\left(|S_0|+|S|\right)-\mathrm{tr}\left(|S_0|\right)
where \mathrm{tr}(n) means the n\mathrm{th} triangular number(the sum of natural numbers from 1 to n). This is based on an observation, off-diagonal nonzeros is the surrounding vertices ordered after the vertex. This definition of surrounding depends on the connection. For example, in the ordering below, for 5-point grid, off-diagonal nonzeros of Vertex 20 are {40,43,45,49}, and for 9-point grid, they are {21,29,30,40,41,42,43,44,45,46,47,48,49}. When S is in the neighbor of S_0, it is not a separator of C_0 and the above formulas can not be applied directly. In this special case, at least one smaller rectangle is empty and \mathrm{nz}(S) is not difficult to calculate with the observation. Nonzeros of a rectangle is only determined by it width, height and the shape of its neighbor and there are only a few different shapes of the neighbor of a rectangle. For s\times t grid, all the rectangles k\times l, k\leq s, l\leq t need to be computed. k\times l rectangle has k+l horizontal or vertical lines. So the time complexity of this method is \mathcal{O}(s^2 t+t^2 s). Further details can be seen in the code of the demo. When the grid is large, it costs a lot of DOM operations to display the ordering. To save time, mnz(s,t,0,0) can be called to return the minimum nonzeros of s&timest grid in the JavaScript console if it is not necessary to display the ordering.

Table 1. An ordering of 7×7 grid
23 24 41 2 7 5 3
25 26 42 8 9 6 4
27 28 21 43 1 47 48
22 39 40 20 45 17 11
38 37 29 49 10 18 16
33 34 36 44 19 15 13
31 32 35 30 46 14 12

This method can be extended to more general case. C_0 can be any component and S is its separator. The object can be changed to operations in the factorization, which is the quadratic sum of nonzeros of all vertices. This is also included in the demo, though commented out. Minimizing operations leads to a different ordering but it will not be discussed here.

The ordering shown in the demo is only one of many cases resulting minimum fill-in. When the grid is very small, AMD is better than MESHND. But the method proposed here surpasses both methods in all cases I have tested(Table 2, Table 3). The improvement over MESHND is very small (only 3-4 percent) for large square grid(Table 2). So in this case where Nested Dissection originate, though dividing the graph equally is not the best choice, it is only little worse than the best choice.

Table 2. Nonzeros of s×s grid
s AMD Metis MESHND Proposed Method
7 3.29E+02 3.50E+02 3.54E+02 3.18E+02
15 2.65E+03 2.95E+03 2.78E+03 2.61E+03
31 1.75E+04 1.97E+04 1.77E+04 1.69E+04
63 1.02E+05 1.10E+05 9.95E+04 9.56E+04
127 5.73E+05 5.65E+05 5.19E+05 5.00E+05
255 3.24E+06 2.76E+06 2.57E+06 2.48E+06
511 1.70E+07 1.36E+07 1.23E+07 1.19E+07
1023 8.55E+07 6.12E+07 5.72E+07 5.54E+07

When the grid is not square, the improvement is more significant as the aspect ratio increases(Table 3). It is interesting that relative difference between AMD and MEHSND also becomes larger as the aspect ratio increases(Table 3).

Table 3. Nonzeros of 31×s grid
s AMD Metis MESHND Proposed Method
63 4.06E+04 4.56E+04 4.12E+04 3.91E+04
127 8.68E+04 9.87E+04 9.01E+04 8.39E+04
255 1.79E+05 2.11E+05 1.90E+05 1.74E+05
511 3.64E+05 4.31E+05 3.91E+05 3.53E+05
1023 7.33E+05 7.96E+05 7.96E+05 7.12E+05

The minimum fill-in of s\times s grid is \mathcal{O}\left(s^2 \log s\right)[3]. Regressing the result of this method, the minimum fill-in of s\times t grid may be \mathcal{O}\left(st\log\left(\min(s,t)\right)\right). As pointed out, AMD is a good complement for Nested Dissection, not only when the grid is too small, but also when the grid is too slim. I suppose that the distance is important for fill-reducing, not only the size. A square is a disc for 9-point grid. In Nested Dissection, a disc is split into 4 smaller discs and every smaller disc is further split, which produces very good result. When the shape is different, maybe some other skills can be added to improve the result.

[1] A. George, Nested dissection of a regular finite-element mesh.
[2] V. Bouchitté, I. Todinca, Treewidth and minimum fill-in grouping the minimal separators.
[3] A. George, J. Liu, E. Ng, Computer Solution of Sparse Linear Systems.

This entry was posted in Sparse matrix and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s