Performance of Greedy Ordering Heuristics for Sparse Cholesky Factorization.
Greedy algorithms for ordering sparse matrices for Cholesky factorization can be based on different metrics. Minimum degree, a popular and effective greedy ordering scheme, minimizes the number of nonzero entries in the rank-1 update (degree) at each step of the factorization. Alternatively, minimum deficiency minimizes the number of nonzero entries introduced (deficiency) at each step of the factorization. In this paper we develop two new heuristics: modified minimum deficiency (MMDF) and modified multiple minimum degree (MMMD). The former uses a metric similar to deficiency while the latter uses a degree-like metric. Our experiments reveal that on the average, MMDF orderings result in 21% fewer operations to factor than minimum degree; MMMD orderings result in 15% fewer operations to factor than minimum degree. MMMD requires  on the average 7--13% more time than minimum degree, while MMDF requires on the average 33--34% more time than minimum degree.
Introduction
. It is well known that ordering the rows and columns of a matrix
is a crucial step in the solution of sparse linear systems using Gaussian elimination. The
ordering can drastically affect the amount of fill introduced during factorization and hence
the cost of computing the factorization [7, 13]. When the matrix is symmetric and positive
definite, the ordering step is independent of the numerical values and can be performed
prior to numerical factorization. The ideal choice is an ordering that introduces the least
fill, but the problem of computing such an ordering is NP-complete [22]. Consequently,
almost all ordering algorithms are heuristic in nature. Examples include reverse Cuthill-McKee
[5, 6, 8], automatic nested dissection [9], and minimum degree [18].
A greedy ordering heuristic numbers columns successively by selecting at each step a
column with the optimal value of a metric. In the minimum degree algorithm of Tinney
and Walker [21] the metric is the number of nonzero entries (and hence operations) in the
update associated with a column in a right-looking, sparse Cholesky factorization.
The algorithm can be stated in terms of vertex eliminations in a graph representing the
matrix [18]; now the metric translates into the degree of a vertex. Efficient implementations
of minimum degree are due to George and Liu [11, 12]. The minimum degree algorithm
with multiple eliminations (MMD) due to Liu [16] has become the method of choice in
the last decade. Multiple independent vertices are eliminated at a single step in MMD
to reduce the ordering time. Recently, Amestoy, Davis, and Duff [1] have developed the
"approximate minimum degree" algorithm (AMD), which uses an approximation to the
degree to further reduce the ordering time. Berman and Schnitger [4] have analytically
shown that the minimum degree algorithm can, in some rare cases, produce a poor ordering.
However, experience has shown that the minimum degree algorithm and its variants are
Work was supported in part by the Defense Advanced Research Projects Agency under contracts
DAAL03-91-C-0047, ERD9501310, and Xerox-MP002315, and by the Applied Mathematical Sciences Re-search
Program, Office of Energy Research, U.S. Department of Energy under contract DE-AC05-96OR22464
with Lockheed Martin Energy Research Corp., and by the National Science Foundation under grants NSF-
ASC-94-11394 and NSF-CDA-9529459.
y Computer Science and Mathematics Division, Oak Ridge National Laboratory, P. O. Box 2008, Oak
Ridge, TN 37831-6367 (ngeg@ornl.gov).
z 107 Ayres Hall, Department of Computer Science The University of Tennessee, Knoxville, TN 37996-
1301 (padma@cs.utk.edu).
effective heuristics for generating fill-reducing orderings. In fact, only some very recent
separator-based schemes [3, 14, 15] have outperformed MMD for certain classes of sparse
matrices. Some of these new schemes are hybrids that use the minimum degree algorithm
to order some of the columns.
A greedy ordering heuristic that was also proposed by Tinney and Walker [21], but
has largely been ignored, is the minimum deficiency (or minimum fill) algorithm. The
minimum deficiency algorithm minimizes the number of fill entries introduced at each step
of sparse Cholesky factorization (or deficiency in graph terminology). Although the metrics
look similar, the minimum deficiency and minimum degree algorithms are different. For
example, the deficiency could well be zero even when the degree is not. There are two reasons
why the minimum deficiency algorithm has not become as popular as the minimum degree
algorithm [7]. First, the minimum deficiency algorithm is typically much more expensive
than the minimum degree algorithm. Second, it has been believed that the quality of
minimum deficiency orderings is not much better than that of minimum degree orderings [7].
Results by Rothberg [19] (and also by us [17]) demonstrate that minimum deficiency leads
to significantly better orderings than minimum degree. However, current implementations
of the minimum deficiency algorithm require substantially more time than MMD.
In this paper, we develop two greedy heuristics that are less expensive to compute than
minimum deficiency, but compute better orderings than minimum degree on average. The
heuristics are variants of minimum deficiency and minimum degree. In Section 2, we provide
background material and introduce some special notation to help describe our heuristics. In
Section 3 we develop our "modified minimum deficiency"(MMDF) and "modified multiple
minimum degree" (MMMD) heuristics. We also show that the two heuristics can be implemented
using the update mechanism in the "approximate degree" scheme of Amestoy, Davis,
and Duff [1]. In Section 4 we provide empirical results on the performance of MMDF and
MMMD. Section 5 contains some concluding remarks. The remaining part of this section
describes recent related work.
Related work. Rothberg has investigated metrics for greedy ordering schemes based on
approximations to the deficiency [19]. His work and our work [17] were done independently
of each other. 1 Rothberg [19]:
ffl shows that the minimum deficiency algorithm is significantly superior to MMD in
terms of the number of operations required to compute the Cholesky factor,
ffl develops three "approximate minimum fill" (AMF) heuristics based on approximations
to the deficiency, and
ffl concludes that heuristic AMF1 is the best among the three; on the average, AMF1
orderings require 14% fewer operations to factor than MMD orderings.
In our earlier report [17], we:
ffl establish that many of the techniques used in efficient implementations of the minimum
degree algorithm (namely, indistinguishable vertices, mass elimination, and
outmatching) also apply to the minimum deficiency algorithm,
ffl corroborate Rothberg's empirical results establishing the superior performance of
the minimum deficiency metric,
ffl develop our "modified minimum deficiency" (MMDF) and "modified multiple minimum
degree" (MMMD) heuristics, and
ffl show that MMDF (MMMD) orderings require 17% (15%) fewer operations to factor
than MMD (on the average).
It is difficult to compare the results in [17] and [19] directly because the test suites used
1 Raghavan and Rothberg presented their results independently at the Second SIAM Conference on
Sparse Matrices in 1996.
in the two papers are substantially different. The aggregate measures reported in the two
papers are also different. Moreover they were based on performance data obtained from
different sets of initial numberings.
More recently, in a revision of [19], Rothberg and Eisenstat have developed two new
metrics for greedy ordering schemes [20]. Rothberg and Eisenstat [20]:
ffl develop two heuristics "approximate minimum mean fill" (AMMF) and "average
minimum increase in neighbor degree" (AMIND), and
ffl show that AMMF orderings require 22% (median) to 25% (geometric mean) fewer
operations to factor than MMD orderings; AMIND orderings require 20% (median)
to 21% (geometric mean) fewer operations to factor than MMD orderings.
This paper is a shorter version of [17]. The test suite in this paper is substantially
different from that in the original paper. In an attempt to compare the performance of our
heuristics with that of the AMF1 (called AMF in [20]), AMMF, and AMIND heuristics in [19]
and [20], we now use nearly the same test suite as in those two papers. Four of the matrices
in [19] and [20] are proprietary, and therefore are not available to us. To report performance
relative to MMD, we had earlier used the "median of ratios" over 7 initial orderings (6
random orderings and the ordering in which the matrix was given to us). In this paper, we
use the "ratio of medians" over 11 random initial orderings (as in [19, 20]). As we will see
later in the paper, our MMDF and MMMD heuristics produce better orderings than MMD.
The MMDF and MMMD orderings are very competitive with those produced by AMF1,
AMMF, and AMIND. What we see as interesting is the development of five different metrics
that can produce orderings that are significantly better than those produced by MMD. We
had commented in our earlier report [17] that there could well be other relatively inexpensive
greedy strategies that outperform the ones known at that time. The performance of newer
schemes AMMF and AMIND [20] supports our prediction; AMMF seems to be slightly
better than our MMDF. As we discuss in Section 5, we still believe that there may well be
other greedy metrics that perform better than the five developed so far.
2. Implementing Greedy Ordering Heuristics. The efficient implementation of
greedy ordering schemes is based on a compact realization of the graph-model of Cholesky
factorization [18]. In this section, we provide a brief description of elimination graphs and
quotient graphs, and introduce an example, together with some notation used to describe
our greedy heuristics. We also describe minimum degree and minimum deficiency schemes
using quotient graphs.
Throughout, we use terminology common in sparse matrix factorization. The reader is
referred to the book by George and Liu [13] for details.
Elimination graphs and quotient graphs. Sparse Cholesky factorization can be
modeled using elimination graphs [18]. Let G denote an elimination graph. At the beginning,
G is initialized to G 0 , the graph of a sparse symmetric positive definite matrix [13]. At each
step a vertex and its incident edges are removed from G. If x is the vertex removed, edges
are added to G so that the neighbors of x become a clique. Thus cliques are formed as the
elimination proceeds.
A quotient graph [10, 13] is a compact representation of an elimination graph. It
requires no more space than that for G 0 [13]. Unlike the elimination graph, vertices are not
explicitly removed and neither are cliques formed explicitly. Instead vertices are grouped in
"supervertices" and marked as "eliminated" or "uneliminated."
Let G denote the current elimination graph. Let S be the set of vertices that have been
eliminated. Consider the subgraph induced by S in G 0 . This subgraph will contain one or
more connected components (which are also called domains). In the quotient graph, the
vertices in each connected component are coalesced into an eliminated supervertex . Note
that the cliques created by the elimination process in G are easy to identify in a quotient
graph. Each such clique contains all (uneliminated) neighbors of an eliminated supervertex.
It is well known that as the elimination proceeds, some (uneliminated) vertices will
become indistinguishable from each other; that is, they share essentially the same adjacency
structure in the current elimination graph G. Now each set of indistinguishable vertices is
coalesced into an uneliminated supervertex in the quotient graph. Observe that all vertices
in an uneliminated supervertex have the same degree (or deficiency) and hence can be
"mass-eliminated" when the degree (or deficiency) becomes minimum [13, 17]. Furthermore,
vertices in an uneliminated supervertex form a clique.
Z
Z 6
Fig. 1. An example of a quotient graph; X is the most recently eliminated supervertex. Supervertices
enclosed in a curve form a clique; other partial cliques used in MMDF are shown using
dotted curves.
Thus a quotient graph can be viewed as a graph containing two kinds of supervertices:
uneliminated supervertices and eliminated supervertices. Each uneliminated supervertex
is a clique of indistinguishable vertices of the corresponding elimination graph G. Each
eliminated supervertex is a subset of the vertices that have been eliminated from the original
graph G 0 . Vertices in the set of uneliminated supervertices adjacent to the same eliminated
supervertex in the quotient graph form a clique in the elimination graph. For simplicity, we
will say that these uneliminated supervertices form a "clique" in the quotient graph. Two
uneliminated supervertices are said to be "neighbors" in the quotient graph when there is an
edge between them or they are adjacent to the same eliminated supervertex in the quotient
graph. Thus vertices belonging one uneliminated supervertex are adjacent to those of the
other supervertex in the corresponding elimination graph.
An example and some notation. Figure 1 contains an example of a quotient graph.
Eliminated supervertices are represented by rectangles and uneliminated supervertices are
represented by circles. Assume that an uneliminated supervertex has been selected according
to the greedy criterion, and the quotient graph has been transformed. This gives a new
eliminated supervertex in the quotient graph. Denote the new eliminated supervertex by X;
in the remaining part of this paper X will be referred to as the "most recently eliminated
supervertex." Using our convention, both Z 1 and Z 2 are neighbors of Y 1 . Note that the
uneliminated supervertices Y (enclosed by a curve), adjacent to the eliminated su-
pervertex X, form a clique. Two other cliques are fY 1 g.
Observe that the three cliques are not disjoint. Uneliminated supervertices that are enclosed
by a dotted curve (such as Z 2 , Z 3 , Z 4 , and Z 5 ) form what we call a "partial" clique; these
"partial" cliques will be used to describe our heuristics in the next section.
If V is a supervertex (either uneliminated or eliminated) in the quotient graph, we define
as the set of uneliminated supervertices that are neighbors of V . We use N 2 (V ) to
denote the set of uneliminated supervertices that are neighbors of those in N 1 (V ). We use
deg(V ) to denote the degree of an uneliminated supervertex
and the total number of vertices in all supervertices in N 1 (V ).
Minimum degree and deficiency schemes. Recall that a greedy heuristic needs a
metric d(v) for selecting the next supervertex to eliminate. Examples of d() are the degree
(in minimum degree) and the deficiency (in minimum deficiency). In terms of elimination
graphs, a greedy heuristic has the following structure: select a vertex that minimizes d(),
eliminate it from the current elimination graph, form the next elimination graph, and update
the value of the metric for each vertex affected by the elimination. A greedy scheme can also
be described in terms of quotient graphs: select an uneliminated supervertex that minimizes
d(), create a new quotient graph, and update the value of the metric for each uneliminated
supervertex affected by the elimination.
In the minimum deficiency heuristic, updating the deficiency after one step of elimination
may be significantly more time consuming than updating the degree in the minimum
degree algorithm. Consider the example in Figure 1 where X is the most recently eliminated
supervertex. With minimum degree (MMD and AMD) only the uneliminated supervertices
in N 1 (X) need a degree update. However, with minimum deficiency, we need to update the
deficiency of not only supervertices in N 1 (X), but also some of the supervertices belonging
to N 2 (X). Any supervertex in N 2 (X) that is a neighbor of two or more supervertices in
would need a deficiency update. With respect to Figure 1, we would have to update
the deficiency of Z 1 since it is a neighbor of both Y 1 and Ym . Similarly, we would have to
update the deficiency of each of Z 5 , Z 6 , \Delta \Delta \Delta, Z k (each supervertex is a neighbor of both Y 1
Rothberg showed that the true minimum deficiency algorithm (true local fill in [19])
produces significantly better orderings than MMD. We obtained similar results in [17].
However, our implementation of the minimum deficiency algorithm was on the average
slower than MMD by two orders of magnitude [17]. Let X be the most recently eliminated
supervertex. Using the deficiency as the metric but restricting updates to uneliminated
supervertices in V 1 (X) (as in MMD) leads to orderings that are inferior to true minimum
deficiency but still significantly better than MMD. This was observed by Rothberg [19] and
later corroborated by Ng and Raghavan [17]. However, even such a restricted scheme is
more than 40 times slower than MMD [17]. In the next section we describe two relatively
inexpensive but effective heuristics based on modifications to the deficiency and degree.
3. Modified Minimum Deficiency and Minimum Degree Heuristics. We now
describe two heuristics based on approximations to the deficiency and the degree. Both
metrics can be implemented using either the update mechanism in MMD or the faster
scheme in AMD.
Our first heuristic "modified minimum deficiency" (MMDF) is based on a deficiency-like
metric. Consider the example in Figure 1 and assume X is the most recently eliminated
supervertex. We update the values of the metric d() of uneliminated vertices in N
just as in MMD. Consider updating d(Y 1 ) in Figure 1. An upper bound ffi on
the deficiency of Y 1 can be obtained in terms of the degree of Y 1 . The true deficiency of
Y 1 is obtained by subtracting from the upper bound the number of edges that are present
before Y 1 is eliminated. Identifying all such edges requires examining the uneliminated
supervertices in N 1 (Y 1 ) and N 2 (Y 1 ). However, some of these edges can be identified easily
because in the quotient graph representation, uneliminated supervertices connected to a
common eliminated supervertex form a clique. Using notation introduced earlier, N 1 (Y 1
is the set of uneliminated neighbors of Y 1 . The elements of
can be grouped into a set of disjoint "partial" cliques K. The obvious member of K is
consisting of the uneliminated neighbors of the eliminated supervertex X. The
other partial cliques depend on the order in which the neighbors of Y 1 are examined. Without
loss of generality, assume fZ 1 g forms the second clique. Likewise let fZ be the
next partial clique we examine. Finally, fZ is the fourth disjoint partial clique.
The metric d(Y 1 ) is defined as is an upper bound on deficiency, C is the sum
of contributions from partial cliques, and ct is the correction term. At initialization,
is set to the upper bound ffi . We define ct below.
The upper bound ffi is based on the external degree [16]:
This upper bound favors larger supervertices. If
two supervertices have the same degree, the larger supervertex will have a smaller
upper bound on deficiency since its external degree is smaller.
K be the set of disjoint partial cliques as described above. We define
is a partial clique in K; the size of V is the total
number of vertices in all uneliminated supervertices that constitute V .
ct : The correction term ct takes into account contributions missed because (1) partial
cliques in K are forced to be disjoint, and (2) cliques such as fZ 1 ; Ym g which
are not detected because we do not examine N 2 (Y 1 ). Our heuristic value of ct is
j. The rationale for the choice of ct is as follows. Assume that
each supervertex in N 1 (Y 1 ) is connected to one other supervertex (in
that the associated contribution has been missed. Assume further that the size of
Y 1 is representative of the sizes of supervertices in N 1 (Y 1 ); then the contributions
that have been missed equal
which simplifies to ct =
We would like to emphasize that MMDF is heuristic. We see the correction term as an
approximation to edges missed because we restrict our attention to partial cliques that are
disjoint. In our experiments we found that small multiples of the correction term behaved
just as well if not better.
Our second heuristic "modified multiple minimum degree" (MMMD) attempts to use
a metric that is bounded by a small multiple of the degree. As indicated by the name it
is a close variant of the minimum degree algorithm with multiple eliminations. Consider

Figure

1 and once again assume X is the most recently eliminated supervertex. For the
uses the metric d(Y 1 U is the size of the
largest partial clique in the set K (described above). More precisely,
initialization we simply use 2 edeg(Y 1 ). Note that MMMD differs from MMD only in the
definition of the metric. The metric in MMMD tries to take into account contributions from
the largest clique that contains Y 1 .
The disjoint partial cliques in the set K of Y 1 are exactly those used implicitly in Liu's
MMD code to compute edeg(Y 1 ). Hence the update cost of MMDF and MMMD is similar
to that of Liu's MMD.
Approximate MMDF and MMMD. We now briefly outline how "approximate"
versions of the two schemes can be implemented using the faster update mechanism in the
AMD scheme of Amestoy, Davis, and Duff [1].
Consider "approximate" MMDF. Consider once again Figure 1 and the metric for Y 1 ,
an uneliminated supervertex adjacent to X, the most recently eliminated supervertex. The
upper bound is now calculated using the approximate external degree of AMD. The correction
term can also be easily calculated in terms of this approximate external degree and
the size of supervertex Y 1 . The main difference is in how K is constructed, and hence the
term C. Now the set K corresponds to the cliques used in AMD to compute an approximation
to the degree. AMD uses the sizes of certain cliques of supervertices in the set
g. With respect to the example in Figure 1, the cliques
used in AMD are: fY g. The first clique is
the one formed by elimination of X; the remaining cliques have no overlap with this clique.
However, the remaining cliques may have supervertices in common. MMDF based on MMD
forces the partial cliques to be disjoint. On the other hand, approximate-MMDF relaxes
this restriction, i.e., it uses the cliques in AMD and these cliques may have common une-
liminated supervertices. The approximation to C (the contribution to the deficiency from
the partial cliques) is computed using the clique sizes used in AMD (for the approximation
to the degree). Approximate-MMMD is similar; it also uses the cliques in AMD.
Relation to other deficiency-like schemes. We would like to note that MMDF
is similar to AMF3, proposed by Rothberg [19]; it differs mainly in the way in which the
partial cliques are constructed, as well as in the definition of the correction term. AMF
("approximate minimum fill"), AMMF ("approximate mean minimum fill") and AMIND
("approximate mean increase in neighbor degree") are three other heuristics developed by
Rothberg and Eisenstat [19, 20]. The deficiency-like metrics in AMF, AMMF, and AMIND
use only edges in the most recently formed clique while the metric in MMDF takes into
account edges in as many cliques as we can "easily identify." AMIND also uses a term
which is similar to our correction term in MMDF. MMMD is similar to AMF in that it uses
only the size of a single clique but it differs in the sense that it uses a degree-like metric.
4. Performance of MMDF and MMMD. We now report on the performance of
MMDF and MMMD. We use a set of 36 test matrices in our empirical study. Our test suite
is a subset of the one used by Rothberg and Eisenstat [19, 20]; their test suite contains four
other matrices that are proprietary and hence are not available to us. Our MMD code is
Liu's Fortran implementation converted to C. Our MMDF and MMMD heuristics are built
using the MMD code. MMDF differs from MMD in the metric update as well in the use of
heaps to store and retrieve the metric. Furthermore, unlike MMD, MMDF does not allow
"multiple eliminations." MMMD is nearly identical to MMD and differs only in the metric
update portion. All our experiments were performed on a Sun Ultra Sparc-2 workstation.
The quality of greedy orderings can vary depending on the initial numbering. For
each test matrix, we use 11 different random initial numberings for MMD, MMDF, and
MMMD. We consider two quantities for the quality of ordering: the number of nonzeros in
the Cholesky factor, and the number of floating-point operations required to compute the
We also report actual execution times for MMD, MMDF, and MMMD.
The characteristics of the test matrices and the quality of MMD orderings are reported in

Table

1. We report mean and median values over 11 initial random numberings for MMD
in

Table

1.

Table

2 shows the performance of MMDF and MMMD relative to that of MMD. The
relative measure is computed as the ratio of the medians over 11 initial random numberings.
We also present the geometric mean and the median over all test matrices in the last two
lines of the table. The execution time of MMMD matches that of MMD, while MMDF
Performance of MMD; jLj and operations are mean and median values over 11 initial orderings.
Problem rank jAj mean median
Time jLj Operations Time jLj Operations
bcsstk36 23052 1166.2 1.56 2760 609 1.56 2761 609
crystk01 4875 320.7 0.46 1082 337 0.46 1083 338
crystk03 24696 1775.8 3.92 13943 13050 3.92 13944 13051
gearbox 153746 9234.1 40.52 52972 57327 40.52 52973 57328
msc10848 10848 1240.6 1.07 2028 576 1.07 2028 576
pwt 36519 326.1 2.51 1768 224 2.51 1768 225
struct2 73752 3670.9 7.74 9810 3817 7.74 9810 3817
struct3 53570 1227.3 6.36 5309 1215 6.36 5309 1216
struct4 4350 242.1 2.07 2248 1756 2.07 2248 1756
troll 213453 1198.5 42.37 61171 153228 42.37 61171 153228
Performance of MMDF and MMMD relative to MMD. For each problem we report the ratio of
median values over 11 initial random orderings.
Problem Ordering time jLj Operations
MMDF MMMD MMDF MMMD MMDF MMMD
bcsstk36 1.68 1.47 1.01 1.00 0.98 0.96
crystk01 1.33 1.22 0.91 0.89 0.80 0.77
crystk02 1.23 1.04 0.86 0.83 0.72 0.68
crystk03 1.25 1.04 0.89 0.80 0.79 0.64
flap 1.50 1.06 0.93 0.91 0.81 0.78
gearbox 1.58 1.13 0.91 1.00 0.77 1.17
pwt 1.48 1.03 0.94 0.97 0.85 0.92
struct1 1.72 1.08 0.95 0.96 0.85 0.90
struct2 1.80 1.06 0.97 0.98 0.94 0.93
struct3 1.28 1.05 0.95 0.96 0.87 0.90
troll 1.13 1.04 0.80 0.85 0.65 0.73
g-mean 1.33 1.13 0.91 0.92 0.80 0.84
median 1.34 1.07 0.92 0.95 0.80 0.86
requires on average an overhead of 34% over MMD. Our experiments indicate that avoiding
the use of heaps in MMDF (as suggested by a referee) will reduce about a third of this
overhead.
Results for variants of MMDF and MMMD are summarized in Table 3. The approximate
versions of MMDF and MMMD were based on our implementation of AMD
and did not include features such as "aggressive absorption." The approximate version of
MMDF/MMMD performs equally well; the geometric mean and the median are the same as
those for MMDF/MMMD. For both MMDF and MMMD (and their approximate versions),
adding Ashcraft's initial compression step [2] improved the performance slightly (1% on the
average).

Table
Summary of performance of MMDF and MMMD variants relative to MMD. The geometric-mean
and median over all problems in the test suite is based on the ratio of median values over 11 initial
random orderings for each problem.
Method jLj Operations
g-mean median g-mean median
initial compression
With initial compression
5. Conclusions. We have developed two new greedy heuristics: "modified minimum
deficiency" (MMDF) and "modified multiple minimumdegree" (MMMD). Both these schemes
produce orderings that are better than MMD orderings. The first scheme MMDF produces
orderings that require approximately 21% fewer floating-point operations for factorization
than MMD, while the second scheme MMMD generates orderings that incurs 15% fewer
operations for factorization than MMD. MMDF uses a deficiency-like metric, i.e., a metric
whose value is a quadratic function of the degree. The execution time of MMDF is approximately
1:3 times that of MMD. On the other hand, MMMD uses a degree-like metric, which
is bounded above by twice the value of the degree. MMMD is the same as MMD but for the
difference in the choice of the metric. Consequently, the ordering time of MMMD is very
similar to that of MMD. Furthermore, there is no change in the quality of the orderings
when MMDF (MMMD) is implemented using "approximate degree" [1] framework.
For completeness, Table 4 summarizes the performance of our schemes, as well as
those in [20]. It appears that the performance of MMMD and "approximate minimum
fill" (AMF1 [19] and AMF [20]) are similar. Likewise, MMDF and "approximate mean
increase in neighbor degree" (AMIND [20]) produce orderings of similar quality. "Approxi-
mate mean minimum fill" (AMMF [20]) appears to be slightly better than MMDF. Relative
to MMD, AMMF orderings require 25% (geometric mean) to 22% (median) fewer operations
for factorization, while MMDF (with compression) orderings require 21% (geometric mean
and median) fewer operations for factorization.

Table
Summary of operation counts to factor for MMDF, MMMD, AMF, AMMF, and AMIND relative
to MMD (with initial compression).
Measure Ng-Raghavan Rothberg-Eisenstat
MMDF MMMD AMF1 AMMF AMIND
g-mean .79 .84 .85 .75 .79
median .79 .85 .85 .78 .80
Our work is an attempt to understand factors affecting the performance of greedy ordering
heuristics. We tried several metrics that are close to those in MMDF and MMMD.
Many of these had average operation counts for factorization similar to those reported for
MMDF and MMMD, while others varied substantially. We also experimented with a variant
of MMDF that did update the metric for "neighbors of neighbors" as in true minimum
deficiency. Surprisingly, the operation counts were on the average higher by 3-4% for this
variant. The performance of true minimum deficiency shows that deficiency is a better metric
than the degree. However, we surmise that the improved performance of our heuristics
is from the complicated interplay of the metric and the greedy process, and not necessarily
from accurately modeling the true deficiency. We conjecture that there could well be
other relatively inexpensive greedy strategies that significantly outperform the ones known
so far.



--R

An approximate minimum degree ordering algorithm
Compressed graphs and the minimum degree algorithm
Robust orderings of sparse matrices using multisection
On the performance of the minimum degree ordering for Gaussian elimination
Several strategies for reducing bandwidth of matrices
Reducing the bandwidth of sparse symmetric matrices
Direct Methods for Sparse Matrices
Computer Implementation of the Finite Element Method
An automatic nested dissection algorithm for irregular finite element problems




Fast and effective algorithms for graph partitioning and sparse matrix or dering
Improving the runtime and quality of nested dissection ordering
Modification of the minimum degree algorithm by multiple elimination
Performance of greedy ordering heuristics for sparse cholesky fac- torization
A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations
Ordering sparse matrices using approximate minimum local fill.
Node selection strategies for bottom-up sparse matrix ordering
Direct solution of sparse network equations by optimally ordered triangular factorization
Computing the minimum fill-in is NP-complete
--TR

--CTR
Abdou Guermouche , Jean-Yves L'Excellent , Gil Utard, Impact of reordering on the memory of a multifrontal solver, Parallel Computing, v.29 n.9, p.1191-1218, September
Patrick R. Amestoy , Iain S. Duff , Stphane Pralet , Christof Vmel, Adapting a parallel sparse direct solver to architectures with clusters of SMPs, Parallel Computing, v.29 n.11-12, p.1645-1668, November/December
Timothy A. Davis , John R. Gilbert , Stefan I. Larimore , Esmond G. Ng, A column approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.353-376, September 2004
Timothy A. Davis, A column pre-ordering strategy for the unsymmetric-pattern multifrontal method, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.165-195, June 2004
minimum degree;sparse matrix ordering;greedy heuristics;minimum deficiency