Ordering to singly bordered block diagonal form

In this section, we discuss an algorithm for obtaining a singly bordered block diagonal form as depicted in Figure 9.10.2, where the number of diagonal blocks is a power of two and all blocks are sparse. The merit of this form is that, until the border is reached, the elimination operations for each block row are completely independent of those for the other block rows. Therefore, the block rows may be held separately and the computations on them can be performed in parallel. The form may be imposed on a matrix that does not have it naturally by choosing columns to place in the border. The particular algorithm we discuss is the MONET algorithm of Hu, Maguire, and Blake (2000). This is based on the row graph of the unsymmetric matrix and uses tools very similar to those employed for dissection orderings on symmetric matrices as discussed in Section 9.8.

As in the dissection ordering for symmetric matrices, the algorithm uses nested bisection and it is the bisection algorithm that we now describe. The difference is that here we bisect the set of rows. This combines global knowledge of the problem, obtained through a multilevel approach, with local refinement based on the work of Kernighan and Lin (1970).

Before we consider the coarsening strategy for developing the multilevel scheme, we will first discuss our aims. We seek to partition the rows into two sets such that only a few columns have entries in both sets. By moving these columns to the border, we get the required form. The net-cut is defined as the number of columns with entries in both partitions and will be equal to the number of border columns in the reordered form. The object is then to reduce the width of the border, that is the net-cut, while at the same time maintaining a good balance between the numbers of rows in the two partitions.

Any full or nearly full columns should be moved ab initio to the border and the algorithm applied to the rest of the matrix. Such columns will not cause the algorithm to fail, but will slow it significantly.

The algorithm in Figure 9.10.3 is used to improve a given partition. The value of the net-cut for this partition can be easily calculated. A boundary row is a row in one set of the current partition that is connected in the row graph to a row in the other set of the partition (has an entry in the same column as a row of the other partition). For each row, we can then compute the change in the net-cut value caused if the row were moved to the other partition. This is called the gain by Hu et al. (2000). The fine details of the algorithm are

A summary of the Hu et al. (2000) implementation of the Kernighan and Lin (1970) algorithm in pseudo-algol

Fig. 9.10.3. A summary of the Hu et al. (2000) implementation of the Kernighan and Lin (1970) algorithm in pseudo-algol.

determined by the use that we make of this information. Hu et al. (2000) have experimented with several options and we describe in Figure 9.10.3 the one that, on empirical grounds, they chose to implement in the MONET code. The two main parameters for the algorithm are the number of consecutive uphill steps allowed (maxup) and an upper limit to the number of outer iterations allowed (maxit). Neither parameter is particularly critical; the defaults set in HSL_MC66, the HSL implementation of MONET, are 15 and 10, respectively (although an aggressive option increases these to to and 1000, respectively).

We use this algorithm within a multilevel scheme, as was the case for spectral bisection in the symmetric case. We now consider how the different levels are defined. The strategy used by MONET for coarsening the pattern of the unsymmetric matrix is to recognize and combine pairs of rows that have similar patterns. The algorithm for doing this is given in Figure 9.10.4.

This coarsening is continued until the number of rows in the coarse matrix is less than a preset number (default 100 in HSL_MC66) or the ratio of the number of rows in consecutive matrices is more than a preset fraction (default 0.75 in HSL_MC66).

The MONET approach coarsens the matrix recursively and then applies the Kernighan and Lin algorithm described in Figure 9.10.3 to the graph corresponding to the coarsest matrix from an arbitrary starting partition with roughly equal numbers of rows in its two sets and with its parameters set very high in the hope of getting a near optimal partition on this small matrix. This

A summary of the MONET coarsening algorithm in pseudo-algol

Fig. 9.10.4. A summary of the MONET coarsening algorithm in pseudo-algol.

partition is then prolongated to the next finer graph through expanding the rows that were collapsed in that level of the coarsening. The Kernighan and Lin algorithm of Figure 9.10.3 is then applied with this partition as the starting point and the process is repeated up to the finest graph corresponding to the original matrix. The columns of the net-cut are moved to the border.

