REDUCING THE BANDWIDTH OF SPARSE SYMMETRIC MATRICES

E. Cuthill and J. McKee

Naval Ship Research and Development Center
Washington, D. C. 20007

Abstract pAp T

derived from the coefficient matrix A (by corre-

The finite element displacement method of
sponding row and column permutations) will be such
analyzing structures involves the solution of
that the non-zero elements will cluster as much as
large systems of linear algebraic equations with
possible, in.some sense, about the main diagonal.
sparse, structured, symmetric coefficient matrices.
For Jennings 12 storage scheme we would want to
There is a direct correspondence between the
determine P to minimize for PAP T a function of the
structure of the coefficient matrix, called the
form:
stiffness matrix in this case, and the structure
N
of the spatial network delineating the element 1
layout. For the efficient solution of these
~ ei (I)
i=1
systems of equations, it is desirable to have an
automatic nodal numbering (or renumbering) scheme where 8 i is the difference in column indices of the
to ensure that the corresponding coefficient diagonal element for row i and the first non-zero
matrix will have a narrow bandwidth. This is the element for row i, and N is the order of A. For
problem considered by R. Rosen I. A direct method the diagonal band matrix storage scheme, one would
of obtaining such a numbering scheme is presented. want bandwidth minimization, i.e., one would want
In addition several methods are reviewed and to minimize:
compared. max 8 i . (2)
i
I. Introduction
In this paper we address ourselves to the
problem of bandwidth minimization. For some dis-
The finite element displacement method of
cussion of the problem of minimizing (I) see
analyzing structures involves the solution of
Tewarson 9. An iterative program for minimizing (I)
large systems of linear algebraic equations with
is presented by Akyuz and Utku I0.
sparse, structured, symmetric coefficient matrices.
This is also true of many other physical problems For automatic bandwidth minimization, Rosen 1
involving networks explicitly, or into which net- has published a program based on an iterative
works are introduced when approximate solutions method. This method may converge to a local mini-
of field problems are sought. mum as we shall see. Alway and Martin II do an
educated search of permutations to arrive at one
In our discussion we confine ourselves to
which can be used to permute rows and corresponding
systems of equations with sparse, symmetric, posi-
columns of the given matrix to minimize bandwidth.
tive definite coefficient matrices. In order to
This can be very time consuming, especially for
solve such systems of equations efficiently we
large matrices. Our strategy is to look at only a
• must conserve computer storage as well as calcu-
few such permutations suggested by the structure
lation time.
of a graph associated with the coefficient matrix.
Several approaches are available for the These in many cases of interest lead to minimum or
storing of these coefficient matrices; the choice near minimum bandwidth for the permuted matrix.
of scheme being governed by the particular method Our program is significantly faster than the
of solution, whether iterative or direct. others.
Iterative methods as described by Varga 2 can be
The initial purpose of our effort was to arrive
very efficient. For the types of problems
at a permutation to give a matrix with reasonably
considered here the methods described by Carr~ B
narrow bandwidth for use as a starting point so
are especially pertinent. Direct methods based
that iterative methods such as that of reference 1
on Gaussian elimination may be preferable if the
would converge to a numbering scheme giving some-
pattern of non-zero elements in the coefficient
wheres near the minimum bandwidth. HoWever, for
matrix is such that not too many non-zero elements
fairly regular networks such as those arising in
have to be introduced during the elimination.
our structures work, the permutations generated by
Part er 4 , Sato and Tinney 5 , Tewars on 6 , Nathan and
our program have usually been such that Rosen's
Even 7, Steward 8 among others consider strategies
program when applied to the output has given very
that will introduce into the coefficient matrix
little improvement. For sparse, random matrices,
as few non-zero elements as possible during the
we have gotten more significant improvements with
solution of the system of equations. The disad-
Rosen's program.
vantage of these methods is that when automated,
unless the matrix is of rather special form, they
2. Notation and Definitions
tend to involve a considerable amount of "red-
tape programming" along with the calculations.
Before describing our algorithm for determining
Another approach to this problem of taking a permutation matrix which will give a narrow band-
advantage of sparseness, which tends to involve width, we will summarize some of the notation to be
fewer clerical instructions when automated, is to used plus definitions of needed terms from graph
determine a permutation matrix P such that the theory.
symmetric matrix:

