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

TITLE: Permuting Markov Chains to Nearly Completely Decomposable Form

AUTHOR: Tugrul Dayar

ABSTRACT: This paper highlights an algorithm that computes, if possible, a 
nearly completely decomposable (NCD) partitioning for a given Markov chain 
using a specified decomposability parameter. The algorithm is motivated by
search for connected components (CCs) of an undirected graph. The nestedness
of the NCD partitionings for increasing values of the decomposability 
parameter is demonstrated on the Courtois matrix. The relation among the 
degree of coupling, the smallest eigenvalue of the coupling matrix and the 
magnitude of the subdominant eigenvalue of the block Gauss-Seidel (BGS) 
iteration matrix induced by the underlying NCD partitionings is investigated 
on the same matrix. Experimental results that appear elsewhere show that the 
partitioning algorithm may be used successfully in two-level iterative 
solvers such as block successive over-relaxation (BSOR) and iterative
aggregation-disaggregation (IAD).