A Parallel Block Projection Method of the Cimmino Type for Finite Markov Chains

M. Benzi, F. Sgallari and G. Spaletta
Additional contact information
M. Benzi: Universitá di Bologna, Dipartimento di Matematica
F. Sgallari: Universitá di Bologna, Dipartimento di Matematica
G. Spaletta: Universitá di Bologna, Dipartimento di Matematica

Chapter 5 in Computations with Markov Chains, 1995, pp 65-80 from Springer

Abstract: Abstract A parallel block projection method is used to approximate the stationary vector of a finite Markov chain. Block projection methods are very attractive for solving large chains thanks to their potential for parallel computation and robustness. We show that the block Cimmino method is particularly well-suited if the chain is nearly uncoupled, a condition which is often met in the applications. This is due to the favorable spectral distribution of the iteration matrix, in contrast with more traditional iterative solvers which are known to exhibit poor convergence rates when applied to nearly uncoupled problems. We consider conjugate gradient acceleration, and we experiment with different block partitionings and row reorderings of the rate matrix. The results of numerical experiments on a simple reliability model, carried out on the CRAY T3D massively parallel computer, are discussed. The test results point to the fact that this method is well suited for the parallel solution of nearly uncoupled Markov chains.

Keywords: Markov Chain; Rate Matrix; Nonzero Eigenvalue; Convergence Factor; Finite Markov Chain (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4615-2241-6_5

Ordering information: This item can be ordered from
http://www.springer.com/9781461522416

DOI: 10.1007/978-1-4615-2241-6_5

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().