157
 The systems of linear algebraic equations b) The nodes adjacent to this node are
being considered are of the form: numbered in sequence beginning with 2 in the order
of their increasing degree. These nodes are at
distance 1 from node 2. They are said to be at
the first level. The 3 nodes of Figures 2A and 2B
where A i~ an N x N sparse symmetric, positive
at distance I from node 2 are labeled 2, 3, and 4.
deflnltematrix. The elements of A will be desig-
nated aij where i is a row index and j a column c) This procedure is repeated for each node
index. We will use the maximum value of li-jl for at the first level in sequence, i.e., first for
non-zero aij as a measure of the bandwidth of A. node 2, then for node 3, etc. Thus, in Figure 2A,
the node adjacent to node 2 which has not already
For the graph G(A) corresponding to the matrix
been numbered will become node 5, adjacent to 3 we
A we will have N nodes labeled i = 1,2,...,N. For
have additional nodes 6, 7, and 8, node 6 having a
each non-zero element ai= , i < j of A there will
lower degree than node 7, which is of lower degree
be an edge connecting no~es i and j. From the
than node 8. Thus, nodes 5, 6, 7, and 8 are at
graph of A we can determine the position of all
the second level. These are the nodes at distance
off-dlagonal non-zero elements of A.
2 from the starting node. They are said to be at
Two nodes of G(A) are said to be adjacent if the second level.
they are connected by an edge. Two nodes of G(A)
d) The above procedure is repeated for the
are said to be connected if there is a sequence of
nodes at each successive level.
edges joining them such that consecutive edges have
a co~m~on end point. A graph is said to be
This procedure will terminate when all the
connected if every pair of nodes of the graph are
nodes of a component have been labeled. If there
connected. If G(A) is connected, the corresponding
is more than one component, the procedure can be
matrix 2 is irreducible. A component of a graph is
continued by selecting the unlabeled node to start
a connected subgraph which is not contained in a
a new component.
larger connected subgraph.
For the two sets of labels developed in Figure
The degree of a node i of G(A) is the number
2 for the same graph, we see that the one in
of edges meeting at i. For the corresponding
Figure 2A leads to a matrix with a bandwidth of 5,
matrix, this is the number of non-zero off-
while that in Figure 2B leads to a matrix with
diagonal elements in row i.
bandwidth 3. Since the nodes of maximum degree
A tree is a graph which has no isolated nodes are I and J which are of degree 6, a lower bound
and which has one more node than the number of for the bandwidth will be 3. This we have
edges. A tree contains no closed loops. achieved. Figure 3 gives an "obvious" type of
numbering scheme that one might guess would result
A spanning tree of G(A) is a subgraph of G(A)
in a minimum bandwidth. It does not.
which is a tree containing all the nodes of G(A).
When one starts with a node of minimum degree,
When we permute the rows and columns of A
our simple numbering scheme described does sur-
using the permutation matrix P ~enerating PAP T,
prisingly well for many occurring patterns which
the graph of PAP T, namely G(PAPI), is structurally
are fairly regular. For a matrix which can be
identical to A but the node labels have been per-
transformed to band diagonal form with no zero
muted according to the permutation matrix P. P
elements in the band, an optimum numbering scheme
has one non-zero unit element in each row and
will automatically result. Some examples are
column; in row i it will be Pij where i is the new
given in Figure 4.
node label and j designates the original one.
Other cases in which our scheme will auto-
3. A Nodal Numberin 8 Scheme matically give either an optimum bandwidth or at
most one greater than the optimum are for an n x m
Given the matrix A, from its graph G(A) as rectangular network as shown in Figure 5A and the
defined above, we can see immediately that a lower corresponding triangular network in Figure 5B.
bound for our measure of the bandwidth of PAP T for The generation of a numbering scheme by our
any permutation matrix P is given by the smallest procedure corresponds to the generation of a
integer greater than or equal to D/2 where D is spanning tree for G(A). See the trees in part d)
the maximum degree of any node of G(A). For the of Figures 2A and 2B indicated by the solid lines.
matrix of Figure IA, a lower bound for the band- Note that a node of minimum or near minimum degree
width of PAP T is thus I, while for those of is chosen as the r o o t of the tree. The nodes
Figures IB and IC it is 2. Note that in Figure IA adjacent to this node are at the next level in the
the nodal numbering pattern is such that this tree. They are at a distance 1 from the root.
lower bound has been achieved. The nodes adjacent to these nodes which have not
The first procedure presented here for yet been labeled become second level nodes. They
determining P or equivalently a renumbering are at a distance 2 from the root, etc. A number-
scheme for G(A) is given below: ing scheme which will minimize the maximum number
of nodes per level of such a spanning tree will in
a) Select a starting node which might be a general be a good one since nodes at any level are
node of minimum degree. Relabel it I. See Figure connected only to those of the same level, the
2. We consider two possibilities, labeling node preceding level, or the following level. Note in
A as I in Figure 2A and labeling node B as 1 in Figure 4A the number of nodes per level are I, 3,
Figure 2B. 4, 2 respectively while in Figure 2B they are i, 3,

