Hager’s exchange methods for profile reduction
Hager (2002) suggested two exchange methods for improving any given permutation for profile reduction, which he called ‘down’ and ‘up’. His down exchange algorithm involves the successive exchange of rows (k,k + 1), (k +1,k + 2), ..., (l — 1,1) of the permuted matrix and interchanges
corresponding columns. This actually gives us a cyclic permutation in which the original row k moves to row 1 and all the intervening rows move backwards by one place. For a given k, Hager finds the value of 1 that most reduces the profile. He performs a pass over the matrix with k taking the values n — 1, n — 2, ..., 1; he calculates 1 for each k and, if this gives a profile reduction, applies the corresponding permutation.
Hager’s up exchange is similar, with the direction reversed. For a given k, he exchanges rows and columns (k, k — 1), (k — 1, k — 2),..., (1 + 1,1), finding the value of 1 that most reduces the profile. He performs a pass over the matrix with k taking the values 2, 3, . . . , n.
Hager proposes using the down exchange and up exchange schemes in an iterative fashion: the down exchange algorithm is first applied, followed by the up exchange algorithm, followed by the down exchange algorithm, and so on.
Reid and Scott (2002) considered these algorithms and showed that their efficiency could be significantly improved by careful implementation. They found that the profile reductions usually decreased rapidly over successive passes, but small reductions may continue to occur for many passes. Their code, MC67 in HSL, terminates after a chosen number of passes (default 5) or if a pass makes a change less than a chosen amount (default 0). The value 5 was based
Table 8.9.1 Normalized profiles for the original matrix, the Sloan, hybrid,, and hybrid multilevel orderings, and for these followed by 5 applications of the Hager down/up passes (denoted by +Hager).
Identifier |
Original |
Sloan |
Hybrid |
Hybrid multi. |
|||
+Hager |
+Hager |
+Hager |
|||||
bcsstk30 |
543.4 |
543.4 |
534.2 |
272.5 |
272.1 |
273.6 |
273.0 |
copteri |
1 103.3 |
346.2 |
331.3 |
354.7 |
331.5 |
351.6 |
335.5 |
copter2 |
19 541.8 |
685.2 |
650.9 |
590.7 |
562.9 |
698.1 |
654.5 |
finance256 |
6 459.7 |
169.4 |
167.4 |
172.3 |
168.7 |
127.4 |
124.4 |
finan512 |
12 859.2 |
158.2 |
156.9 |
156.8 |
152.1 |
114.0 |
113.2 |
fordi |
1 880.4 |
126.3 |
99.9 |
104.3 |
88.8 |
101.9 |
85.2 |
on numerical experiments and was chosen so that most of the available gain was usually obtained without undue computing overheads. Even with careful implementation, they found the Hager algorithm typically took twice as long to run as the Sloan algorithm.
Reid and Scott (2002) applied their code to the tests used by Kumfert and Pothen (1997), using the Sloan, hybrid, and hybrid multilevel methods (see Sections 8.5 and 8.8) and five representative results from their summary table are reproduced in Table 8.9.1. Normalized profiles, that is, profiles divided by n are shown in the table. For each problem, the least value and any within 1% of it are highlighted in bold and any within 5% are highlighted in italics. It can be seen that the largest reductions in profile arises from the choice of initial ordering; beyond this, the Hager method gives reductions of up to 20%. It seems sensible to use it unless speed is very important, since it can only give an improvement.