Parallel Implementation of the GTH Algorithm for Markov Chains

David M. Cohen, Daniel P. Heyman, Asya Rabinovitch and Danit Brown
Additional contact information
David M. Cohen: Bellcore
Daniel P. Heyman: Bellcore
Asya Rabinovitch: Bellcore
Danit Brown: Bellcore

Chapter 35 in Computations with Markov Chains, 1995, pp 594-596 from Springer

Abstract: Extended Abstract We are concerned with computing the steady-state distribution it of an finite irreducible Markov chain with transition matrix P. We will use the GTH [1]algorithm which has excellent numerical properties which have been demonstrated empirically[2] and mathematically [3] We have at our disposal workstations and a massively parallel computer; we want to see how execution times on the latter compare to execution times on the former. Embedded in this endeavor is an exploration of how to harness the massively parallel computer to work on the GTH algorithm. Our main conclusions are: Our massively parallel computer can solve a problem with one thousand states one hundred times as fast as a serial computer. Extrapolation of our experience using one-eighth of the available memory indicates that for a problem with eleven thousand states,the serial machine would require 104 as much time as the parallel machine Having enough memory to store the transition matrix is the limiting factor for our parallel computer. When the transition matrix has the block tridiagonal form, our parallel computer can store many thousands of states (depending on the block size; 16 × 106 states can be stored when the blocks are 2 × 2) and compute the steady-state distribution in a few hours. The 16 × 106 state example can be done in 24 hours.

Keywords: Markov Chain; Execution Time; Transition Matrix; Parallel Computer; Parallel Machine (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_35

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

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

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