158
3, 3 respectively, so that one might expect that tO developing improved strategies for such schemes
the numbering scheme in Figure 2B would be the is in progress. Our present program has an input
better one, which it is. In fact, it is optimum option permitting the specification of one or more
since there is a node of degree 6 and this scheme nodes as starting points for the numbering scheme.
gives a bandwidth of 3. Other improvements to the numbering procedure can
be made when there is some exploration of the
Regardless of the details of the numbering
alternate paths possible under the rules for
scheme, when the maximum number of nodes per level
generating our scheme. See Figure 5, for example.
is known for a spanning tree such as we are
After rooting the spanning tree at node I, nodes
generating, an upper bound for the bandwidth of
2 and 3 can be labeled in one of two ways. Once
PAP T is automatically available. It will be 2N-I,
a decision is made here, there are no further
where N is the maximum number of nodes per level.
alternate paths that our numbering scheme could
The factor of two occurs since at worst the first
take. In this case, one of the two choices leads
node at one level can be connected to the last node
to an optimum numbering scheme.
of the next level. Note that for the trees of
Figures 2A and 2B respectively these are 7 and 5
4. Comparison with Other Methods
which are both conservative.
In addition, the minimum bandwidth that can be Alway and Martin II present a method of surveying
obtained using a numbering scheme based on a those permutations which could lead to bandwidth
particular spanning tree is the maximum number of reduction. Whenever the matrix is such that the
nodes per level. In the numbering schemes of permuted form contains no zero elements within the
Figures 2A and 2B this is 4 and 3, respectively. band, they will find the appropriate permutation
for minimum bandwidth very efficiently. Our scheme
In many cases, starting with a node of lowest
is also especially efficient for such a matrix; in
degree is good strategy, but it is easy to give
fact, as already noted, our numbering scheme,
examples in which this will not lead to an optimum
starting with any node of lowest degree will lead
numbering. Figure 6 contains such an example in
to an optimum in this case. In the form described
which the starting node for an optimum numbering
in reference ii, their algorithm is not usually
scheme is not of lowest degree.
practical for the very large order matrices (of the
Our FORTRAN program includes as parameters two order of i000 to i0,000) for which our program was
integers N and M which are used as follows: If for developed. The amount of calculation time required
any node of G(A) Dmi n is the minimum degree, and goes up too rapidly.
Dma x is the maximum degree, then for each component
Rosen I presents an iteration scheme for "matrix
of G(A) spanning trees are generated starting at
bandwidth minimization". This scheme is based on
each node of degree D such that
a search for interchanges of two rows and the corre-
• ~ D < D + N
sponding columns which will reduce or at worst not
Dmln - min M Dmax (3) increase the bandwidth. One can readily construct
matrices for which such a procedure will give no
This allows one to control the degrees of the set
reduction in bandwidth, but for which a permutation
of nodes tried. Then for each component of G(A),
exists which would give a considerable reduction.
for those starting nodes leading to the minimum
maximum number of nodes per level, relabeling For example, consider a matrix with a graph
schemes are generated following our prescription. represented by a rectangular network numbered in
Again for each component, that leading to a mini- a regular pattern as shown in Figure 8. Figure 8A
mum bandwidth is adopted. A good strategy appears shows a possible numbering scheme for which our
to be to choose M=2, N=I. The program is very fast measure of the corresponding matrix bandwidth is M,
even when the number of nodes is large. The while Figure 8B gives a numbering scheme for the
running time increases nearly linearly with the same network for which our measure of the corre-
product of the number of nodes, the number of nodes sponding matrix bandwidth is N. Since we are
of degree D satisfying¢3)and, the average degree assuming that N > M, the first scheme is better.
per node. For every other program of which we are Suppose we try to interchange two node labels, say
aware the running time increases much faster as the i and j (this is equivalent to permuting
number of nodes increases. corresponding rows and columns of the related
matrix) in the scheme of Figure 8B. Figure 8C
Several byproducts result from the organization
shows the case in which one of them (i) is not
of our computer program. One can readily check
from the top or bottom row of the network; Figure
whether a matrix is reducible or not. If it is
8D shows the case in which they are both in the
reducible, any relabeling scheme generated by our
top row; Figure 8E shows the case in which they
program will lead to a matrix in completely
are both in the bottom row; and Figure 8F shows
reduced f o r ~ As a byproduct of generating a
the case in which one is in the top row and the
spanning tree, we generate the distance of every
other in the bottom row. These are all of the
node from the starting node. When this is done for
possible types of interchanges involving two nodes.
every node of the graph, the maximum distance
In each case, we see that our measure of the band-
encountered is the diameter of the graph.
width of the corresponding matrix will be greater
One should also consider sets of trees rooted than N. Thus Rosen's program will not improve upon
at more than one node. These will often give this numbering, although Figure 8A shows that such
improvements for more complex graph structures, and an improvement is clearly possible.
even some simple ones. See Figure 7. Work related

