Threshold Partitioning of Sparse Matrices and
Applications to Markov Chains
Hwajeong Choi and Daniel B. Szyld
Department of Mathematics
Temple University, Philadelphia, Pennsylvania 19122-2585, USA
(choi@math.temple.edu, szyld@math.temple.edu).
Abstract.
It is well known that the order of the variables and equations
of a large, sparse linear system influences the performance of
classical iterative methods. In particular if, after a symmetric
permutation, the blocks in the diagonal have more nonzeros,
block methods have a faster asymptotic rate of convergence.
In this paper, different ordering and partitioning algorithms
for sparse matrices are presented. They are modifications of
PABLO [SIAM J. Sci. Stat. Computing, 11 (1990) 811--823].
In the new algorithms, in addition to the location of the
nonzeros, the values of the entries are taken into account.
The matrix resulting after the symmetric permutation has dense
blocks along the diagonal, and small entries in the off-diagonal
blocks. Parameters can be easily adjusted to obtain, for example,
denser blocks, or blocks with elements of larger magnitude.
In particular, when the matrices represent Markov chains, the
permuted matrices are well suited for block iterative methods that
find the corresponding probability distribution.
Also, if the partition obtained from the ordering algorithm
with certain parameters is used as an aggregation scheme, an
iterative aggregation method performs better with this partition
than with others found in the literature.
The complexity of the new algorithms is linear in the number of
nonzeros and the order of of the matrix, and thus adding little
computational effort to the overall solution.
Numerical experiments are presented which illustrate the
performance of the block iterative methods and of the
aggregation/disaggregation methods with the new orderings.