Iterative methods based on splittings for stochastic automata networks

被引:28
作者
Uysal, E [1 ]
Dayar, T [1 ]
机构
[1] Bilkent Univ, Dept Comp Engn & Informat Sci, TR-06533 Bilkent, Turkey
关键词
Markov processes; stochastic automata networks; tensor algebra; splittings; block methods;
D O I
10.1016/S0377-2217(97)00215-4
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper presents iterative methods based on splittings (Jacobi, Gauss-Seidel, Successive Over Relaxation) and their block versions for Stochastic Automata Networks (SANs). These methods prove to be better than the power method that has been used to solve SANs until recently. With the help of three examples we show that the time it takes to solve a system modeled as a SAN is still substantial and it does not seem to be possible to solve systems with tens of millions of states on standard desktop workstations with the current state of technology. However, the SAN methodology enables one to solve much larger models than those could be solved by explicitly storing the global generator in the core of a target architecture especially if the generator is reasonably dense. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:166 / 186
页数:21
相关论文
共 12 条
[1]  
BENZI M, 1995, PARALLEL ALGORITHMS, V6, P25
[2]   KRONECKER PRODUCTS AND SHUFFLE ALGEBRA [J].
DAVIO, M .
IEEE TRANSACTIONS ON COMPUTERS, 1981, 30 (02) :116-125
[3]  
DAYAR T, 1997, TR97198 CESDIS NASA
[4]  
FERNANDES P, 2935 INRIA
[5]  
FERNANDES P, 1996, 4 PROC ALG PERF MOD
[6]   An efficient two-stage iterative method for the steady-state analysis of Markov regenerative stochastic Petri net models [J].
Malhis, LM ;
Sanders, WH .
PERFORMANCE EVALUATION, 1996, 27-8 :583-601
[7]   STOCHASTIC AUTOMATA NETWORK FOR MODELING PARALLEL SYSTEMS [J].
PLATEAU, B ;
ATIF, K .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1991, 17 (10) :1093-1108
[8]   A METHODOLOGY FOR SOLVING MARKOV-MODELS OF PARALLEL SYSTEMS [J].
PLATEAU, B ;
FOURNEAU, JM .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1991, 12 (04) :370-387
[9]  
Plateau B., 1988, MODELING TECHNIQUES, P291
[10]  
PLATEAU B, 1985, P 1985 ACM SIGMETRIC, P147