159
 Versions of Rosen's program I and ours have TABLE 3
been compared on a number of sample problems.
Figures 9 to 12 illustrate the starting numbering Problem No.Nodes (O) (R) (C) (RT) (CT)
schemes used and the renumbering schemes generated
IA iii 36 18 12 5.3 .26
by both Rosen's program and ours for 4 simple
structures. In each case for our scheme we used 2A 82 73 18 9 3.4 .26
as starting node, a node of minimum degree. Table
3A 114 113 20 13 8.9 .38
I summarizes the results obtained for these
problems. Here column (0) contains the original 4A 114 113 26 15 15.1 .40
bandwidth. (R) contains the bandwidth obtained
5A 114 113 29 18 18.9 .53
using Rosen's schame and (C) contains that for our
scheme. In none of these eases would Rosen's
program improve upon the scheme generated by our In none of these cases would Rosen's program
program. imp'rove upon our generated scheme.
Finally, a set of problems was run for which
TABLE i
the positions of off-dlagonal elements of sparse
symmetric matrices were generated using a random
Problem No.Nodes (O) (R) (C)
number generator. The results are summarized in
!. Fig. 9 16 15 3 2 Table 4. The density refers to the ratio of the
number of non-zero elements in the matrix to the
2. Fig. 10 45 36 12 5
total number of elements. To obtain the starred
3. Fig. ii 19 18 4 4 results, the first node encountered of lowest
degree was used to start our numbering scheme.
4. Fig. 12 42 37 9 9
The unstarred ones were obtained using essentially
the strategy used for the problems of Table 2, that
N6dal numbering schemes for a set of five is, the scheme of Section 3 with ~ of Equation 3
larger structural problems were generated by an equal to ½. Again (R) identifies Rosen's scheme,
input processor using a convenient input de- (C) identifies our scheme, but in addition, (CR)
scription, but with no thought of optimal identifies our scheme followed by Rosen's.
numbering for bandwidth minimization. The
structures and their modeling are briefly TABLE 4
described in Table 2.
FINAL
TABLE 2 Order Density No. (O) (R) (C) (CR)
Average I0 .4 6 7 3.8 3.3 3.3
Problem Description desree/node
.5 16 7.9 4.4 4.5 4.4
IA Plate with elliptic 6.
50 .04 4 40.3 3.8 3.3 3.0
hole modeled with
triangular elements 7* 42.9* 3.7* 3.0* 2.6*
2A Spherical sector with 6. .07 2* 44.5* 12.5" 13.5" 12.0"
hole modeled with
.I0 6 47.2 19.3 18.5 17.0
triangular elements
8* 46.8* 18.9" 22.5*
3A Cylinder with hole 4.
modeled with truss .14 5* 46.2* 23.6* 28.2* 22.3*
elements
4A Cylinder with hole 6. In contrast to the results presented earlier
modeled wlth for the more regular networks, the results of these
triangular elements runs show that Rosen's scheme will frequently
improve upon results generated by ours for random
5A Cylinder with hole 8.
matrices, especially as the density of elements
modeled with
increases.
quadrilateral elements
5. References
The strategy used for our numbering scheme
was that described in Section 3 with ~ of Equation i. R. Rosen, '~atrix bandwidth minimization."
3 equal to ½. The results are given in Table 3. Proceedings of 23rd National Conference, ACM,
Here columns (O), (R) and (C) have the same ACM Publication P-68, Brandon/Systems Press,
meaning as before. Columns (RT) and (CT) contain Princeton, N. J. (1968), pp. 585-595.
the running times in seconds taken on an IBM 360/91
2. R. S. Varga, '~atrix Iterative Analysis."
for Rosen's program and for ours, respectively.
Prentice-Hall, Inc., New York (1962).
3. B . A . CarrY, "The partitioning of network
problems for block iteration." Computer
Journal ~, (1966), pp. 84-97.

