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.