Circulant approximation for preconditioning in stochastic automata networks

Stochastic Automata Networks (SANs) are widely used in modeling practical s ystems such as queueing systems, communication systems, and manufacturing s ystems. For the performance analysis purposes, one needs to calculate the s teady-state distributions of SANs. Usually, the steady-state distributions have no close form solutions and cannot be obtained efficiently by direct m ethods such as LU decomposition due to the huge size of the generator matri ces. An efficient numerical method should make use of the tensor structure of SANs' generator matrices. The generalised Conjugate Gradient (CG) method s are possible choices though their convergence rates are slow in general. To speed up the convergence rate, preconditioned CG methods are considered in this paper. In particular, circulant based preconditioners for the SANs are constructed. The preconditioners presented in this paper are easy to co nstruct and can be inverted efficiently. Numerical examples of practical SA Ns are also given to illustrate the fast convergence rate of the method. (C ) 2000 Elsevier Science Ltd. All rights reserved.