Kronecker product approximate preconditioner for SANs

Many very large Markov chains can be modelled efficiently as stochastic automata networks (SANs). A SAN is composed of individual automata which, for the most part, act independently, requiring only Q of the underlying Markov chain compactly infrequent interaction. SAN's represent the generator matrix as the sum of Kronecker products of smaller matrices. Thus, storage savings are immediate. The benefit of a SAN's compact representation, known as the descriptor, is often outweighed by its tendency to make analysis of the underlying Markov chain tough. While iterative or projections methods have been used to solve the system piQ=0, the time until these methods converge to the stationary solution pi is still unsatisfactory. SAN's compact representation has made the next logical research step of preconditioning thorny. Several preconditioners for SANs have been proposed and tested, Yet each has enjoyed little or no success. Encouraged by the recent Success of approximate inverses as preconditioners, we have explored their potential as SAN preconditioners. One particularly relevant finding on approximate inverse preconditioning is the nearest Kronecker product approximation discovered by Pitsianis and Van Loan. In this paper, we extend the nearest Kronecker product technique to approximate the 0 matrix for an SAN with a Kronecker product, A(1)circle timesA(2)circle times(...)circle timesA(N). Then, we take M =A(1)(-1)circle timesA(2)(-1)circle timesA(N)(-1) as our SAN NKP preconditioner. Copyright (C) 2004 John Wiley Sons, Ltd.