A new parallel block aggregated algorithm for solving Markov chains

Abderezak Touzene*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


In this paper, we propose a new scalable parallel block aggregated iterative method (PBA) for computing the stationary distribution of a Markov chain. The PBA technique is based on aggregation of groups (block) of Markov chain states. Scalability of the PBA algorithm depends on varying the number of blocks and their size, assigned to each processor. PBA solves the aggregated blocks very efficiently using a modified LU factorization technique. Some Markov chains have been tested to compare the performance of PBA algorithm with other block techniques such as parallel block Jacobi and block Gauss-Seidel. In all the tested models PBA outperforms the other parallel block methods.

Original languageEnglish
Pages (from-to)573-587
Number of pages15
JournalJournal of Supercomputing
Issue number1
Publication statusPublished - Oct 2012


  • Markov chains
  • Parallel block methods
  • Performance evaluation

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'A new parallel block aggregated algorithm for solving Markov chains'. Together they form a unique fingerprint.

Cite this