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.