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

TUGRUL DAYAR

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:

  1. 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.
  2. T. Dayar. Permuting Markov chains to nearly completely decomposable normal form, SIAM J. Matrix Anal. Appl., submitted for publication.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. I. Marek and P. Mayer. Convergence theory of an aggregation/disaggregation iteration method. J. Comp. Appl. Math., 62, unassigned, 1997.
  9. C. D. Meyer. Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems. SIAM Rev., 31, 240-272, 1989.
  10. 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.
  11. J. O'Neil and D. B. Szyld. A block ordering method for sparse matrices. SIAM J. Sci. Stat. Comput., 11, 811-823, 1990.
  12. B. Philippe, Y. Saad, and W. J. Stewart. Numerical methods in Markov chain modelling. Opns. Res., 40, 1156-1179, 1992.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. W. J. Stewart. Marca models: a database of Markov chain models. http://www.csc.ncsu.edu/faculty/WStewart/MARCA_Models/MARCA_Models.html
  18. W. J. Stewart and W. Wu. Numerical experiments with iteration and aggregation for Markov chains. ORSA J. Comput., 4, 336-350, 1992.