As in the case for the symmetric partitioning, this bisection algorithm is then repeated on each of the partitions just computed (excluding the border) until the requisite number of blocks is obtained.

The above algorithm was based on row graphs, but a very similar approach to obtaining a block bordered diagonal form can be developed using hypergraphs. Arguably, the most popular algorithm that uses hypergraphs to partition unsymmetric matrices is PaToH (Aykanat, Pinar, and Catalyurek 2004; Catalyurek and Aykanat 1999). PaToH uses a multilevel algorithm to effect the partitioning. This multilevel hypergraph partitioning method consists of three phases: coarsening, initial partitioning, and uncoarsening. This is essentially the same as we discussed for the case of graph partitioning in Section 9.8. In the coarsening phase, the original hypergraph is coarsened into a smaller hypergraph through a series of coarsening levels. At each coarsening level, strongly connected vertices are grouped into super-vertices of the next level, thus decreasing the sizes of the nets. In the initial partitioning phase, the coarsest hypergraph is partitioned using various heuristics. In the uncoarsening phase, the generated coarse hypergraphs are uncoarsened back to the original, flat hypergraph. At each uncoarsening level, the partition projected from the previous coarser level is improved using a refinement heuristic (Kernighan and Lin 1970; Fiduccia and Mattheyses 1982).

The METIS team in Minnesota have also developed software for partitioning hypergraphs, called hMEHS (Karypis and Kumar 1998b). The algorithms used are similar to those used by PaToH and their main target application is in VLSI circuits.

Vastenhouw and Bisseling (2005) partition matrices using hypergraphs, although their main target is for sparse matrix vector multiplication on parallel

Table 9.10.1 Number of interface variables in the singly bordered block diagonal form generated by HSL_MC66. n is the order of the problem and N is the number of submatrices. The percentages of interface variables are in parentheses.

Identifier

n

N = 2

N = 4

N=8

N

= 16

ethylene-21

10

353

21

(0.20%)

73

(0.71%)

147

(1.42%)

271

(6.79%)

ethylene-11

10

673

42

(0.39%)

118

(1.11%)

181

(1.70%)

276

(6.29%)

Matrix108761

10

876

128

(1.18%)

644

(5.92%)

1123

(10.3%)

2088

(19.2%)

4001s1

11

770

30

(0.25%)

60

(0.51%)

184

(1.56%)

433

(3.68%)

1hr14c

14

270

68

(0.68%)

266

(1.58%)

635

(4.45%)

1262

(8.84%)

bayer04

20

545

185

(0.90%)

453

(2.29%)

599

(2.92%)

886

(7.71%)

10c0ls1

29

496

30

(0.10%)

137

(0.46%)

288

(0.98%)

600

(2.03%)

Matrix324061

32

406

574

(1.77%)

1021

(3.15%)

1387

(4.28%)

2289

(7.06%)

lhr34c

35

152

94

(0.27%)

384

(1.09%)

885

(2.52%)

1766

(5.02%)

Matrix356401

35

640

312

(0.88%)

624

(1.75%)

1464

(4.11%)

2520

(7.07%)

bayer01

57

735

71

(0.12%)

233

(0.46%)

354

(0.61%)

613

(1.06%)

lhr71c

70

304

64

(0.09%)

252

(0.36%)

832

(1.18%)

1834

(2.61%)

icomp1

75

724

186

(0.25%)

250

(0.33%)

449

(0.59%)

719

(0.95%)

1 Not in the Florida sparse matrix collection.

architectures. Their program is based on a recursive bipartitioning algorithm that cuts the matrix horizontally and vertically. Because such a partition resembles the paintings of Mondriaan, this is the name that they use for their program. The algorithms are multilevel algorithms similar to the above-mentioned methods.

 
Source
< Prev   CONTENTS   Source   Next >