on Large, Sparse Markov Chains

Department of Computer Engineering and Information Science,

Bilkent University,

06533 Bilkent, Ankara, Turkey

and

WILLIAM J. STEWART

Department of Computer Science,

North Carolina State University,

Raleigh, NC 27695-8206

Abstract

Solving for the stationary distribution of an irreducible Markov chain amounts
to computing a positive solution vector to a homogeneous system of linear
equations with a singular coefficient matrix, *A*, subject to a
normalization constraint. Despite recent advances, practicing performance
analysts generally prefer iterative methods based on splittings when they want
to compare the performance of newly devised algorithms against existing ones,
or when they need candidate solvers to evaluate the performance of a systems
model at hand. 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 [11],[6],
[7],[5],[1],[10],[8] has raised important and interesting questions that led
to research in a related direction. These questions are the following: "How
must one go about partitioning the global coefficient matrix *A* 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 normal form
of *P*, 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 [15]? Finally, is
there any merit in using two-level iterative solvers when preconditioned Krylov
subspace methods [13], [4], [12], [3], [14] are available?"

When seeking answers to these questions, we have not considered two-level
solvers of the inner-outer iteration type [10], but have attempted at solving
diagonal blocks (and the coupling matrix [9] in IAD) directly by Gaussian
elimination. The memory needed to solve the coupling matrix is set aside at
the beginning and what is left is used for diagonal blocks. Blocks of order 1
and 2 are treated separately. We obtain the *LU* factorizations of as many
diagonal blocks as possible given available memory and do this in such a way
that smaller blocks are treated first, leaving the big blocks to be solved
using point SOR when there is insufficient memory. Currently, we use a
considerably larger tolerance (i.e., 0.001), a relaxation parameter of 1.0
(hence, Gauss-Seidel), and a maximum number of iterations of 100 with the point
SOR algorithm when solving diagonal blocks. Furthermore, the block Gauss-Seidel
correction [18] in the disaggregation step of IAD is replaced by block SOR.

Four block partitioning techniques are considered. The first one results from
the near-complete decomposability test *(ncdtest)* of the MARkov Chain
Analyzer (MARCA) [16]. It determines the strongly connected components of the
transition probability matrix by ignoring the nonzeros less than a prespecified
decomposability parameter. Then symmetric permutations are performed to put the
matrix into the form in which the diagonal blocks form the strongly connected
components. In a recent paper [2], it is shown that the *ncdtest*
algorithm may fail to produce a correct NCD partitioning of the state space.
The same paper gives an improved NCD partitioning algorithm, which has the same
run-time complexity as that of *ncdtest*. We name this new NCD
partitioning algorithm *newncd* and experiment with it. Also two
straightforward partitionings are investigated. The *equal* partitioning
forms (approximately) equal order blocks. The second straightforward
partitioning, *other*, uses blocks of order respectively 1,2,3,...
Finally, the Threshold PABLO (TPABLO) partitioning algorithm [1] is considered
on some of the test problems.

Results of experiments on a large suite of Markov chains [17] show that
two-level iterative solvers are in most cases superior to incomplete *LU*
(ILU) preconditioned Krylov subspace solvers. For two-level iterative solvers,
there are cases in which a straightforward partitioning of the coefficient
matrix gives a faster solution than can be obtained using the *ncdtest* or
*newncd* partitioning algorithms. However, in between *newncd* and
*ncdtest*, the former gives faster converging iterations than the latter
in a larger number of the test cases. In general, it is possible to solve each
of the problems (except one which takes a minimum of about 82 seconds to solve)
in less than 1 minute. This includes time spent for partitioning or
preconditioning.

References:

- H. Choi and D. B. Szyld.
Application of threshold partitioning of sparse matrices to Markov chains.
*Proceedings of the IEEE International Computer Performance and Dependability Symposium IPDS'96*(1996) 158-165. - T. Dayar.
Permuting Markov chains to nearly completely decomposable normal form,
*SIAM J. Matrix Anal. Appl.*, submitted for publication. - R. W. Freund and M. Hochbruck.
On the use of two QMR algorithms for solving singular systems and
applications in Markov chain modelling.
*Numer. Linear Algebra with Applic.*, 1, 403-420, 1994. - D. Gross, B. Gu, and R. M. Soland.
The biconjugate gradient method for obtaining the steady-state probability
distributions of Markovian multiechelon repairable item inventory systems.
In W. J. Stewart (Ed.),
*Numerical Solution of Markov Chains*, M. Dekker, Inc., NY (1991), 473-489. - S. T. Leutenegger and G. H. Horton.
On the utility of the multi-level algorithm for the solution of nearly
completely decomposable Markov chains.
In W. J. Stewart (Ed.),
*Computations with Markov Chains: Proceedings of the Second International Workshop on the Numerical Solution of Markov Chains*, Kluwer, Boston (1995), 425-442. - I. Marek and D. B. Szyld.
Iterative and semi-iterative methods for computing stationary probability
vectors of Markov operators.
*Math. Comp.*, 61, 719-731, 1993. - I. Marek and D. B. Szyld.
Local convergence of the (exact and inexact) iterative aggregation method
for linear systems and Markov operators.
*Numer. Math.*, 69, 61-82, 1994. - I. Marek and P. Mayer.
Convergence theory of an aggregation/disaggregation iteration method.
*J. Comp. Appl. Math.*, 62, unassigned, 1997. - C. D. Meyer.
Stochastic complementation, uncoupling Markov chains, and the theory of
nearly reducible systems.
*SIAM Rev.*, 31, 240-272, 1989. - V. Migallón, J. Penadés, and D. B. Szyld.
Block two-stage methods for singular systems and Markov chains.
*Numer. Linear Algebra with Applic.*, 3, 413-426, 1996. - J. O'Neil and D. B. Szyld.
A block ordering method for sparse matrices.
*SIAM J. Sci. Stat. Comput.*, 11, 811-823, 1990. - B. Philippe, Y. Saad, and W. J. Stewart.
Numerical methods in Markov chain modelling.
*Opns. Res.*, 40, 1156-1179, 1992. - Y. Saad.
Projection methods for the numerical solution of Markov chain models.
In W. J. Stewart (Ed.),
*Numerical Solution of Markov Chains*, M. Dekker, Inc., NY (1991), 455-471. - Y. Saad.
Preconditioned Krylov subspace methods for the numerical solution of
Markov chains.
In W. J. Stewart (Ed.),
*Computations with Markov Chains: Proceedings of the Second International Workshop on the Numerical Solution of Markov Chains*, Kluwer, Boston (1995), 49-64. - G. W. Stewart, W. J. Stewart and D. F. McAllister.
A two-stage iteration for solving nearly completely decomposable Markov
chains.
In G. H. Golub, A. Greenbaum, and M. Luskin, eds.,
*The IMA Volumes in Mathematics and its Applications 60: Recent Advances in Iterative Methods*, Springer-Verlag, New York (1994) 201-216. - W. J. Stewart.
*MARCA*: Markov Chain Analyzer. A software package for Markov modelling. In W. J. Stewart (Ed.),*Numerical Solution of Markov Chains*, M. Dekker, Inc., NY (1991), 37-62. - W. J. Stewart.
*Marca models: a database of Markov chain models*. http://www.csc.ncsu.edu/faculty/WStewart/MARCA_Models/MARCA_Models.html - W. J. Stewart and W. Wu.
Numerical experiments with iteration and aggregation for Markov chains.
*ORSA J. Comput.*, 4, 336-350, 1992.