160
4. S. Patter, "The use of linear graphs in Gauss
elimination." SlAM Review 3, (1961), pp.
119-130.
5. N. Sato and W. F. Tinney, "Techniques for
exploiting the sparsity of the network
admittance matrix." IEEE Transactions on
Power Apparatus and Systems, 82, (1963),
pp. 944-950.
6. R. P. Tewarson, "Solution of a system of
simultaneous linear equations with a sparse
coefficient matrix by elimination methods."
BIT ~, (1967), pp. 226-239.
7. A. Nathan and R. K. Even, "The inversion of
sparse matrices by a strategy derived from
their graphs." Computer Journal 9, (1966),
pp. 190-194.
8. D. V. Steward, "On an approach to techniques
for the analysis of the structure of large
systems of equations." SlAM Review ~, (1962),
pp. 321-342.
9. R. P. Tewarson, "Row-Column permutation of
sparse matrices." Computer Journal i0, (1967),
pp. 300-305.
I0. F. A. Akyuz and S. Utku, "An automatic
relabeling scheme for bandwidth minimization
of stiffness matrices." AIAA Journal, 6,
(1968), pp. 728-730.
II. G. G. Alway and D. W. Martin, "An algorithm
for reducing the bandwidth of a matrix of
symmetrical configuration." Computer Journal
8, (1965), pp. 264-272.
12. A. Jennings, "A compact storage scheme for the
solutionof symmetric linear simultaneous equ-
ations." Computer Journal 9, (1966),pp.281-285
13. F. Harary, '~ graph theor~ic approach to
matrix inversion by partitioning." Numerisehe
Mathematik, ~, (1962), pp. 128-135.

