¤ ¤ ¦

10. ;

—˜ ˜ ¤ ¤

¦ ¦

11.

12. EndDo

13. EndDo

© ¢ ¤ Q

¢ ¤ Q ¢

¤ ¤ ¤ ¤ ¤

¦

14.

15. EndWhile

§¨¦©

¥£¡

The array obtained from the procedure lists the nodes in the order in which

they are visited and can, in a practical implementation, be used to store the level sets in

¨¦©

§¥£¡

succession. A pointer is needed to indicate where each set starts. The array thus

constructed does in fact represent the permutation array de¬ned earlier.

In 1971, George [103] observed that reversing the Cuthill-McKee ordering yields a

better scheme for sparse Gaussian elimination. The simplest way to understand this is to

look at the two graphs produced by these orderings. The results of the standard and reversed

Cuthill-McKee orderings on the sample ¬nite element mesh problem seen earlier are shown

0

in Figures 3.6 and 3.7, when the initial node is (relative to the labeling of the original

ordering of Figure 2.10). The case of the ¬gure, corresponds to a variant of CMK in which

the traversals in Line 6, is done in a random order instead of according to the degree. A

large part of the structure of the two matrices consists of little “arrow” submatrices, similar

to the ones seen in Example 3.3. In the case of the regular CMK ordering, these arrows

point upward, as in Figure 3.4, a consequence of the level set labeling. These blocks are

similar the star matrices of Figure 3.4. As a result, Gaussian elimination will essentially

¬ll in the square blocks which they span. As was indicated in Example 3.3, a remedy is

to reorder the nodes backward, as is done globally in the reverse Cuthill-McKee strategy.

For the reverse CMK ordering, the arrows are pointing downward, as in Figure 3.5, and

Gaussian elimination yields much less ¬ll-in.

ud

¡ ¤§ ¥ §¢

¡

¡© © ¢ ¡ ¥ ¥ © ¡ ¥

§

15

13 12

9

14 10

11 6 4

7 2 1

5 3

8

T © ¥ ¡¢ D

Cuthill-McKee ordering.

1

3 4

6 7

2

5 10 12

9 15

14

13

11

8

© ¥ ¡¢ D ¡T Reverse Cuthill-McKee ordering.

d nd¡ £ ¨¡ d¥ $ ¥ £ ”¤§¤

u © n ¥ u§¥ ¡

¤ §¥ ¡ ©

¨

¤©

¡ ¥ ¡

¥ T © ©¨¦

§¥

The choice of the initial node in the CMK and RCMK orderings may be

important. Referring to the original ordering of Figure 2.10, the previous illustration used

0 . However, it is clearly a poor choice if matrices with small bandwidth or pro¬le are

0

desired. If is selected instead, then the reverse Cuthill-McKee algorithm produces

the matrix in Figure 3.8, which is more suitable for banded or skyline solvers.

1