An Analysis of Spectral Envelope Reduction via Quadratic Assignment Problems.
A new spectral algorithm for reordering a sparse symmetric matrix to reduce its envelope size was described in [Barnard, Pothen, and Simon, Numer. Linear Algebra Appl., 2 (1995), pp. 317--334]. The ordering is computed by associating  a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. In this paper we provide an analysis of the spectral envelope reduction algorithm. We describe related 1- and 2-sum problems; the former is related to the envelope size, while the latter is related to an upper bound on the work in an envelope Cholesky factorization. We formulate these two problems as quadratic assignment problems and then study the 2-sum problem in more detail. We obtain lower bounds on the 2-sum by considering a relaxation of the problem and then show that the spectral ordering finds a permutation matrix closest to an orthogonal matrix attaining the lower bound. This provides a stronger justification of the spectral envelope reduction algorithm than previously known. The lower bound on the 2-sum is seen to be tight for reasonably "uniform" finite element meshes. We show that problems with bounded separator sizes also have bounded envelope parameters.
Introduction
. We provide a raison d'-etre for a novel spectral algorithm to reduce
the envelope of a sparse, symmetric matrix, described in a companion paper [2]. The algorithm
associates a discrete Laplacian matrix with the given symmetric matrix, and then
computes a reordering of the matrix by sorting the components of an eigenvector corresponding
to the smallest nonzero Laplacian eigenvalue. The results in [2] show that the spectral
algorithm can obtain significantly smaller envelope sizes compared to other currently used
algorithms. All previous envelope-reduction algorithms (known to us), such as the reverse
Cuthill-McKee (RCM) algorithm and variants [3, 16, 17, 26, 37], are combinatorial in nature,
employing breadth-first-search to compute the ordering. In contrast, the spectral algorithm
is an algebraic algorithm whose good envelope-reduction properties are somewhat intriguing
and poorly understood.
We describe problems related to envelope-reduction called the 1- and 2-sum problems,
and then formulate these latter problems as quadratic assignment problems (QAPs). We
show that the QAP formulation of the 2-sum enables us to obtain lower bounds on the 2-sum
(and related envelope parameters) based on the Laplacian eigenvalues. The lower bounds
seem to be quite tight for finite element problems when the mesh points are nearly all of the
same degree, and the geometries are simple. Further, a closest permutation matrix to an
orthogonal matrix that attains the lower bound is obtained, to within a linear approxima-
tion, by sorting the second Laplacian eigenvector components in monotonically increasing or
decreasing order. This justifies the spectral envelope-reducing algorithm more strongly than
earlier results.
Although initially envelope-reducing orderings were developed for use in envelope schemes
for sparse matrix factorization, these orderings have been used in the past few years in several
other applications. The RCM ordering has been found to be an effective pre-ordering
in computing incomplete factorization preconditioners for preconditioned conjugate-gradient
methods [4, 6]. Envelope-reducing orderings have been used in frontal methods for sparse
matrix factorization [7].
The wider applicability of envelope-reducing orderings prompts us to take a fresh look
at the reordering algorithms currently available, and to develop new ordering algorithms.
Spectral envelope-reduction algorithms seem to be attractive in this context, since they
(i) compare favorably with existing algorithms in terms of the quality of the orderings [2],
(ii) extend easily to problems with weights, e.g., finite element meshes arising from discretizations
of anisotropic problems, and
(iii) are fairly easily parallelizable.
Spectral algorithms are more expensive than the other algorithms currently available. But
since the envelope-reduction problem requires only one eigenvector computation (to low pre-
cision), we believe the costs are not impractically high in computation-intensive applications,
e.g., frontal methods for factorization. In contexts where many problems having the same
structure must be solved, a substantial investment in finding a good ordering might be justi-
fied, since the cost can be amortized over many solutions. Improved algorithms that reduce
the costs are being designed as well [25].
We focus primarily on the class of finite element meshes arising from discretizations of
partial differential equations. Our goals in this project are to develop efficient software implementing
our algorithms, and to prove results about the quality of the orderings generated.
The projection approach for obtaining lower bounds of a QAP is due to Hadley, Rendl,
and Wolkowicz [19], and this approach has been applied to the graph partitioning problem
by the latter two authors [35]. In earlier work a spectral approach for the graph (matrix)
partitioning problem has been employed to compute a spectral nested dissection ordering
for sparse matrix factorization, for partitioning computations on finite element meshes on a
distributed-memory multiprocessor [21, 33, 34, 36], and for load-balancing parallel computations
[22]. The spectral approach has also been used to find a pseudo-peripheral node [18].
Juvan and Mohar [23, 24] have provided a theoretical study of the spectral algorithm for
reducing p-sums, where et al. [20] obtain spectral lower
bounds on the bandwidth. A survey of some of these earlier results may be found in [31].
Paulino et al. [32] have also considered the use of spectral envelope-reduction for finite element
problems.
The following is an outline of the rest of this paper. In Section 2 we describe various
parameters of a matrix associated with its envelope, introduce the envelope size and envelope
work minimization problems, and the related 1- and 2-sum problems. We prove that bounds
on the minimum 1-sum yield bounds on the minimum envelope size, and similarly, bounds
on the minimum 2-sum yield bounds on the work in an envelope Cholesky factorization.
We also show in this section that minimizing the 2-sum is NP-complete. We compute lower
bounds for the envelope parameters of a sparse symmetric matrix in terms of the eigenvalues
of the Laplacian matrix in Section 3. The popular RCM ordering is obtained by reversing
the Cuthill-McKee (CM) ordering; the RCM ordering can never have a larger envelope size
and work than the CM ordering, and is usually significantly better. We prove that reversing
an ordering can improve or impair the envelope size by at most a factor \Delta, and the envelope
work by at most \Delta 2 , where \Delta is the maximum degree of a vertex in the adjacency graph.
In Section 4, we formulate the 2- and 1-sum problems as quadratic assignment problems.
We obtain lower and upper bounds for the 2-sum problem in terms of the eigenvalues of the
Laplacian matrix in Section 5 by means of a projection approach that relaxes a permutation
matrix to an orthogonal matrix with row and column sums equal to one. We justify the
spectral envelope-reduction algorithm in Section 6 by proving that a closest permutation
matrix to an orthogonal matrix attaining the lower bound for the 2-sum is obtained, to
within a linear approximation of the problem, by permuting the second Laplacian eigenvector
in monotonically increasing or decreasing order. In Section 7 we show that graphs with
small separators have small envelope parameters as well, by considering a modified nested
dissection ordering. We present computational results in Section 8 to illustrate that the
2-sums obtained by the spectral reordering algorithm can be close to optimal for many finite
element meshes. Section 9 contains our concluding remarks. The Appendix contains some
lower bounds for the more general p-sum problem, where 1
2. A menagerie of envelope problems.
2.1. The envelope of a matrix. Let A be an n \Theta n symmetric matrix with elements
whose diagonal elements are nonzero. Various parameters of the matrix A associated
with its envelope are defined below.
We denote the column indices of the nonzeros in the lower triangular part of the ith row
by
For the ith row of A we define
Here is the column index of the first nonzero in the ith row of A (by our assumption
of nonzero diagonals, 1 - f i - i), and the parameter r i (A) is the row-width of the ith row
of A. The bandwidth of A is the maximum row-width
The envelope of A is the set of index pairs
For each row, the column indices lie in an interval beginning with the column index of the
first nonzero element and ending with (but not including) the index of the diagonal nonzero
element.
We denote the size of the envelope by
(which includes the diagonal elements) is called the profile of A [7].) The work in the
Cholesky factorization of A that employs an envelope storage scheme is bounded from above
by
This bound is tight [29] when an ordering satisfies (1) f
between 1 and n, and
A 3 \Theta 3 7-point grid and the nonzero structure of the corresponding matrix A are shown
in

