Orderings for Incomplete Factorization Preconditioning of Nonsymmetric Problems.
Numerical experiments are presented whereby the effect of reorderings on the convergence of preconditioned Krylov subspace methods for the solution of nonsymmetric linear systems is shown. The preconditioners used in this study are different variants of incomplete factorizations. It is shown that certain reorderings for direct methods, such as reverse Cuthill--McKee, can be very beneficial. The benefit can be seen in the reduction of the number of iterations and also in measuring the deviation of the preconditioned operator from the identity.
Introduction
. In this paper, we study experimentally how di#erent reorderings
a#ect the convergence of Krylov subspace methods for nonsymmetric systems of
linear equations when incomplete LU factorizations are used as preconditioners. In
other words, given a sparse linear system of equations are n-dimensional
vectors, we consider symmetric permutations of the matrix A, i.e., of the
then solve the equivalent system P T
way of some preconditioned iterative method. Our focus is on linear systems arising
from the discretization of second order partial di#erential equations, which often are
structurally symmetric (or very nearly so) and have a zero-free diagonal. For these ma-
trices, it is usually possible to carry out an incomplete factorization without pivoting
for stability (that is, choosing the pivots from the main diagonal). Such properties are
preserved under symmetric permutations of A, but not necessarily under nonsymmetric
ones. Hence, we restrict our attention to symmetric permutations only. We stress
the fact that very di#erent conclusions may hold for matrices which are structurally
far from being symmetric, although we have little experience with such problems.
If A is structurally symmetric, the reorderings are based on the (undirected) graph
associated with the structure of A; otherwise, the structure of A A T is used. We
consider several iterative methods for nonsymmetric systems, including GMRES [43],
Bi-CGSTAB [48], and transpose-free QMR (TFQMR) [28]; for a description of these,
as well as a description of incomplete factorizations, see, e.g., [3], [42].
In this paper, we mainly concentrate on orderings originally devised for matrix
those used to reduce fill-in in the factors; see, e.g., [18] or [29]. We
want to call attention to the fact that a permutation of the variables (and equations)
# Received by the editors September 4, 1997; accepted for publication (in revised form) March 31,
1998; published electronically May 6, 1999.
http://www.siam.org/journals/sisc/20-5/32684.html
Computing Group (CIC-19), MS B256, Los Alamos National Laboratory, Los Alamos,
NM 87545 (benzi@lanl.gov). This work was supported in part by the Department of Energy through
grant W-7405-ENG-36 with Los Alamos National Laboratory.
# Department of Mathematics, Temple University, Philadelphia, PA 19122-6094 (szyld@math.
temple.edu). The work of this author was supported by National Science Foundation grant DMS-
9625865.
- Department of Computer Science, Leiden University, 2300 RA Leiden, The Netherlands (arno@
cs.leidenuniv.nl).
using reordering methods designed for direct solvers can have an important positive
e#ect on the robustness and performance of preconditioned Krylov subspace methods
when applied to nonsymmetric linear systems. This is especially the case if the matrices
are far from symmetric. This observation, although not completely new, is not
fully appreciated, to the point that some authors have concluded that direct solver
reorderings should not be used with preconditioned iterative methods; see section 2.
It is hoped that the present study will contribute to a reassessment of direct solver
reorderings in the context of incomplete factorization preconditioning. Furthermore,
we hope that the evidence of our experiments can set the stage for more widespread
use of these reorderings.
Many papers have been written on the e#ect of permutations on the convergence
of preconditioned Krylov subspace methods. The main contributions are surveyed,
together with some of our observations, in section 2. In section 3 we present our
numerical experiments and comment on those results. Finally, in section 4 we present
our conclusions.
2. Overview of the literature. The influence of reorderings on the convergence
of preconditioned iterative methods has been considered by a number of authors.
Several of these papers are concerned with symmetric problems only [8], [12], [14], [21],
[24], [27], [36], [37], [38], [45], [49]. In this context, Du# and Meurant [21] have performed
a very detailed study of the e#ects of reorderings for preconditioned conjugate
gradients, i.e., in the symmetric positive definite case. Based on their extensive exper-
iments, they concluded that the number of iterations required for convergence with
direct solver reorderings is usually about the same as, and sometimes considerably
higher than, with the natural (lexicographic) ordering. An important observation in
[21] is that the number of conjugate gradient iterations is not related to the number
of fill-ins discarded in the incomplete factorization (as conjectured by Simon [44]) but
is almost directly related to the norm of the residual matrix
is an incomplete Cholesky factor of A; see [1] for a rigorous derivation of this result
under appropriate conditions. Throughout the paper we abuse the notation and use
A to denote both the original matrix and the permuted one. Similarly, -
L and -
U refer
to the incomplete factors of A or those of P T AP , depending on the context.
As it can be seen in the experiments in section 3, for the test matrices that are
nearly symmetric, our observations are in agreement with those of Du# and Meurant:
the reorderings have no positive e#ect on the convergence of the preconditioned Krylov
methods. On the other hand, for the highly nonsymmetric test matrices, i.e., when
the nonsymmetric part is large, we conclude that reorderings can indeed make a big
di#erence. Permutations that appear to be ine#ective for the (nearly) symmetric case
turn out to be very beneficial, often improving the robustness and performance of
the preconditioned iteration dramatically. (It is worth emphasizing that in [21], only
symmetric problems are considered.)
In addition, we will see that for problems that are strongly nonsymmetric and/or
are far from being diagonally dominant, the norm of the residual matrix R alone is
usually not a reliable indicator of the quality of the corresponding preconditioner. It
has been pointed out, e.g., in [11], that a more revealing measure of the quality of the
preconditioner can be obtained by considering the Frobenius norm of the deviation
of the preconditioned matrix from the identity, i.e., #I - A( -
. Note that
this quantity is equal to #R( -
Even if R is small in norm, it could happen
that ( -
U) -1 has very large entries, resulting in a large deviation of the preconditioned
matrix from the identity. As a result, the preconditioned iteration fails to converge. A
1654 MICHELE BENZI, DANIEL B. SZYLD, AND ARNO VAN DUIN
notable example of this phenomenon occurs when convection-dominated convection-
di#usion equations are discretized with centered finite di#erences. When the natural
(lexicographic) ordering is used, the incomplete triangular factors resulting from a
no-fill ILU factorization tend to be very ill conditioned, even if the coe#cient matrix
itself is well conditioned. Allowing more fill-in in the factors, e.g., using ILU(1) or
ILUT instead of ILU(0), will solve the problem in some cases but not always. This
kind of instability of ILU factorizations was first noticed by van der Vorst [47] and
analyzed in detail by Elman [25].
We will see that in some cases, reordering the coe#cient matrix before performing
the incomplete factorization can have the e#ect of producing stable triangular factors,
and hence more e#ective preconditioners. Generally speaking, #R#F and #R( -
do not contain enough information to describe in a quantitative fashion the behavior
of incomplete factorizations. In particular, it is not possible in general to establish
comparisons between incomplete factorizations based on these quantities alone. This
is not surprising, considering that for general nonsymmetric problems it is not known
how to predict the rate of convergence of iterative solvers. In practice, however,
one can expect that very ill-conditioned incomplete -
L and -
U factors will result in a
poor preconditioner. As suggested in [11], an inexpensive way of detecting this ill-conditioning
is by computing #( -
denotes a vector of all ones. This
is only a lower bound for #( -
but is quite useful in practice.
The e#ects of permutations on preconditioned Krylov subspace methods for non-symmetric
problems have been considered in [9], [13], [15], [16], [17], [22], [33], [44],
[46]. Some authors have concluded that the reorderings designed for sparse direct
solvers are not recommended for use with preconditioned iterative methods; see, e.g.,
[14], [33], [44]. Simon [44] used quotient minimum degree and nested dissection [29] in
conjunction with an ILU preconditioner for some oil simulation problems and found
essentially no improvement over the original ordering. He wondered if this strategy
would be advantageous for other kinds of problems. Similar conclusions were reached
by Langtangen [33], who applied a minimum degree reordering with ILU(0) preconditioning
of matrices arising from a Petrov-Galerkin formulation for convection-di#usion
equations. It should be mentioned that neither the problems considered by Simon nor
those considered by Langtangen exhibited any kind of instability of the incomplete
triangular factors and that most of those problems can be regarded as fairly easy
to solve, at least by today's standards. Dutto [22], in the context of a specific application
(solving the compressible Navier-Stokes equations with finite elements on
unstructured grids), was possibly the first to observe that minimum degree and other
direct solver reorderings can have a positive e#ect on the convergence of GMRES with
preconditioning. This is mostly consistent with some of our own experiments
reported here.
In the context of oil reservoir simulations, reverse Cuthill-McKee and some variants
of it were found to perform satisfactorily for symmetric, strongly anisotropic
problems due to the fact that these orderings are relatively insensitive to anisotropies
[4], [12], [49]. Numerical experiments indicating that the D2 diagonal ordering (which
is a special case of Cuthill-McKee) for ILU(k) preconditioning of certain nonsymmetric
problems defined on rectangular grids can be superior to the natural ordering
were reported in [5], but this observation did not receive the attention it deserved.
This may be due in part to the fact that the authors use a terminology that is peculiar
to the field of reservoir simulation. A short paragraph mentioning that level
set reorderings (like reverse Cuthill-McKee) can be useful for preconditioned iterative
methods can be found in [42], and similar remarks are no doubt found elsewhere in
the literature. In spite of this, reorderings for direct methods are still widely regarded
as ine#ective (or even bad) for preconditioned iterative methods.
We also mention the minimum discarded fill (MDF) algorithm (see [13], [14]),
which takes into account the numerical values of the entries of A. This method can
be very e#ective, but it is often too expensive to be practical, except for rather simple
problems.
In addition to reorderings which were originally designed for direct methods, one
can use the permutation produced by the algorithm TPABLO [10], which also uses the
magnitude of the entries of the matrix. This algorithm produces a permuted matrix
with dense diagonal blocks, while the entries outside the blocks on the diagonal have
magnitude below a prescribed threshold. Hence, like MDF, the TPABLO reordering is
based both on graph information and on the numerical values. The original motivation
for the TPABLO algorithm was to produce good block diagonal preconditioners, and
also blocks for the treatment of certain Markov chain problems [10]; see also [23]. It
turns out that this reordering is also useful for point incomplete factorizations, where
it is often better than the natural ordering [6] and some of the reorderings considered
in this paper [7]. However, for most cases treated in this paper, the performance of
TPABLO is inferior to that of some of the reorderings designed for direct methods,
and thus we do not report results with it here. TPABLO might prove useful in the
context of block incomplete factorizations, but this topic is outside the scope of the
present paper.
Finally, a number of papers have considered other kinds of reorderings, such as
those motivated by parallel computing (e.g., multicoloring; see [8], [15], [27], [37]) and
reorderings based on the physics underlying the discrete problem being solved [9].
Such reorderings can be very useful in practice, but they are strongly architecture
and problem specific.
3. Numerical experiments. In this section we show, by means of numerical
experiments, that direct solver reorderings can be very beneficial when solving difficult
nonsymmetric linear systems (obviously, at best, little gains can be expected
from reordering problems which are easily solved with the original ordering). The results
reported here are a representative selection from a large number of experiments
with nonsymmetric matrices arising from the numerical solution of partial di#er-
ential equations. In the first subsection we focus on an important class of problems
(convection-di#usion equations discretized with finite di#erences), while in the second
we present a selection of results for matrices from a variety of applications. In the last
subsection we investigate reasons why reordering improves the performance of the pre-
conditioners. All the experiments were performed on a Sun Ultra SPARC workstation
using double precision arithmetic. Codes were written in standard Fortran-77.
3.1. Convection-di#usion equations. A source of linear systems which can
be challenging for iterative methods is the following partial di#erential equation in
the open unit
#x
#y
(1)
with homogeneous Dirichlet boundary conditions. Equation (1) has been repeatedly
used as a model problem in the literature; see, e.g., [39]. The problem is discretized
using centered di#erences for both the second order and first order derivatives with
leading to a block tridiagonal linear system of order 1024 with
nonzero coe#cients. While this is a small problem size, it exhibits the features
we wish to address here. Numerical experiments were also performed with finer grids
and with a three-dimensional analogue of the same PDE, and the results obtained
were similar to those reported in Tables 1-4 below. For the right-hand side we used
a random vector. Results similar to those in Tables 1-4 were obtained with other
choices of b. In all our experiments we used v guess and we stopped
the iterations when the 2-norm of the (unpreconditioned) residual b - Av k had been
reduced to less than 10 -4 or when a maximum number of iterations was reached. The
parameter # > 0 controls the di#culty of the problem-the smaller # is, the harder it is
to solve the discrete problem by iterative methods. For our experiments, we generated
linear systems of increasing di#culty, corresponding to #
The coe#cient matrix A becomes more nonsymmetric (and less diagonally dominant)
as # decreases. If we denote by S and T the symmetric and the skew-symmetric part
of A, respectively, then for #
gets smaller, the norm of T remains unchanged, whereas the norm of S decreases. For
We point out incidentally that these quantities
are invariant under symmetric permutations, so the departure from symmetry cannot
be altered simply by reordering the matrix; however, we will see that from the point
of view of incomplete factorization preconditioning, some orderings are less sensitive
to the departure from symmetry than others.
There are many possible ways of implementing the (reverse) Cuthill-McKee and
minimum degree reorderings. We used Liu's multiple minimum degree algorithm [34],
and for the Cuthill-McKee reorderings, we used an implementation which chooses
a pseudoperipheral node as starting node and sorts nodes in the same level set by
increasing degree [29]. Other strategies are possible as well, and di#erent choices may
lead to somewhat di#erent results. We note here that we experimented also with one-way
and nested dissection reorderings, and for discrete convection-di#usion problems
the results found were comparable to those obtained with the multiple minimum
degree reordering, both from the point of view of fill-in in the incomplete factors and
from the point of view of convergence rates. For this reason we do not show these
results in the tables.
We report the results of experiments with the following accelerators: Bi-CGSTAB,
TFQMR, and GMRES with restart parameter 20. The preconditioners used were
standard incomplete factorizations based on levels of fill (ILU(0) and ILU(1); see [35])
and Saad's dual threshold ILUT; see [41], [42]. For ILUT, we used two di#erent sets
of parameters, (10 -2 , 5) and (10 -3 , 10). The latter results in a very powerful but
expensive preconditioner, containing up to five times the number of nonzeros in A.
Right preconditioning was used in all cases.
In

Tables

1-4 we present the number of iterations for the di#erent orderings and
the three Krylov subspace methods used in this study. In these tables, and in the
ones that follow, n/o stands for natural (or original) ordering, CM for Cuthill-McKee,
RC for reverse Cuthill-McKee, and MD for multiple minimum degree. The symbol
indicates that convergence was not achieved in 250 iterations for Bi-CGSTAB and
TFQMR, which require two matrix-vector products and applications of the preconditioner
per iteration, and in 500 iterations for GMRES(20), which requires only one
matrix-vector product and preconditioner application per iteration. In each case the
number in bold indicates the run which required the least amount of work. This is
not always the same as the run which required the least number of iterations because,

Table
Number of iterations for di#erent orderings, preconditioner ILU(0).
300 17 19 28 27 26 27 79 15 15 15
28
43

Table
Number of iterations for di#erent orderings, preconditioner ILU(1).
28 8 8
900 142 12
in general, di#erent reorderings result in preconditioners with a di#erent number of
nonzeros (except, of course, for ILU(0), where the number of nonzeros is always equal
to the number of nonzero entries in A). For this particular class of matrices, the
amount of fill-in in the incomplete factors is often highest for the natural ordering.
Cuthill-McKee and reverse Cuthill-McKee result in comparable fill-in (slightly less,
on average, than with the natural ordering), while minimum degree produces the least
amount of fill-in. For example, in the case # 100, the ILUT(10 -2 , 5) factors contain
12907 nonzeros with the natural ordering, 10271 nonzeros with Cuthill-McKee,
10143 nonzeros with reverse Cuthill-McKee, and 9038 nonzeros for multiple minimum
degree. As # gets smaller, these values slowly increase (more or less uniformly for all
orderings). For # we have 14695 nonzeros for the natural ordering, 15023
for Cuthill-McKee, 14259 for reverse Cuthill-McKee, and 9348 for multiple minimum
degree.
We now comment on the numerical results. We notice that for the moderately
nonsymmetric problems (smaller values of # -1 ), the alternative permutations o#er little
or no advantage over the natural ordering. In particular, the Cuthill-McKee and
reverse Cuthill-McKee reorderings produce nearly the same results as the natural
ordering. It is known (see, e.g., [50, sections 5.5 and 5.6]) that for five-point stencils
and no-fill factorizations, the Cuthill-McKee reorderings are equivalent to the natural
ordering in the sense that the incomplete factors of the permuted matrix are just the
permuted incomplete factors of the original matrix. Hence the ILU(0) preconditioners
with the natural ordering and Cuthill-McKee reorderings are mathematically equiv-
alent. This is true, however, only if the starting node is the same for both types of

Table
Number of iterations for di#erent orderings, preconditioner ILUT(10 -2 , 5).

Table
Number of iterations for di#erent orderings, preconditioner ILUT(10 -3 , 10).
orderings. For our implementation of (reverse) Cuthill-McKee, this is not the case in
general. Hence, there are some di#erences in the number of iterations obtained. We
note that these discrepancies are more pronounced for larger values of # -1 , suggesting
that the sensitivity of ILU(0) preconditioning to the choice of the starting node
becomes stronger as the matrix becomes increasingly nonsymmetric and farther from
being diagonally dominant.
For larger values of #, minimum degree causes a serious degradation of the convergence
rate, especially with ILU(0). Notice that the di#erences in behavior are not
as pronounced with the ILUT preconditioners, which use a drop tolerance.
As the coe#cient matrix becomes increasingly nonsymmetric, however, things
change. While the number of iterations increases for all reorderings, the rate of
increase is not the same for all reorderings, suggesting that some orderings are less
sensitive than others to the degree of nonsymmetry. For ILU(0), the natural ordering
and the Cuthill-McKee reorderings exhibit the worst degradation as # decreases. The
best performance is achieved with minimum degree, which is the only reordering
which caused all three iterative solvers to converge on all problems. The situation is
quite di#erent with ILU(1) and the ILUT preconditioners. With ILU(1), the natural
ordering performs poorly, minimum degree is only slightly better, but the Cuthill-McKee
reorderings are both quite good. With ILUT(10 -2 , 5) minimum degree is very
bad and the Cuthill-McKee orderings are both excellent. With ILUT(10 -3 , 10), which
gives very good (but expensive) approximations of A, all orderings produce e#ective
preconditioners, but the performance is particularly good with the Cuthill-McKee
reorderings. Notice that reverse Cuthill-McKee is only slightly better than Cuthill-
McKee. It is worth mentioning that for the natural, cuthill-McKee, and reverse
cuthill-McKee orderings the number of nonzeros in the ILUT(10 -3 , 10) factors is
approximately 35% of the number of nonzeros in the complete LU factors computed
with the same ordering; for multiple minimum degree, this proportion goes up to about
58%. For the more powerful preconditioners (ILU(1) and ILUT) the cuthill-McKee
reorderings give the best results for all values of #. As far as the relative performance
of the three Krylov subspace solvers is concerned, we observe that they are more
or less equivalent for this particular class of problems, with GMRES(20) requiring
fewer matrix-vector products and preconditioner applications than the other solvers
in many cases.
This set of problems was generated using second order, centered di#erence approximations
for both the second and first partial derivatives in (1). It is well known
that for large values of h/#, this discretization can become unstable. Alternative dis-
cretizations, such as those which use upwinding for the first order terms, do not su#er
from this problem and give rise to matrices with very nice properties from the point
of view of iterative solutions, such as diagonal dominance. However, this may not be
true for nonuniform grids (see [30]), and, moreover, such approximations are only first
order accurate and in many cases are unable to resolve fine features of the solution,
such as boundary layers. In this case, as suggested in [31], a uniform coarse grid could
be used to determine the region where the boundary layer is located (this corresponds
to "wiggles" in an otherwise smooth solution). This would require solving linear systems
such as those considered in the previous set of experiments. Subsequently, a local
mesh refinement can be performed in the region containing the boundary layer. This
solves the instability problem, and the approximation is still second order accurate
(except at a few points on the interface between the coarse and the fine grids), but the
resulting linear system, like the one corresponding to the uniform grid, can be quite
challenging for iterative methods if convection is strong. Again, a simple reordering
of the coe#cient matrix can improve the situation dramatically. To illustrate this, we
take the following example from Elman [26]. Consider the following partial di#erential
equation
#x
#y
(2)
and the right-hand side g and the boundary conditions are determined
by the solution
e 2P (1-x)
e 2P
e 2Py
e 2P
This function is nearly identically zero
in# except for boundary layers of width
O(#) near coarse grid was used in the
region where the solution is smooth, and a uniform fine grid was superimposed on
the regions containing the boundary layers, so as to produce a stable and accurate
see [26] for details.
We performed experiments with These values are
considerably larger than those used in [26]. The resulting matrices are of order 5041
and 7921, with 24921 and 39249 nonzeros, respectively. The convergence criterion used
was a reduction of the residual norm to less than 10 -6 ; the initial guess, right-hand
side, and maximum number of iterations allowed were the same as for the previous
set of the experiments. When ILU(0) preconditioning was used, no iterative solver

Table
Number of iterations for di#erent orderings and preconditioners.
Preconditioner P n/o CM RC MD n/o CM RC MD n/o CM RC MD

Table
Test problem information.
Matrix N NZ Application Source
engineering Harwell-Boeing
ale1590 1590 45090 Metal forming simulation S. Barnard
utm1700b 1700 21509 Plasma physics SPARSKIT
fidap007 1633 54487 Incompressible flow SPARSKIT
converged within the maximum allowed number of iterations, independent of the re-ordering
used. However, with minimum degree the three solvers appeared to be slowly
converging, whereas with the other reorderings the iteration either diverged or stag-
nated. The results for ILU(1) and ILUT preconditioning and various orderings are
reported in Table 5. We note that the natural ordering and the cuthill-McKee re-orderings
produced the same or comparable amount of fill-in for all preconditioners,
whereas multiple minimum degree resulted in higher fill-in with ILU(1) and considerably
less fill-in with the ILUT preconditioners with respect to the other reorderings.
From these results, we observe that reorderings do not have a great impact on the performance
of ILU(1) when In contrast, reorderings make a di#erence when
used with the ILUT preconditioners, with cuthill-McKee producing the best results.
Reverse cuthill-McKee is much better than the natural ordering but is not quite as
good as cuthill-McKee. Multiple minimum degree is bad with ILUT(10 -2 , 5) but it
performs well with ILUT(10 -3 , 10), although it is not as e#ective as cuthill-McKee.
Notice that for preconditioners fail when the natural ordering is used.
For this particular example cuthill-McKee dramatically improves the performance of
ILUT preconditioners. Finally, we mention that similar results were obtained with
recirculating flow problems in which the coe#cients of the first order terms in the
convection-di#usion equation have variable sign.
3.2. Miscellaneous problems. The results in the previous subsection are relative
to an important, but nevertheless rather special, class of problems. It is not clear
to what extent, if any, those observations can be applied to other problems. For this
reason, we discuss additional experiments performed on a selection of nonsymmetric
matrices from various sources, including the Harwell-Boeing collection [19] and Saad's
SPARSKIT [40]. These matrices arise from di#erent application areas: oil reservoir
modeling, plasma physics, neutron di#usion, metal forming simulation, etc. Some of
these matrices arise from finite element modeling, and they have a much more complicated
structure than those of the previous subsection. Also, they tend to be more
ill conditioned. Some information about the matrices is provided in Table 6, where

Table
Number of iterations for di#erent orderings, preconditioner ILU(0).
Bi-CGSTAB GMRES TFQMR
Matrix n/o CM RC MD n/o CM RC MD n/o CM RC MD

Table
Number of iterations for di#erent orderings, preconditioner ILU(1).
Bi-CGSTAB GMRES TFQMR
Matrix n/o CM RC MD n/o CM RC MD n/o CM RC MD
watt2 28 31 15 17 17 17
ale1590 22
N is the order of the matrix and NZ is the number of nonzeros.
The degree of di#culty of these problems varies from moderate (watt2) to extreme
(utm5940 and fidap007). Concerning problem ale1590, which was provided by
Barnard [2], the original ordering caused the coe#cient matrix to have some zero
entries on the main diagonal. This may cause trouble for the construction of ILU
preconditioners. Therefore, the matrix was first reordered into a form with a zero-
using a nonsymmetric permutation described in [20]. As for problem
this matrix was extracted from the AUGUSTUS unstructured mesh
di#usion package developed by Michael Hall at Los Alamos National Laboratory; see
[32]. It should be mentioned that analogous results to those reported here for ker-
shaw60x60 were obtained with di#erent matrices extracted from this package. The
convergence criterion used here is a residual norm reduction to less than 10 -9 , due to
the greater di#culty of these problems. All the remaining parameters are the same
as those used in the previous subsection.
The ILUT parameters were (10 -2 , 5) and (10 -3 , 10) for the first four matrices (as
in the experiments in Tables 3 and 4), whereas di#erent parameters had to be used for
the last three problems, due to their di#culty. For the matrix utm3060 the parameters
used were (10 -3 , 10) and (10 -5 , 20); for utm5940, (10 -3 , 30) and (10 -4 , 40); and for
fidap007, (10 -5 , 50) and (10 -7 , 70). In Tables 9 and 10 we refer to ILUT with these
two sets of parameters as ILUT1 and ILUT2, respectively.
The minimum degree reordering always produced the least amount of fill-in in
the preconditioner, while the original ordering and the cuthill-McKee reorderings
usually gave comparable fill-in. A notable exception is fidap007: for this matrix,
the cuthill-McKee reordering resulted in considerably more fill-in in the incomplete
factors than the original ordering or reverse cuthill-McKee. In Tables 9 and 10 the
indicates that the maximum storage allowed for the preconditioner has been
exceeded before the preconditioner construction was completed. This corresponds to
approximately 300,000 nonzeros in the incomplete factors. In the tables, n/o refers to

Table
Number of iterations for di#erent orderings, preconditioner ILUT1.
Bi-CGSTAB GMRES TFQMR
Matrix n/o CM RC MD n/o CM RC MD n/o CM RC MD

Table
Number of iterations for di#erent orderings, preconditioner ILUT2.
Bi-CGSTAB GMRES TFQMR
Matrix n/o CM RC MD n/o CM RC MD n/o CM RC MD
watt2
ale1590
the original ordering of the matrices. With GMRES, the restart parameter used was
all cases except for kershaw60x60, for which, due to the amount of storage
used.
It should be mentioned that for the matrices from plasma physics, the standard
implementation of the cuthill-McKee reorderings caused a breakdown (zero pivot)
of the ILU(1) and ILUT factorizations. Hence, it is possible for these reorderings to
produce a poor pivot sequence. This di#culty was circumvented by applying to these
matrices a slightly di#erent version of (reverse) cuthill-McKee, in which the first
node is chosen as the initial node (that is, there is no search of a pseudoperipheral
node), and no attempt is made to order nodes within a level set by increasing degree.
Instead, the order of the nodes is determined by the order in which they are traversed;
see [18]. With this implementation, no zero or very small pivots were encountered.
The results with these matrices are reported in Tables 7-10. They are somewhat
less clear-cut than those for the convection-di#usion problems. Nevertheless, it can
be seen that reorderings helped in a large majority of cases. While cuthill-McKee
and minimum degree did not perform well with ILU(0) and ILU(1), reverse cuthill-McKee
did with few exceptions. Reverse cuthill-McKee was also useful with the
ILUT preconditioners. For the more di#cult problems which could be solved only
allowing high amounts of fill-in in the factors, minimum degree proved useful.
We add that another version of ILUT, the ILUTP preconditioner (see [42]), was
also tried. This is ILUT combined with a column pivoting strategy, and it is known
to be sometimes better than ILUT, especially for problems leading to small pivots.
For this set of experiments, however, ILUTP was found to be no better than ILUT.
3.3. Further analysis of the results. The results of the experiments presented
show that a simple reordering of the coe#cient matrix can bring about a dramatic
improvement in the quality of incomplete factorization preconditioners. In particular,
we saw problems where all preconditioned iterative solvers failed with the natural

Table
Norms of A-
U and I -A( -
di#erent orderings, preconditioner ILU(0).
n/o CM RC MD
200 2.70e-01 1.09e+04 2.71e-01 9.74e+03 2.70e-01 1.10e+04 1.36e+00 4.89e+01
300 3.23e-01 8.89e+04 3.26e-01 8.15e+04 3.23e-01 9.08e+04 1.88e+00 7.42e+01
400 3.53e-01 2.68e+05 3.57e-01 2.73e+05 3.53e-01 2.74e+05 2.41e+00 9.97e+01
500 3.72e-01 5.28e+05 3.78e-01 1.01e+06 3.72e-01 5.40e+05 2.94e+00 1.25e+02
700 3.97e-01 1.34e+06 4.04e-01 8.60e+07 3.97e-01 1.30e+06 4.01e+00 1.75e+02
800 4.06e-01 3.26e+06 4.13e-01 4.86e+08 4.06e-01 2.79e+06 4.53e+00 2.00e+02
900 4.14e-01 9.93e+06 4.20e-01 1.98e+09 4.14e-01 8.25e+06 5.05e+00 2.25e+02
1000 4.22e-01 2.69e+07 4.26e-01 6.25e+09 4.22e-01 2.26e+07 5.57e+00 2.50e+02

Table
Norms of A-
U and I -A( -
di#erent orderings, preconditioner ILU(1).
n/o CM RC MD
100 4.60e-02 1.70e+00 4.90e-02 2.13e+00 4.59e-02 2.09e+00 4.21e-01 1.30e+01
200 1.31e-01 6.56e+00 8.57e-02 4.68e+00 7.94e-02 5.21e+00 5.49e-01 1.89e+01
300 1.79e-01 1.08e+01 1.09e-01 6.47e+00 9.56e-02 7.51e+00 6.95e-01 2.53e+01
400 2.09e-01 1.44e+01 1.30e-01 8.12e+00 1.06e-01 9.42e+00 8.49e-01 3.23e+01
500 2.29e-01 1.77e+01 1.50e-01 9.77e+00 1.12e-01 1.11e+01 1.01e+00 3.96e+01
700 2.55e-01 2.36e+01 1.86e-01 1.32e+01 1.22e-01 1.41e+01 1.33e+00 5.46e+01
800 2.64e-01 2.63e+01 2.02e-01 1.49e+01 1.26e-01 1.56e+01 1.49e+00 6.21e+01
900 2.71e-01 2.89e+01 2.17e-01 1.67e+01 1.29e-01 1.70e+01 1.66e+00 6.96e+01
1000 2.77e-01 3.14e+01 2.30e-01 1.85e+01 1.33e-01 1.83e+01 1.82e+00 7.71e+01
ordering and all converged rapidly after a symmetric permutation of the coe#cient
matrix. In this subsection, we investigate the reasons behind these observations.
An incomplete factorization preconditioner can fail or behave poorly for several
reasons. A common cause of failure is instability of the incomplete factorization,
which is caused by numerically zero pivots or exceedingly small ones. The result of
this type of instability is that the incomplete factorization is very inaccurate, that
is, the norm of the residual matrix
U is large. This is a very real possibility
for matrices that do not have some form of diagonal dominance and for highly
unstructured problems. Of course, an inaccurate factorization can also occur in the
absence of small pivots, when many large fill-ins are dropped from the incomplete
factors. Another kind of instability, which can take place whether or not small pivots
occur, is severe ill-conditioning of the triangular factors, which reflects the instability
of the long recurrences involved in the forward and backward solves when the pre-conditioning
is applied [25], [47]. In this situation, #R#F need not be very large, but
be. Again, this is a common situation when
the coe#cient matrix is far from being diagonally dominant. Of course, both types
of instabilities can simultaneously occur for a given problem; see [11] for an extensive
experimental study of the causes of failure of incomplete factorizations.
In order to gain some insight about the e#ect of reorderings, we computed the
Frobenius norms of R and R( -
U) -1 for each test matrix, reordering, and precon-
ditioner. Those for the matrices arising from the discretization of problem (1) are
reported in Tables 11-14, where
U#F and
Loosely speaking, N1 measures the accuracy of the incomplete factorization, whereas

Table
Norms of A-
U and I -A( -
di#erent orderings, preconditioner ILUT(10 -2 , 5).
n/o CM RC MD
100 9.20e-03 5.65e-01 4.96e-03 2.06e-01 2.57e-03 1.07e-01 1.39e-01 4.64e+00
200 3.09e-02 2.64e+00 5.22e-03 2.82e-01 4.71e-03 2.48e-01 3.13e-01 1.01e+01
300 5.64e-02 6.21e+00 1.13e-02 7.42e-01 8.58e-03 4.93e-01 5.08e-01 1.83e+01
500 1.00e-01 1.21e+01 2.81e-02 1.98e+00 1.68e-02 1.21e+00 9.98e-01 1.62e+02
700 1.43e-01 1.84e+01 5.20e-02 3.96e+00 2.43e-02 2.07e+00 2.03e+00 1.69e+03
800 1.78e-01 2.79e+01 6.21e-02 4.89e+00 2.83e-02 2.54e+00 7.39e+01 5.81e+06
900 6.57e+20 1.69e+33 9.88e-02 8.86e+00 3.22e-02 3.08e+00 9.37e+00 1.12e+05
1000 6.47e+28 3.98e+43 9.82e-02 8.33e+00 3.54e-02 3.52e+00 2.28e+01 3.71e+06

Table
Norms of A-
U and I -A( -
di#erent orderings, preconditioner ILUT(10 -3 , 10).
n/o CM RC MD
100 1.48e-03 8.56e-02 5.09e-04 2.05e-02 3.77e-04 1.63e-02 4.76e-02 1.62e+00
200 7.18e-03 4.99e-01 6.05e-04 2.93e-02 4.97e-04 2.68e-02 1.13e-01 3.85e+00
300 1.82e-02 1.36e+00 1.51e-03 9.48e-02 1.11e-03 6.76e-02 1.79e-01 6.24e+00
400 3.14e-02 2.49e+00 3.41e-03 2.36e-01 2.06e-03 1.39e-01 2.55e-01 9.00e+00
500 4.61e-02 3.78e+00 6.48e-03 4.78e-01 3.08e-03 2.28e-01 3.39e-01 1.21e+01
700 8.37e-02 8.56e+00 1.45e-02 1.15e+00 5.87e-03 5.01e-01 5.48e-01 1.92e+01
800 9.85e-02 1.08e+01 1.90e-02 1.55e+00 7.88e-03 6.98e-01 6.45e-01 2.29e+01
900 1.19e-01 1.43e+01 2.45e-02 2.08e+00 1.00e-02 9.34e-01 7.42e-01 2.68e+01
1000 1.48e-01 1.98e+01 2.96e-02 2.54e+00 1.18e-02 1.13e+00 8.39e-01 3.08e+01
N2 measures its stability (in the sense of [25]). We also monitored the size of the
pivots in the course of the incomplete factorizations, and we did not find any very
small pivots. Hence, failure or poor behavior of an incomplete factorization could be
due to significantly large fill-ins having been dropped, to unstable triangular solves,
or both.
The results in Table 11 give a clear explanation of the convergence behavior of
iterative methods with ILU(0) preconditioning reported in Table 1. For the natural,
cuthill-McKee, and reverse cuthill-McKee orderings the degradation and eventual
failure in the convergence as # -1 increases is not due to inaccuracy of the incomplete
factorizations, but to instability of the triangular solves. As # -1 increases, the
condition number of the no-fill incomplete factors grows rapidly, the preconditioned
becomes more and more ill conditioned, and the number of iterations
increases. Furthermore, for large enough # -1 , Elman [25] observed that the
symmetric part of A( -
becomes indefinite, and this in turn can cause failure of
the Krylov subspace accelerators. Inspection of the last column in Table 11 reveals
that minimum degree has the e#ect of stabilizing the ILU(0) triangular factors. The
preconditioner remains well conditioned even for large values of # -1 , and all three
Krylov subspace methods converge. The fact that the number of iterations still increases
with increasing # -1 appears to be due to the fact that the ILU(0) factorization
becomes less accurate, as measured by N1. We observe that for the moderately non-symmetric
problems the number of iterations is almost directly related
to
norm alone is not a good
indicator of the e#ectiveness of the preconditioner and
comes a more reliable indicator. Notice that minimum degree always results in less
accurate ILU(0) factors (larger N1) than the other orderings.
The results in Table 2 show that ILU(1) preconditioning is more robust and
e#ective than ILU(0) for this class of problems, and the Frobenius norms presented
in

Table

12 show that this is due to the fact that ILU(1) does not su#er from the
kind of instability that plagues ILU(0). Because of this,
U#F is now
a fairly accurate indicator of the performance of the preconditioner for all values
of # -1 . The values reported for N1 indicate that the cuthill-McKee reorderings
outperform the natural ordering because they result in more accurate ILU(1) factors
and that minimum degree is inferior to the other orderings because the incomplete
factorization is less accurate.
We mention that some ad hoc stabilization techniques to be used with ILU(0)
for convection-di#usion problems have been proposed in [26] and [47]. Our results
indicate that using ILU(1) with a level set reordering of the matrix o#ers a simple
solution to the instability problem.
Similar results apply to the ILUT preconditioners (Tables 13 and 14). However,
there are two phenomena that occur with ILUT(10 -2 , 5) and not with ILUT(10 -3 , 10)
that deserve to be mentioned. For # 900, the ILUT(10 -2 , 5) preconditioner with
natural ordering fails rather dramatically. An inspection of the corresponding entries
of

Table

13 shows that this is due to the simultaneous occurrence of inaccuracy in the
factorization (large #R#F -too many large fill-ins have been dropped) and instability
in the triangular factors (as revealed by a much larger value of #R( -
This is
an illustration of the fact that for strongly nonsymmetric problems, increasing fill-in
in the incomplete factors does not necessarily result in an improved preconditioner,
unless the factorization approaches an exact one; see also [11]. We mention that the
number of nonzeros in the factors is considerably higher for ILUT(10 -2 , 5) than for
ILU(1). The other interesting phenomenon is that with ILUT(10 -2 , 5), the incomplete
factors obtained with minimum degree are not only less accurate than those for the
other reorderings but also unstable when # becomes large. This is the opposite
of what happens for ILU(0) and confirms that the relative performance of a given
reordering is di#erent for di#erent preconditioning strategies, as already observed
in [21]. When ILUT(10 -3 , 10) is used, the accuracy of the incomplete factorization
approaches that of a direct solve and none of the orderings su#ers from instability
(note that the original coe#cient matrix A is fairly well conditioned for all values
of # -1 ). The norm of
U again becomes a very reliable indicator of the
performance of the preconditioners corresponding to the di#erent permutations. The
cuthill-McKee reorderings give better results than the other orderings because they
make the incomplete factorization more accurate, as is indicated by the values for N1
reported in Table 14. For fixed values of the ILUT parameters, the amount of fill-in
in the incomplete factors is only slightly less with the cuthill-McKee reorderings
than with the natural ordering, whereas the number of nonzeros in the complete LU
factors is much less. Hence, when compared to the natural ordering, the cuthill-McKee
reorderings allow one to compute a more accurate incomplete factorization for
roughly the same arithmetic and storage costs for this class of problems.
The Frobenius norms #R#F and #R( -
were also computed for the two
matrices arising from problem (2). For ILU(0), the failures with the natural ordering
and the cuthill-McKee reorderings were due to the concurrent e#ect of inaccuracy and
instability of the triangular solves (again, no small pivots arise for these problems).
The instability was especially severe for the case. For instance, with the
cuthill-McKee ordering we found On the
other hand, no instabilities occurred with minimum degree, and the failures with this
reordering were due to inaccurate factorizations
With minimum degree, the computed residual was reduced to about 10 -5 by all
three iterative methods preconditioned with ILU(0) when the maximum number of
iterations was reached. With the natural ordering and cuthill-McKee reorderings,
on the other hand, there was divergence or stagnation at much higher values of the
residual. Thus, it appears that instability in the preconditioner has a more devastating
e#ect than low accuracy of the factorization.
With ILU(1), no instabilities occurred. The failures with the natural ordering
and with multiple minimum degree for were due to low accuracy of the
factorization (large N1). With the ILUT preconditioners, the failures with the natural
ordering are due to the simultaneous occurrence of inaccuracy in the factorization and
unstable triangular solves, very much like the case in Table 13 for #
the other orderings produced stable incomplete factorizations. The failures with the
minimum degree ordering and ILUT(10 -2 , 5) preconditioning were due to inaccuracy
of the factorization.
Again, the best results are obtained with the cuthill-McKee reorderings and
ILUT preconditioning, which yield accurate and stable factorizations. We note that
for these problems, cuthill-McKee is somewhat better than reverse cuthill-McKee.
The Frobenius norms of R and R( -
were also computed for the problems of
section 3.2. In most cases, when considered together they were found to give a qualitative
explanation of the observed convergence behavior. Whenever a preconditioner
failed, it was usually due to inaccuracy rather than instability, with the exception
of fidap007 with ILUT preconditioning and cuthill-McKee reordering, for which the
factorization was both inaccurate and severely unstable.
4. Conclusions. We have provided evidence that reorderings originally designed
for use with sparse direct solvers can significantly improve the performance of iterative
methods preconditioned with incomplete LU factorizations. While not entirely new,
an examination of the literature reveals that this fact is not widely known.
The benefit of reordering the coe#cient matrix depends in part on how far the
matrix is from being symmetric and diagonally dominant, as well as on the type of
incomplete factorization preconditioner used. In our experiments with regular grid
problems, we found that when the coe#cient matrix is nearly symmetric, very little
is gained from reordering it. On the other hand, if the matrix is strongly nonsymmet-
ric, large reductions of the number of iterations can be obtained by (symmetrically)
reordering the matrix.
A somewhat surprising result of our experiments is that the "natural" or "orig-
inal" ordering of the test matrices used in this study is almost never the best from
the point of view of incomplete factorization preconditioning and is very often the
worst. More specifically, the original ordering was found to give the best results in
only 13 cases out of the 228 comparisons reported in this paper. Reverse cuthill-McKee
gave the best results in 132 cases, cuthill-McKee in 57 cases, and multiple
minimum degree in cases. The original ordering was found to be worse than the
other orderings also from the point of view of robustness: there were 61 failures with
the original ordering, 54 with multiple minimum degree, 48 with cuthill-McKee, and
only 37 with reverse cuthill-McKee. There were 26 cases where the original ordering
led to a failure and reverse cuthill-McKee succeeded, but only two cases where
reverse cuthill-McKee failed and the original ordering succeeded (matrix utm5940
with ILU(1) preconditioning; see Table 10).
It should be stressed that in most cases for which reverse cuthill-McKee was
not best, it still gave good results (that is, it was not found to be much worse than
the best ordering). Hence, overall, reverse cuthill-McKee appears to be superior
to the other orderings in the context of incomplete factorization preconditioning.
As revealed by a direct inspection of the residual matrices A -
U , in most cases
this was simply due to the fact that this reordering produced more accurate (as
measured by #A -
factorizations than those obtained with the
natural ordering, with a comparable amount of fill-in in the factors. In some cases the
improvement was due to the fact that the reordering resulted in a stabilization of the
incomplete triangular factors (as measured by #I-A( -
However, none of the
orderings considered in this paper were found to be completely immune from potential
instabilities in the corresponding triangular solves. In most cases where instabilities
occurred, the problem disappeared by allowing more fill-in in the incomplete factors,
but not always. Indeed, there were a few cases where increasing the amount of fill-in
made things worse in the sense that the instability of the factors increased; see also
[11].
In general, cuthill-McKee cannot be recommended. While it performed well
on many problems, its behavior is rather erratic. Reverse cuthill-McKee should be
preferred.
The minimum degree reordering was found to be inferior to the level set reorderings
in general, but often better than the original ordering. It is well known that for
the purpose of complete sparse factorization, minimum degree is usually much more
e#ective at preserving sparsity than level set reorderings. Thus, this reordering could
be useful when the LU factorization with the original ordering su#ers from extremely
high fill-in, and a sparse preconditioner is sought. For the same choice of the ILUT
parameters, this reordering always resulted in incomplete factors which were considerably
more sparse than those obtained with the other reorderings. While it is true
that minimum degree is more expensive to compute than the level set reorderings,
this cost is usually of the order of only a few iterations.
Of course, reverse cuthill-McKee is not trouble-free. The quality of the corresponding
preconditioner will be a#ected, in general, by the choice of the initial node
and by the ordering of nodes within level sets. In particular, it is not clear how di#er-
ent tie-breaking strategies will a#ect the incomplete factorization. It is also possible
that some orderings within level sets will produce a poor pivot sequence and a break-down
of the incomplete factorization process. Moreover, it is easy to contrive examples
where reverse cuthill-McKee will be a poor ordering, for example, by constructing
a convection-di#usion problem for which the reverse cuthill-McKee ordering of the
grid points goes against the flow direction.
Nevertheless, based on the results of our experiments, we conclude that much
can be gained from reordering strongly nonsymmetric matrices before performing an
incomplete factorization and not much should be lost, particularly when the reverse
cuthill-McKee reordering is used. For convection-di#usion problems on rectangular
grids, ILU(1) or ILUT preconditioning combined with reverse cuthill-McKee is rec-
ommended, whereas the lexicographic ordering behaves rather poorly and should be
avoided. For matrices that do not have a "natural" ordering, such as those arising
from unstructured meshes, we recommend reverse cuthill-McKee as the original or-
dering. A similar conclusion was reached in [21] for symmetric matrices arising from
the finite element method.
Concerning possible developments of this study, an interesting possibility would
be to consider a red-black approach, where the reduced system is reordered with
reverse cuthill-McKee. Some promising results with this approach were reported
in [5]. It would also be interesting to study the e#ects of combining nonsymmetric
permutations designed for moving large entries to the diagonal (see [20]) with the
symmetric permutations considered in this paper.
Finally, there are some open questions which warrant further investigation. As
already mentioned, some understanding of the e#ect of the choice of the initial node
and of the ordering within level sets on the performance of (reverse) cuthill-McKee
would be welcome. Also, with reference to the linear systems arising from the discretization
of model problem (1) or similar ones, it would be desirable to understand
why the ILU(0) factors computed with the minimum degree ordering do not su#er
from the instability that occurs when the natural ordering (or the equivalent level set
are used. Likewise, it would be instructive to understand why the ILU(1)
factors were found to be stable regardless of the ordering used to compute them; see

Table

2. At present, we are unable to see how Elman's analysis [25] for the ILU(0)
preconditioner with the natural and equivalent orderings could be applied to more
complicated preconditioners and to other orderings.

Acknowledgments

. We have benefited from the advice and assistance of several
colleagues during the writing of this paper. Howard Elman read and commented
on drafts of the paper during its early stages and o#ered many good suggestions.
Discussions with Wayne Joubert and Mike DeLong were also helpful. Hwajeong Choi
and Jacko Koster provided some of the codes which were used for the numerical
experiments. Special thanks go to Miroslav T-uma, who not only provided us with
some of his software but also was very generous in sharing his insight on sparse matrix
reorderings at various stages of this project. We are indebted to G-erard Meurant,
whose questions and detailed reading helped us turn report [7] into this paper. Part
of this research took place while the first author was with CERFACS and the second
author was a visitor there. CERFACS's support and warm hospitality are greatly
appreciated.



--R

Vectorizable preconditioners for elliptic di
A portable MPI implementation of the SPAI preconditioner in ISIS
Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods


Threshold ordering for preconditioning nonsymmetric problems
Orderings for Incomplete Factorization Precondi- tionings of Nonsymmetric Problems
Parallel elliptic preconditioners: Fourier analysis and performance on the connection machine
On preconditioned Krylov subspace methods for discrete convection- di#usion problems
Application of threshold partitioning of sparse matrices to Markov chains
Experimental study of ILU preconditioners for indefinite matrices
Weighted graph based ordering techniques for preconditioned conjugate gradient methods


SOR as a preconditioner
On parallelism and convergence of incomplete LU factorizations
A Graph-Theory Approach for Analyzing the E#ects of Ordering on ILU Preconditioning
Direct Methods for Sparse Matrices
Sparse matrix test problems
The design and use of algorithms for permuting large entries to the diagonal of sparse matrices


Parallelizable block diagonal preconditioners for the compressible Navier-Stokes equations
Analysis of parallel incomplete point factorizations
A stability analysis of incomplete LU factorizations
Relaxed and stabilized incomplete factorizations for non-self-adjoint linear sys- tems

A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems
Computer Solution of Large Sparse Positive Definite Systems
Diagonal dominance and positive definiteness of upwind approximations for advection di
Don't suppress the wiggles
A Second-Order Cell-Centered Di#usion Di#erence Scheme for Unstructured Hexahedral Lagrangian Meshes
Conjugate gradient methods and ILU preconditioning of non-symmetric matrix systems with arbitrary sparsity patterns
Modification of the minimum degree algorithm by multiple elimination
An iterative solution method for linear systems of which the coe
Ordering Methods for Approximate Factorization Preconditioning
Orderings for conjugate gradient preconditionings
Multicolor ICCG methods for vector computers
Preconditioning techniques for nonsymmetric and indefinite linear systems
SPARSKIT: A Basic Tool Kit for Sparse Matrix Computations
ILUT: A dual threshold incomplete LU factorization
Iterative Methods for Sparse Linear Systems
GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems
Incomplete LU preconditioners for conjugate-gradient-type iterative methods
Orderings for parallel conjugate gradient preconditioners

Iterative solution methods for certain sparse linear systems with a non-symmetric matrix arising from PDE-problems


Iterative Solution of Large Linear Systems
--TR

--CTR
E. Flrez , M. D. Garca , L. Gonzlez , G. Montero, The effect of orderings on sparse approximate inverse preconditioners for non-symmetric problems, Advances in Engineering Software, v.33 n.7-10, p.611-619, 29 November 2002
Michele Benzi, Preconditioning techniques for large linear systems: a survey, Journal of Computational Physics, v.182 n.2, p.418-477, November 2002
nonsymmetric matrices;incomplete factorizations;preconditioned iterative methods;linear systems;krylov subspace methods;permutation of sparse matrices;reorderings