A new parallel block aggregated algorithm for solving Markov chains

被引:0
作者
Abderezak Touzene
机构
[1] Sultan Qaboos University,Computer Science Department
来源
The Journal of Supercomputing | 2012年 / 62卷
关键词
Performance evaluation; Markov chains; Parallel block methods;
D O I
暂无
中图分类号
学科分类号
摘要
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.
引用
收藏
页码:573 / 587
页数:14
相关论文
共 28 条
[1]  
Saad Y(1981)Krylov subspace methods for solving asymmetric linear systems Math Comput 37 105-126
[2]  
Benzi M(2002)A parallel solver for large-scale Markov chains Appl Numer Math 41 135-153
[3]  
Tuma M(2000)Comparison of partitioning techniques for two-level iterative methods on large, sparse Markov chains SIAM J Sci Comput 21 1691-1705
[4]  
Dayar T(1994)On the use of two QMR algorithms for solving singular systems and applications to Markov chain modelling Numer Linear Algebra Appl 1 403-420
[5]  
Stewart WJ(1992)Numerical methods in Markov chain modeling Oper Res 40 1156-1179
[6]  
Freund RW(1984)Iterative Methods for computing stationary distributions of nearly completely decomposable Markov chains SIAM J Algebr Discrete Math 5 164-186
[7]  
Hochbruck M(1985)Iterative aggregation/disaggregation techniques for nearly uncoupled Markov chains J Assoc Comput Mach 32 702-719
[8]  
Philippe B(1961)Aggregation of variables in dynamic systems Econometrica 29 111-138
[9]  
Saad Y(1992)Numerical experiments with iteration and aggregation for Markov chains ORSA J Comput 4 336-350
[10]  
Stewart WJ(1984)Bounds for the positive eigenvectors of nonnegative matrices and their approximation by decomposition J Assoc Comput Mach 31 804-825