Figure

2.1. A ' ffl ' indicates a nonzero element, and a ` \Lambda ' indicates a zero element
that belongs to the lower triangle of the envelope in the matrix. The row-widths given in

Table

2.1 are easily verified from the structure of the matrix. The envelope size is obtained
by summing the row-widths, and is equal to 24. (Column-widths c i are defined later in this
section.)
The values of these parameters strongly depend on the choice of an ordering of the rows
and columns. Hence we consider how these parameters vary over symmetric permutations
of a matrix A, where P is a permutation matrix. We define Esize min (A), the minimum
envelope size of A, to be the minimum envelope size among all permutations P T AP of A.
The quantities Wbound min (A) and bw min (A) are defined in similar fashion. Minimizing the
envelope size and the bandwidth of a matrix are NP-complete problems [28], and minimizing

Fig. 2.1. An ordering of 7-point grid and the corresponding matrix. The lower triangle of the envelope
is indicated by marking zeros within it by asterisks.

Table
Row-widths and column-widths of the matrix in Figure 1.
the work bound is likely to be intractable as well. So one has to settle for heuristic orderings
to reduce these quantities.
It is helpful to consider a "column-oriented" expression for the envelope size for obtaining
a lower bound on this quantity in Section 3. The width of a column j of A is the number of
row indices in the jth column of the envelope of A. In other words,
(This is also called the jth front-width.) It is then easily seen that the envelope size is
The work in an envelope factorization scheme is given by
where we have ignored the linear term in c j . The column-widths of the matrix in Figure 2.1
are given in Table 2.1. These concepts and their inter-relationships are described by Liu and
Sherman [29], and are also discussed in the books [5, 15].
The envelope parameters can also be defined with respect to the adjacency graph
(V; E) of A. Denote In terms of the graph G and an ordering ff of
its vertices, we can define
Hence we can write the envelope size and work associated with an ordering ff as
Esize(G;
Wbound(G;
The goal is to choose a vertex ordering ng to minimize one of the parameters
described above. We denote by Esize min (G) (Wbound min (G)) the minimum value of
Esize(G; ff) (Wbound(G; ff)) over all orderings ff. The reader can compute the envelope size
of the numbered graph in Figure 2.1, using the definition given in this paragraph, to verify
that
The jth front-width has an especially nice interpretation if we consider the adjacency
graph E) of A. Let the vertex corresponding to a column j of A be numbered v j so
that g. Denote
a subset of vertices X. Then c
To illustrate the dependence of the envelope size on the ordering, we include in Figure 2.2
an ordering that leads to a smaller envelope size for the 7-point grid. Again, a ' ffl ' indicates
a nonzero element, and a '   ' indicates a zero element that belongs to the lower triangle of
the envelope in the matrix. This ordering by 'diagonals' yields the optimal envelope size for
the 7-point grid [27].
2.2. 1- and 2-sum problems. It will be helpful to consider quantities related to the
envelope size and envelope work, the 1-sum and the 2-sum.
For real 1 we define the p-sum to be
Minimizing the 1-sum is the optimal linear arrangement problem, and the limiting
case corresponds to the minimum bandwidth problem; both these are well-known
NP-complete problems [13]. We show in the Section 2.3 that minimizing the 2-sum is NP-complete
as well.
We write the envelope size and 1-sum, and the envelope work and the 2-sum, in a way
that shows their relationships:

Fig. 2.2. Another ordering of a 7-point grid and the corresponding matrix. Again the lower triangle of
the envelope is indicated by marking the zeros within it by asterisks.
The parameters oe
are the minimum values of these parameters over
all symmetric permutations P T AP of A.
We now consider the relationships between bounds on the envelope size and the 1-sum,
and between the upper bound on the envelope work and the 2-sum. Let \Delta denote the
maximum number of offdiagonal nonzeros in a row of A. (This is the maximum vertex
degree in the adjacency graph of A.)
Theorem 2.1. The minimum values of the envelope size, envelope work in the Cholesky
factorization, 1-sum, and 2-sum of a symmetric matrix A are related by the following inequalities

\DeltaEsize min (A);
Proof. We begin by proving (2.8). Our strategy will be to first prove the inequalities
and then to obtain the required result by considering two different permutations of A.
The bound Wbound(A) - oe 2
is immediate from equations (2.5) and (2.6). If the
inner sum in the latter equation is bounded from above by
then we get \DeltaWbound(A) as an upper bound on the 2-sum.
Now let X 1 be a permutation matrix such that f
Wbound min (A). Then we have
Further, let X 2 be a permutation matrix such that f
Again, we have
We obtain the result by putting the last two inequalities together.
We omit the proof of (2.7) since it can be obtained by a similar argument, and proceed
to prove (2.9). The first inequality oe holds since the p-norm of any real vector
is a decreasing function of p. The second inequality is also standard, since it bounds the
1-norm of a vector by means of its 2-norm. This result was obtained earlier by Juvan and
Mohar [24]; we include its proof for completeness. Applying the Cauchy-Schwarz inequality
to oe 2
We obtain the result by considering two orderings that achieve the minimum 1- and 2-sums.2.3. Complexity of the 2-sum problem. We proceed to show that minimizing the
2-sum is NP-complete. In Section 8 we show that the spectral algorithm computes a 2-sum
within a factor of two for the finite element problems in our test collection. This proof shows
that despite the near-optimal solutions obtained by the spectral algorithm on this test set,
it is unlikely that a polynomial time algorithm can be designed for computing the minimum
2-sum.
Readers who are willing to accept the complexity of this problem without proof should
skip this section; we recommend that everyone do so on a first reading.
Given a graph E) on n vertices, MINTWOSUM is the problem of deciding if
there exists a numbering of its vertices ng such that
k, for a given positive integer k. This is the decision version of the problem of minimizing
the 2-sum of G.
Theorem 2.2. MINTWOSUM is NP-complete.
Remark. This proof follows the framework for the NP-completeness of the 1-sum problem
in Even [8] (Section 10.7); but the details are substantially different.
Proof. The theorem will follow if we show that MAXTWOSUM, the problem of deciding
whether a graph G 0 on n vertices has a vertex numbering with 2-sum greater than or equal to
a given positive integer k 0 , is NP-complete. For, the 2-sum of G 0 under some ordering is at
least k 0 if and only if the 2-sum of the complement of G 0 under the same ordering is at most
is the 2-sum of the complete
graph.
We show that MAXTWOSUM is NP-complete by a reduction from MAXCUT, the
problem of deciding whether a given graph E) has a partition of its vertices into
two sets fS; V n Sg such that jffi(S; V n S)j, the number of edges joining S and V n S, is
at least a given positive integer k. From the graph G we construct a graph G
E) by adding n 4 isolated vertices to V and no edges to E. We claim
that G has a cut of size at least k if and only if G 0 has a 2-sum at least k
If G has a cut (S; V n S) of size at least k, define an ordering ff 0 of G 0 by interposing
the n 4 isolated vertices between S and V n S: number the vertices in S first, the isolated
vertices next, and the vertices in V n S last, where the ordering among the vertices in each
set S and V n S is arbitrary. Every edge belonging to the cut contributes at least n 8 to the
2-sum, and hence its value is at least k \Delta n 8 .
The converse is a little more involved.
Suppose that G 0 has an ordering ff with 2-sum greater than
or equal to k \Delta n 8 . The ordering ff 0 of G 0 induces a natural ordering ng of G,
if we ignore the isolated vertices and maintain the relative ordering of the vertices in V . For
each ig. Then each pair (S
a cut in G. Further, each such cut in G induces a cut (S 0
in the larger graph G 0 as
follows: The vertex set S 0
i is formed by augmenting S i with the isolated vertices numbered
lower than the highest numbered (non-isolated) vertex in S i (with respect to the ordering
We now choose a cut (S maximizes the "1-sum over the cut edges"
from among the n cuts (S 0
By means of this cut and the ordering ff 0 , we define a
new ordering fi 0 by moving the isolated vertices in the ordered set S 0 to the highest numbers
in that set, and by moving the isolated vertices in V 0 n S 0 to the lowest numbers in that
set, and preserving the relative ordering of the other vertices. The effect is to interpose the
isolated vertices in "between" the two sets of the cut.
Claim. The 2-sum of the graph G 0 under the ordering fi 0 is greater than that under ff 0 .
To prove the claim, we examine what happens when an isolated vertex x belonging to
S 0 is moved to the higher end of that ordered set.
Define three sets A 0 , B 0 , C 0 as follows: The set A 0 (B 0 ) is the set of vertices in S 0
numbered lower (higher) than x in the ordering ff 0 , and C
the edges joining A 0 and those joining
A 0 and C 0 .
Denote the contribution, with respect to the ordering ff 0 , of an edge e k to the 1-sum
by a k , and that of an edge e l l . Then the change in the 2-sum due to moving x is
(b l
The third term on the right-hand-side is the contribution to the 1-sum made by the edges
in the cut while the fourth term is the contribution made by
the edges E 1 in the cut By the choice of the cut (S that the
difference is positive, and hence that the 2-sum has increased in the new ordering obtained
from ff 0 by moving the vertex x.
We now show that after moving the vertex x, continues to be a cut that
maximizes the 1-sum over the cut edges among all cuts (S 0
respect to the new
ordering. For this cut, the 1-sum over cut edges has increased by jE 2 j because the number of
each vertex in B has decreased by one in the new ordering. Among cuts with one set equal
to an ordered subset of A 0 , the 1-sum over cut edges can only decrease when x is moved,
since the set B 0 moves closer to A 0 , and C 0 does not move at all relative to A 0 . Now consider
cuts of the form
1 an ordered subset of B 0 , and B 0
. The
cut edges now join A 0 to B 0
. The edges joining A 0 to B 0
contribute a
smaller value to the 1-sum in the new ordering relative to ff 0 , while the edges joining A 0 to C 0
contribute the same to the 1-sum in both cuts A
under the
new ordering. The edges joining B 0
2 do not change their contribution to the 1-sum in
the new ordering. The edges that join B 0
1 and C 0 form a subset of the edges that join B 0 and
hence the contribution of the former to the 1-sum is no larger than the contribution
of the latter set in the new ordering. This shows that the cut continues to
have a 1-sum over the cut edges larger than or equal to that of any cut
Finally, any cut that includes A 0 , B 0 , and an ordered subset C 0
1 of C 0 can be shown by similar
reasoning to not have a larger 1-sum than (S
The reasoning in the previous paragraph permits us to move the isolated vertices in S 0
one by one to the higher end of that set without decreasing the 2-sum while simultaneously
preserving the condition that the cut (S has the maximum value of the 1-sum over
the cut edges. The argument that we can move the isolated vertices in V 0 nS 0 to the beginning
of that ordered set follows from symmetry since both the 2-sum and the 1-sum are unchanged
when we reverse an ordering. Hence by inducting over the number of isolated vertices moved,
the ordering fi 0 has a 2-sum at least as large as the ordering ff 0 . This completes the proof of
the claim.
The rest of the proof involves computing an upper bound on the 2-sum of the graph G 0
under the ordering fi 0 to show that since G 0 has 2-sum greater than k 0 , the graph G has a
cut of size at least k.
)j. The cut edges contribute at most ffi \Delta (n 4 to the upper
bound on the 2-sum; the uncut edges contribute at most the 2-sum of a complete graph on
vertices. The latter is p(n) Thus we have, keeping only leading terms,
The second term on the left hand side is less than 1 for n ? 2 since the number of cut edges
ffi is at most n 2 =2; the third term is less than one for all n. The sum of these two terms is
less than 1 for n ? 2. Hence we conclude that the graph G has a cut with at least k edges.
This completes the proof of the theorem. 2
3. Bounds for envelope size. In this section we present lower bounds for the minimum
envelope size and the minimum work involved in an envelope-Cholesky factorization in
terms of the second Laplacian eigenvalue. We will require some background on the Laplacian
matrix.
3.1. The Laplacian matrix. The Laplacian matrix Q(G) of a graph G is the n \Theta n
is the diagonal degree matrix and M is the adjacency matrix of G.
If G is the adjacency graph of a symmetric matrix A, then we could define the Laplacian
matrix Q directly from A:
Note that
The eigenvalues of Q(G) are the Laplacian eigenvalues of G, and we list them as - 1
corresponding to - k (Q) will be denoted by x k , and will
be called a kth eigenvector of Q. It is well-known that Q is a singular M-matrix, and hence
its eigenvalues are nonnegative. Thus - 1 0, and the corresponding eigenvector is any
nonzero constant vector c. If G is connected, then Q is irreducible, and then -
smallest nonzero eigenvalues and the corresponding eigenvectors have important properties
that make them useful in the solution of various partitioning and ordering problems. These
properties were first investigated by Fiedler [9, 10]; as discussed in Section 1, more recently
several authors have studied their application to such problems.
3.2. Laplacian bounds for envelope parameters. It will be helpful to work with
the "column-oriented" definition of the envelope size. Let the vertex corresponding to a
column j of A be numbered v j in the adjacency graph so that
g. Recall that the column width of a vertex v j is c and that the
envelope size of G (or A) is
Recall also that \Delta denotes the maximum degree of a vertex. Given a set of vertices S, we
denote by ffi(S) the set of edges with one endpoint in S and the other in V n S.
We make use of the following elementary result, where the lower bound is due to Alon
and Milman [1] and the upper bound is due to Juvan and Mohar [24].
Lemma 3.1. Let S ae V be a subset of the vertices of a graph G. Then
Theorem 3.2. The envelope size of a symmetric matrix A can be bounded in terms of
the eigenvalues of the associated Laplacian matrix as
Proof. From Lemma 3.1,
Now substituting the lower bound for jffi(V j )j, and summing
this latter expression over all j, we obtain the lower bound on the envelope size.
The upper bound is obtained by using the inequality c with the upper
bound in Lemma 3.1. 2
A lower bound on the work in an envelope-Cholesky factorization can be obtained from
the lower bound on the envelope size.
Theorem 3.3. A lower bound on the work in the envelope-Cholesky factorization of a
symmetric positive definite matrix A is
Proof. The proof follows from Equations 2.1 and 2.2, by an application of the Cauchy-Schwarz
inequality. We omit the details. 2
Cuthill and McKee [3] proposed one of the earliest ordering algorithms for reducing the
envelope size of a sparse matrix. George [14] discovered that reversing this ordering leads to a
significant reduction in envelope size and work. The envelope parameters obtained from the
(RCM) ordering are never larger than those obtained from CM [29].
The RCM ordering has become one of the most popular envelope size reducing orderings.
However, we do not know of any published quantitative results on the improvement that may
be expected by reversing an ordering, and here we present the first such result. For degree-bounded
finite element meshes, no asymptotic improvement is possible; the parameters are
improved only by a constant factor. Of course, in practice, a reduction by a constant factor
could be quite significant.
Theorem 3.4. Reversing the ordering of a sparse symmetric matrix A can change
(improve or impair) the envelope size by at most a factor \Delta, and the envelope work by at
most
Proof. Let v j denote the vertex in the adjacency graph corresponding to the jth column
of A (in the original ordering) so that the jth column width c
g. Let e
A denote the permuted matrix obtained by reversing the column and row
ordering of A. We have the inequality
(A), summing this inequality over j from one to n, we obtain
A). By symmetry, the inequality Esize( e
holds as well.
The inequality on the envelope work follows by a similar argument from the equation
4. Quadratic assignment formulation of 2- and 1-sum problems. We formulate
the 2- and 1-sum problems as quadratic assignment problems in this section.
4.1. The 2-sum problem. Let the vector
, and let ff be a
permutation vector, i.e., a vector whose components form a permutation of
may permutation matrix with elements
It is easily verified that the (ff(i); ff(j)) element of the permuted matrix X T AX is the element
a ij of the unpermuted matrix A. Let ij. We denote the set of all
permutation vectors with n components by S n .
We write the 2-sum as a quadratic form involving the Laplacian matrix Q.
a
The transformation from the second to the third line makes use of (3.1).
This quadratic form can be expressed as a quadratic assignment problem by substituting
min
There is also a trace formulation of the QAP in which the variables are the elements of
the permutation matrix X. We obtain this formulation by substituting Xp for ff. Thus
min
We may consider the last scalar expression as the trace of a 1 \Theta 1 matrix, and then use the
identity tr tr NM to rewrite the right-hand-side of the last displayed equation as
tr
tr
This is a quadratic assignment problem since it is a quadratic in the unknowns x ij , which
are the elements of the permutation matrix X. The fact that B is a rank-one matrix leads
to great simplifications and savings in the computation of good lower bounds for the 2-sum
problem.
4.2. The 1-sum problem. Let M be the adjacency matrix of a given symmetric
matrix A and let S denote a 'distance matrix' with elements both of order n.
Then
oe
Unlike the 2-sum, the matrices involved in the QAP formulation of the 1-sum are both
of rank n. Hence the bounds we obtain for this problem by this approach are considerably
more involved, and will not be considered here.
5. Eigenvalue bounds for the 2-sum problem.
5.1. Orthogonal bounds. A technique for obtaining lower (upper) bounds for the
QAP
min
permutation matrix;
is to relax the requirement that the minimum (maximum) be attained over the class of
permutation matrices. Let
n)
denote the normalized n-vector of
all ones. A matrix X of order n is a permutation matrix if and only if it satisfies the following
three constraints:
(5.
The first of these, the stochasticity constraint , expresses the fact that each row sum or
column sum of a permutation matrix is one; the second states that a permutation matrix
is orthogonal; and the third that its elements are non-negative. The simplest bounds for a
QAP are obtained when we relax both the stochasticity and non-negativity constraints, and
insist only that X be orthonormal. The following result is from [11]; see also [12].
Theorem 5.1. Let the eigenvalues of a matrix be ordered
Then, as X varies over the set of orthogonal matrices, the following upper and lower bounds
hold:
The Laplacian matrix Q has - 1
1). Hence the lower bound in the theorem above is zero,
and the upper bound is (1=6)- n (Q)n(n
5.2. Projection bounds. Stronger bounds can be obtained by a projection technique
described by Hadley, Rendl, and Wolkowicz [19]. The idea here is to satisfy the stochasticity
constraints in addition to the orthonormality constraints, and relax only the non-negativity
constraints. This technique involves projecting a permutation matrix X into a subspace
orthogonal to the stochasticity constraints (5.1) by means of an eigenprojection.
Let the n \Theta be an orthonormal basis for the orthogonal complement
of u. By the choice of V , it satisfies two properties: V T
is an
orthonormal matrix of order n.
Observe that
This suggests that we take
Note that with this choice, the stochasticity constraints are satisfied.
Furthermore, if X is an orthonormal matrix of order n satisfying
is orthonormal, and this implies that Y is an orthonormal matrix of order n \Gamma 1. Conversely,
if Y is orthonormal of order then the matrix X obtained by the construction above
is orthonormal of order n. The non-negativity constraint X - 0 becomes, from (5.4),
These facts will enable us to express the original QAP in terms of a
projected QAP in the matrix of variables Y .
To obtain the projected QAP, we substitute the representation of X from (5.4) into the
objective function tr QXBX T . Since by the construction of the Laplacian, terms of
the form Qu
tr
where we use the identity tr for an n \Theta k matrix M and a k \Theta n matrix
N . Again this term is zero since u T Hence the only nonzero term in the objective
function is
tr
where c
is a projection of a matrix M .
We have obtained the projected QAP in terms of the matrix Y of order
the constraint that X be a permutation matrix now imposes the constraints that Y is orthonormal
and that V Y V T - \Gammau u T . We obtain lower and upper bounds in terms of the
eigenvalues of the matrices b
by relaxing the non-negativity constraint again.
Theorem 5.2. The following upper and lower bounds hold for the 2-sum problem:
Proof. If we apply the orthogonal bounds to the projected QAP, we get
The vector u is the eigenvector of Q corresponding to the zero eigenvalue, and hence eigen-vectors
corresponding to higher Laplacian eigenvalues are orthogonal to it. Thus any such
eigenvector x j can be expressed as x . Substituting this last equation into the eigenvalue
equation pre-multiplying by V T , we obtain b
Hence
Q). Also, -
are zero. Hence it remains to compute the largest eigenvalue of b
B.
From the representation I
We get the result by substituting these eigenvalues into the bounds for the 2-sum. 2
For justifying the spectral algorithm for minimizing the 2-sum, we observe that the lower
bound is attained by the matrix
where R (S) is a matrix of eigenvectors of b
B), and the eigenvectors correspond to the
eigenvalues of b
B) in non-decreasing (non-increasing) order.
The result given above has been obtained by Juvan and Mohar [24] without using a QAP
formulation of the 2-sum. We have included this proof for two reasons: First, in the next
subsection, we show how the lower bound may be strengthened by diagonal perturbations
of the Laplacian. Second, in the following section, we consider the problem of finding a
permutation matrix closest to the orthogonal matrix attaining the lower bound.
5.3. Diagonal perturbations. The lower bound for the 2-sum can be further improved
by perturbing the Laplacian matrix Q by a diagonal matrix Diag(d), where d is an
n-vector, and then using an optimization routine to maximize the smallest eigenvalue of the
perturbed matrix.
Choosing the elements of d such that its elements sum to zero, i.e., u T simplifies
the bounds we obtain, and hence we make this assumption in this subsection. We begin by
denoting expressing
The second term can be written as a linear assignment problem (LAP) since one of the
matrices involved is diagonal. Let the permutation vector denote the
n-vector formed from the diagonal elements of B.
tr
We now proceed, as in the previous subsection, to obtain projected bounds for the
quadratic term, and thus for f(X). Note that
n )d since
since the elements of d sum to zero. We let
the row-sum of the elements of B.
With notation as in the previous subsection, we substitute in the
quadratic term in f(X). The first term tr Q(d)u u T Bu u
second and third terms are equal, and their sum can be transformed as follows:
Note that this term is linear in the projected variables Y , and we shall find it convenient to
express it in terms of X by the substitution X
since the second term is equal to tr u T d r(B) T u, which is zero by the choice of d.
Finally, the fourth term becomes tr b
and as before
Putting it all together, we obtain
Observe that the first term is quadratic in the projected variables Y , and the remaining terms
are linear in the original variables X. Our lower bound for the 2-sum shall be obtained by
minimizing the quadratic and linear terms separately.
We can simplify the linear assignment problem by noting that
sq(p), the vector
with ith component equal to i 2 . Hence the final expression for the linear assignment problem
is
tr d
The minimum value of this problem, denoted by L(d) (the minimum over the permutation
matrices X, for a given d), can be computed by sorting the components of d and
The eigenvalues of b
B can be computed as in the previous subsection. We may choose d
to maximize the lower bound. Thus this discussion leads to the following result.
Theorem 5.3. The minimum 2-sum of a symmetric matrix A can be bounded as
d
where the components of the vector d sum to zero. 2
6. Computing an approximate solution from the lower bound. Consider the
problem of finding a permutation matrix Z "closest" to an orthogonal matrix X 0 that attains
the lower bound in Theorem 5.2. We show in this section that sorting the second Laplacian
eigenvector components in non-increasing (also non-decreasing) order yields a permutation
matrix that solves a linear approximation to the problem. This justifies the spectral approach
for minimizing the 2-sum.
From (5.5), the orthogonal matrix X a matrix of
eigenvectors of b
B) corresponding to the eigenvalues of b
B) in increasing (decreasing)
order. We begin with a preliminary discussion of some properties of the matrix X 0 and the
eigenvectors of Q. For let the jth column of R be denoted by r j , and
similarly let s j denote the jth column of S. Then s c is a normalization
the vector s j is orthogonal to V T p, i.e.,
Recall from the previous section that a second Laplacian eigenvector x
Now we can formulate the "closest" permutation matrix problem more precisely. The
minimum 2-sum problem may be written as
min
Z
2:
We have chosen a positive shift ff to make the shifted matrix positive definite and hence
to obtain a weighted norm by making the square root nonsingular. It can be verified that
the shift has no effect on the minimizer since it adds only a constant term to the objective
function.
We substitute expand the 2-sum about X 0 to obtain
2:
The first term on the right-hand-side is a constant since X 0 is a given orthogonal matrix;
the third term is a quadratic in the difference hence we neglect it to obtain a
linear approximation. It follows that we can choose a permutation matrix Z close to X 0 to
approximately minimize the 2-sum by solving
min
Z
Z
Substituting for X 0 from (5.5) in this linear assignment problem and noting that
we find
min
Z
Z
Z
tr QV RS
The second term on the right-hand-side is a constant since
tr u u T BZ
Here we have substituted Z T We proceed to simplify the first term in (6.4),
which is
tr QV RS
From (6.1) we find that s j
hence only the first term in
the sum survives. Noting that s becomes
The third term in (6.4) can be simplified in like manner, and hence ignoring the constant
second term, this equation becomes
c(-
Z
Hence we are required to choose a permutation matrix Z to minimize tr x
. The solution to this problem is to choose Z to correspond to a permutation of
the components of x 2 in non-increasing order, since the components of the vector p are in
increasing order. Note that \Gammax 2 is also an eigenvector of the Laplacian matrix, and since the
positive or negative signs of the components are chosen arbitrarily, sorting the eigenvector
components into non-decreasing order also gives a permutation matrix Z closest, within a
linear approximation, to a different choice for the orthogonal matrix X 0 (see 5.5).
Similar techniques can be used to show that if one is interested in maximizing the 2-sum,
then a closest permutation matrix to the orthogonal matrix that attains the upper bound
in Theorem 5.2 is approximated by sorting the components of the Laplacian eigenvector x n
(corresponding to the largest eigenvalue - n (Q)) in non-decreasing (non-increasing) order.
7. Asymptotic behavior of envelope parameters. In this section, we first prove
that graphs with good separators have asymptotically small envelope parameters, and next
study the asymptotic behavior of the lower bounds on the envelope parameters as a function
of the problem size.
7.1. Upper bounds on envelope parameters. Let ff, fi, and fl be constants such
that (1=2) - ff; class of graphs G has n fl -
separators if every graph G on n ? n 0 vertices in G can be partitioned into three sets A, B,
S such that no vertex in A is adjacent to any vertex in B, and the number of vertices in the
sets are bounded by the relations jAj; jBj - ffn and jSj - fin fl . If n - n 0 , then we choose
the separator S to consist of the entire graph. If n ? n 0 , then by the choice of n 0 ,
and we separate the graph into two parts A and B by means of a separator S. The assumption
that fl is at least a half is not a restriction for the classes of graphs that we are interested
in here: Planar graphs have n 1=2 -separators, and overlap graphs [30] embedded in d - 2
dimensions, have n (d\Gamma1)=d -separators. The latter class includes "well-shaped" finite element
graphs in d dimensions, i.e., finite element graphs with elements of bounded aspect ratio.
Theorem 7.1. Let G be a class of graphs that has n fl -separators and maximum vertex
degree bounded by \Delta. The minimum envelope size Esize min (G) of any graph G 2 G on n
vertices is O(n 1+fl ).
Proof. If then we order the vertices of G arbitrarily. Otherwise, let a separator
separate G into the two sets A and B, where we choose the subset B to have no more
vertices than A. We consider a "modified nested dissection" ordering of G that orders the
vertices in A first, the vertices in S next, and the vertices in B last. (See the ordering in

Figure

2.1, where S corresponds to the set of vertices in the middle column.)
The contribution to the envelope E S made by the vertices in S is bounded by the product
of the maximum row-width of a vertex in S and the number of vertices in S. Thus
We also consider the contribution made by vertices in B that are adjacent to nodes in S,
as a consequence of numbering the nodes in S. There are at most \DeltajSj such vertices in B.
Since these vertices are not adjacent to any vertex in A, the contribution EB made by them
is
the number of vertices in the subset A (B). Adding the contributions
from the two sets of nodes in the previous paragraph, we obtain the recurrence relation
We claim that
for suitable constants C 1 and C 2 to be chosen later. We prove the claim by induction on n.
For the claim may be satisfied by choosing C 1 to be greater than or equal to
Now consider the case when n ? n 0 . Let the maximum in the recurrence relation (7.1)
be attained for an and n
have thus the inductive hypothesis can be applied to the subgraphs induced by
A and B. Hence we substitute the bound (7.2) into the recurrence relation (7.1) to obtain
log an
For the claim to be satisfied, this bound must be less than the right-hand-side of the inequality
(7.2). We prove this by considering the coefficients of each of the terms n 1+fl and
Consider the n 1+fl term first. It is easy to see that a 1+fl
positive. Furthermore, this expression attains its maximum when
a is equal to ff. Denote this maximum value by ffl j ff 1+fl 1. Equating the
coefficients of n 1+fl in the recurrence relation, if
then the first term in the claimed asymptotic bound on E(n) would be true. Both this
inequality and the condition on C 1 imposed by n 0 are satisfied if we choose
We simplify the coefficient of the n 2fl term a bit before proceeding to analyze it. We
have
a 2fl log an
- a 2fl log an log an -
log ff n j ' log ff n
log ff n:
In the transformations we have used the following facts: 1 \Gamma a - a, since a - 1=2; the
maximum of a 2fl and 2fl is greater than or equal to one, is
attained for a = ff; this maximum value ' is less than one. Hence for the claim to hold, we
require
This last inequality is satisfied if we choose
log ff \Gamma1
:A similar proof yields Wbound min which is an upper bound on the work
in an envelope-Cholesky factorization. Hence good separators imply small envelope size and
work. Although we have used a "modified nested dissection" ordering to prove asymptotic
upper bounds, we do not advocate the use of this ordering for envelope-reduction. Other
envelope-reducing algorithms considered in this paper are preferable, since they are faster
and yield smaller envelope parameters.
7.2. Asymptotic behavior of lower bounds. In this subsection we consider the
implications of the spectral lower bounds that we have obtained. We denote the eigenvalue
for the sake of brevity in this subsection. We use the asymptotic behavior of the
second eigenvalues together with the lower bounds we have obtained to predict the behavior
of envelope parameters. For the envelope size, we make use of Theorem 3.2; for the envelope
work, we employ Theorem 3.3.
The bounds on envelope parameters are tight for dense and random graphs (matri-
ces). For instance, the full matrix (the complete graph) has -
Esize Similarly, the bound on the envelope work Ework min
The predicted lower bound is within a factor of three of the envelope size. These bounds are
also asymptotically tight for random graphs where each possible edge is present in the graph
with a given constant probability p, since the second Laplacian eigenvalue satisfies [23]
More interesting are the implications of these bounds for degree-bounded finite element
meshes in two and three dimensions. We will employ the following result proved recently by
Spielman and Teng [38].
Theorem 7.2. The second Laplacian eigenvalue of an overlap graph embedded in d-
dimensions is bounded by O(n \Gamma2=d ). 2
problem separator - 2
size LB UB LB UB
d-dim. O(n 1\Gamma1=d

Table
Asymptotic upper and lower bounds on envelope size and work for an overlap graph in d dimensions.
Planar graphs are overlap graphs in 2 dimensions, and well-shaped meshes in 3 dimensions
are also overlap graphs with

Table

7.1 summarizes the asymptotic lower and upper bounds on the envelope parameters
for a well-shaped mesh embedded in d dimensions. The most useful values are
As before, the lower bound on the envelope size is from Theorem 3.2, while the lower
bound on the envelope work is from Theorem 3.3. The upper bound on the envelope size
follows from Theorem 7.1, and the upper bound on envelope work follows from the upper
bound on Wbound(A), discussed at the end of the proof of that theorem.
The lower bounds are obtained for problems where the upper bounds on the second
eigenvalue are asymptotically tight. This is reasonable for many problems, for instance model
problems in Partial Differential Equations. Note that the regular finite element mesh in a
discretization of Laplace's equation in two dimensions (Neumann boundary conditions) has
is the smallest diameter of an element (smallest mesh spacing
for a finite difference mesh). The regular three-dimensional mesh in the discretized Laplace's
equation with Neumann boundary conditions satisfies -
For planar problems, the lower bound on the envelope size is \Omega\Gamma n), while the upper
bound is O(n 1:5 ). For well-shaped three-dimensional meshes, these bounds
O(n 5=3 ). The lower bounds on the envelope work are weaker since they are obtained from
the corresponding bounds on the envelope size. Direct methods for solving sparse systems
have storage requirements bounded by O(n log n) and work bounded by O(n 1:5 ) for a two-dimensional
mesh; in well-shaped three dimensional meshes, these are O(n 4=3 ) and O(n 2 ).
These results suggest that when a two-dimensional mesh possesses a small second Laplacian
eigenvalue, envelope methods may be expected to work well. Similar conclusions should
hold for three-dimensional problems when the number of mesh-points along the third dimension
is small relative to the number in the other two dimensions, and for two-dimensional
surfaces embedded in three-dimensional space.
8. Computational results. We present computational results to verify how well the
spectral ordering reduces the 2-sum. We report results on two sets of problems.
The first set of problems, shown in Table 8.1, is obtained from John Richardson's (Think-
ing Machines Corporation) program for triangulating the sphere. The spectral lower bounds
reported are from Theorem 5.2. Gap is the ratio with numerator equal to the difference
between the 2-sum and the lower bound, and the denominator equal to the 2-sum. The
results show that the spectral reordering algorithm computes values within a few percent of
the optimal 2-sum, since the gap between the spectral 2-sum and the lower bound is within
that range.
1,026 3,072 4.17e-2 3.75e+6 4.05e+6 7.4
7.3

Table
2-sums from the spectral reordering algorithm and lower bounds for triangulations of the sphere.
Problem
BARTH 6,691 19,748 2.62e-3 6.54e+7 6.69e+7 2.2

Table
2-sums from the spectral reordering algorithm and lower bounds for some problems from the Boeing-
Harwell and NASA collections.

Table

8.2 contains the second set of problems, taken from the Boeing-Harwell and NASA
collections. Here the bounds are weaker than the bounds in Table 8.1. These problems have
two features that distinguish them from the sphere problems. Many of them have less regular
degree distributions-e.g., NASA1824 has maximum degree 41 and minimum degree 5. They
also represent more complex geometries. Nevertheless, these results imply that the spectral
2-sum is within a factor of two of the optimal value for these problems. These results are
somewhat surprising since we have shown that minimizing the 2-sum is NP-complete.
The gap between the computed 2-sums and the lower bounds could be further reduced
in two ways. First, a local reordering algorithm applied to the ordering computed by the
spectral algorithm might potentially decrease the 2-sum. Second, the lower bounds could be
improved by incorporating diagonal perturbations to the Laplacian.
9. Conclusions. The lower bounds on the 2-sums show that the spectral reordering
algorithm can yield nearly optimal values, in spite of the fact that minimizing the 2-sum is
an NP-complete problem. To the best of our knowledge, these are the first results providing
reasonable bounds on the quality of the orderings generated by a reordering algorithm for
minimizing envelope-related parameters. Earlier work had not addressed the issue of the
quality of the orderings generated by the algorithms. Unfortunately the tight bounds on the
2-sum do not lead to tight bounds on the envelope parameters. However, we have shown
that problems with bounded separator sizes have bounded envelope parameters and have
obtained asymptotic lower and upper bounds on these parameters for finite element meshes.
Our analysis further shows that the spectral orderings attempt to minimize the 2-sum
rather than the envelope parameters. Hence a reordering algorithm could be used in a post-processing
step to improve the envelope and wavefront parameters from a spectral ordering.
A combinatorial reordering algorithm called the Sloan algorithm has been recently used to
reduce envelope size and front-widths by Kumfert and Pothen [25]. Currently this algorithm
computes the lowest values of the envelope parameters on a collection of finite element
meshes.

Acknowledgments

. Professor Stan Eisenstat (Yale University) carefully read two drafts
of this paper and pointed out several errors. Every author should be so blessed! Thanks,
Stan.



--R


A spectral algorithm for envelope reduction of sparse matrices
Reducing the bandwidth of sparse symmetric matrices
Ordering methods for preconditioned conjugate gradients methods applied to unstructured grid problems
Direct Methods for Sparse Matrices
The effect of ordering on preconditioned conjugate gradients
The use of profile reduction algorithms with a frontal code
Graph Algorithms
Algebraic connectivity of graphs

in Surveys in Combinatorial Optimization
Matrix inequalities in the L-owner orderings
Computers and Intractability: A Guide to the Theory of NP- Completeness
Computer implementation of the finite element method
Computer Solution of Large Sparse Positive Definite Systems
Algorithm 509: A hybrid profile reduction algorithm

A new algorithm for finding a pseudoperipheral node in a graph
A new lower bound via projection for the quadratic assignment problem
A spectral approach to bandwidth and separator problems in graphs.
An improved spectral graph partitioning algorithm for mapping parallel computations

Laplace eigenvalues and bandwidth-type invariants of graphs

A refined spectral algorithm to reduce the envelope and wavefront of sparse matrices.
Implementations of the Gibbs-Poole-Stockmeyer and Gibbs-King algorithms
Minimum profile of grid networks in structure analysis.

Comparative analysis of the Cuthill-Mckee and the reverse Cuthill-Mckee ordering algorithms for sparse matrices
in Graph Theory and Sparse Matrix Computation
Eigenvalues in combinatorial optimization.
Node and element resequencing using the Laplacian of a finite element graph
Partitioning sparse matrices with eigenvectors of graphs

A projection technique for partitioning the nodes of a graph
Partitioning of unstructured problems for parallel processing
An algorithm for profile and wavefront reduction of sparse matrices

--TR

--CTR
Desmond J. Higham, Unravelling small world networks, Journal of Computational and Applied Mathematics, v.158 n.1, p.61-74, 1 September
Shashi Shekhar , Chang-Tien Lu , Sanjay Chawla , Sivakumar Ravada, Efficient Join-Index-Based Spatial-Join Processing: A Clustering Approach, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1400-1421, November 2002
sparse matrices;quadratic assignment problems;reordering algorithms;2-sum problem;envelope reduction;eigenvalues of graphs;1-sum problem;laplacian matrices