161
 1234

XXO0]I 1 2 5 4
XXXO 2 G (A) :
A = OXXX 3
OOXX 4

Figure 1A

13545

I
XXO 2
A = XXO
OOX
XOX
3
4
5
G(A) : i IZ
Figure 1B

1354567

li.ooo
~ XO0000
OXOXO0
A = OOXOXX G(A): 2 17 4
OXOXO0
OOXOXO
OOXOOX 5

Figure 1C

FIGURE 1: Some Examples of Matrices and Their Graphs

162
 A D F

a) 1 a)

b) 1 3 b) 2

If"" ,..4

c) 1 3 6 c)

d) 1 3 6 d) 2 5 8

ll.',#" I "2, ~10

N I / 2~% !

FIGURE 2A FIGURE 2B

FIGURE 2: Our Nodal Numbering Scheme

1 5 B
\ ,'~ /
//~'. . ///~
E
FIGURE 3

163
 1 2 3 4 5 6 7 8
T
~ X X X O 0 0 0 0 ~ G (PAP) :
X X X X O 0 0 0
X X X X X O 0 0 1 3 5 7
O X X X X X O 0
PA pT = O O X X X X X O
O 0 0 X X X X X
O 0 0 0 X X X X 2 4 6 8
~ O 0 0 0 0 X X X

1 2 3 4 5 6 7 8 9

~XXXX 0000 ~ 1
X X X X X O 0 0 0 2 G (PAP T) :
X X X X X X O 0 0 3
x x x x x x x o o 4 1 3 5 7 9
pAp T = O X X X X X X X O
O O X X X X X X X
O 0 0 X X X X X X 67 L ~ ~ ~ ~ C /
O 0 0 0 X X X X X 8 2 4 6 8
O 0 0 0 0 X X X X 9

FIGURE 4: Matrices in Band Diagonal Form with no Zeros in the Bands

164
 The two p o s s i b l e n u m b e r i n g S g e n e r a t e d
for a 4 X 6 r e c t a n g u l a r network.

3 6" f 11" 15'

~" 5 9 13 1~ 21 s 12 16 19

4~ .....
8 1"2" 16 2C 22 6 17 26 22"
i

Bandwidth: 4 Bandwidth: 5
FIGURE 5A

For the c o r r e s p o n d i n g triangular network:

v}!y '15
Y V/8 j ./'12/"1./s/"19
' / X V y y} / L

7 11 15 ~2 24 10 23 24

Bandwidth: 4 Bandwidth: 5
FIGURE 5B

FIGURE 5: Our N u m b e r i n g Scheme for R e c t a n g u l a r and T r i a n g u l a n

Networks

165
Starting with node of lowest degree:

6 1 5 1 ~ 14
Bandwidth: 5

A better numbering scheme:

1 3 5 7 9 11 13
Bandwidth: 3

Figure 6: Example showing that to get optimum numbering

scheme one should not always start at node of
lowest degree.

166
 Start with one node of lowest degree; all generated
spanning trees given by our scheme have a~ maximum of
9 nodes per level. Minimum bandwidth with such a
numbering scheme i8 9. Numbers in parentheses indicate
distances from node (0).

CO) (1) (2) (3) (4) (1) (0) ~ .(i) jo) (1) J2)

"3 )",~ ,( 2 ) ,,(1 ) ,(2)

.
(3)

(~) . , ( 2 ~ [ ~ ) .(3) .(4) (3) i2) / ' ,(3) I' (4)

) i ,
.(2) L(3} .(4)
(4) /3C ~,(3) , (4) (3) , ~(3) .,(4)
[4) ._(4) ,_,(4)J 4 ~ (4) (4<~(4) f4) .(4~,(4)

Start with five connected nodes of lowest degree;

spanning tree generated by our scheme then has a maximum
of 5 nodes per level. Numbering below then leads to
a bandwidth of 6.

~'o)
•
..(o) _Co)/ .4"0)
,~
J 2 A3
m, J
"9 ~ "
'1) (1) (1) (1) ,8 , ,1 0

