TECHNICAL REPORT BU-CEIS-9805, BILKENT UNIVERSITY, 
DEPARTMENT OF COMPUTER ENGINEERING AND INFORMATION SCIENCE

TITLE: Comparison of Partitioning Techniques for Two-Level Iterative Solvers
       on Large, Sparse Markov Chains

AUTHORS: Tugrul Dayar and William J. Stewart

ABSTRACT: Experimental results for large, sparse Markov chains, especially
the ill-conditioned nearly completely decomposable (NCD) ones, are few. 
We believe there is need for further research in this area, specifically to 
help in understanding the effects of the degree of coupling of NCD Markov 
chains and their nonzero structure on the convergence characteristics and 
space requirements of iterative solvers. The work of several researchers 
has raised the following questions that led to research in a related direction.
How one must go about partitioning the global coefficient matrix into blocks
when the system is NCD and a two-level iterative solver (such as block SOR)
is to be employed? Are block partitionings dictated by the NCD form of the 
stochastic one-step transition probability matrix necessarily superior to 
others? Is it worth investing alternative partitionings? Better yet, for a 
fixed labeling and partitioning of the states, how does the performance of
block SOR (or even that of point SOR) compare to the performance of the
iterative aggregation-disaggregation (IAD) algorithm? Finally, is there any 
merit in using two-level iterative solvers when preconditioned Krylov subspace
methods are available? We seek answers to these questions on a test suite of
thirteen Markov chains arising in seven applications.