Anzeige
Erschienen in:
01.01.2014
A new parallel algorithm for solving large-scale Markov chains
Erschienen in: The Journal of Supercomputing | Ausgabe 1/2014
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper, we propose a new parallel sparse iterative method (PPSIA) for computing the stationary distribution of large-scale Markov chains. The PPSIA method is based on Markov chain state isolation and aggregation techniques. The parallel method conserves as much as possible the benefits of aggregation, and Gauss–Seidel effects contained in the sequential algorithm (SIA) using a pipelined technique. Both SIA and PPSIA exploit sparse matrix representation in order to solve large-scale Markov chains. Some Markov chains have been tested to compare the performance of SIA, PPSIA algorithms with other techniques such as the power method, and the generalized minimal residual GMRES method. In all the tested models, PPSIA outperforms the other methods and shows a super-linear speed-up.