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).