(2)
(3) ;p J
16 .]7 j9 •
20
b

i(4/ !4) f4) 4)

(4)~(4) •,23 2 4 ~ 25

Figure 7 : Example showing that one should sometimes start

with several connected nodes of lowest degree.

167
 M+I 2M+I

M+2

M+3,

NM

Figure 8A

1 2 3 4 N
m

N+I N+2 N+.K

N>M~ 2

MN

FIGURE BB

"-N

i " i-~ ;
j/i so that
d+N d max((i+N)-j,j-(i-N))> N

i+N

FIGURE 8C

jc1 i j+l _ i-1 j i÷1 ..

~j so that
(i+N)-j> N
I[ I! I [i ii.
FIGURE 8D

] ] ~j so that

|
d- ~ i i-~ ._~
l LI
g-_ '1 i~1 j

FIGURE 8~

j-1 i •+1

I i,;i ! ii i i > j+N+I

i-j±l > N
so that

-~ i-1 j~i÷l

FIGURE 8F

FIGURE 8 : Interchanging two n o d e labels leads to i n c r e a s e in

bandwidth.

168
Original numbering:

Bandwidth: 15 i . . . . . I
16 15 14 13 12 11 IO -9

Our renumbering: 1 2 4 6 8 10 12 14

Bandwidth: 2
s ~ 7 11 13 15
J16
Rosen's renumbering 1 2 4 6 8 10 13 15
i ~ ~L v ~ A
Bandwidth: 3
i~4 s

Figure 9: P r o b l e m 1. Circle

169
Original numbering: 1~ 2, ~ 4~ 5,, 6 7, 8~. 9

B~ndwidth:36 1
-[
12i 13_ 14
-[
15 i 16
T
17 18 \
Nodes on
these lines
T - should be
identified
_ 29~ _30_ ,~1. 32 33i 34~ 3 ~ 36 with each
] other.
3~ ~_4_41 421 43~ 44
|
45
/
Our renumbering: 1 4 9 14 19 24 29 34 39
~ ~ ~ o ~ ~ • -~

Bandwidth: 5
|
i ....6 _ e _ I ~ _ i ~ 21s 26~ 31. 36_. 41
\
Nodes on
these two
.~,_ 15i__20~,._25~_~_q+.._~s+ 40.4__4 lines should
be identified
with each
other
!
84 13k 181 23, 28~ 33_ 3_8° 4~

4~ 14 I~ 24 29 34 31
/
Rosen's Renumbering: 1~ 2 12 19 23 15 24 34 43

Bandwidth: 12 la 1 2} 30i 32! 25.~ 36. 4 ~ 4

es
8 I I " i - - 44=
~9 31_ 37, 33. 3% 4 !i iid
i identified
~ 61 I with each
5 7 18 22 2 2 1 ~ _ 2 ~ other.

' 4 '

Figure lO:Problem 2. Cylinder

170
Original numbering: 3 5 7 9 11 13 15 17

Bandwidth: 18 [2 "4 -6 -8 1-0 1-2 14 1-6 11

Z9

Our renumbering:

Bandwidth: 4 I 6 10 14 18 16 1~2

1 2

Rosen's Renumbering: S_ .9 IS ,, 17 18 . . . . I / IC

Bandwidth: 4 ! 5 8 12 16 19 15 11

Figure 11. Problem 3. Truss with extras

171
 3~..33 28 24
Original Numbering:

Bandwidth: 37

42 4: 3 2 1

37 9 2

Our Numbering: 16

Bandwidth: 9 42

40 7

84

27

21 T5 1o E ~

37 42
Rosen'8 Numbering: 39 0

Bandwidth: 9

Figure 12: Problem 4. Quarter disc.

172