A Tensor Sum Preconditioner for Stochastic Automata Networks

Stochastic automata networks (SANs) have gained great interest within the performance–modeling community because of their natural ability to capture parallel and distributed activities. SANs and the related concept of stochastic process algebra are advantageous because they keep the transition matrix in a compact form called the SAN descriptor. Several iterative and projection methods have been tested for SANs. Some preconditioners for SANs have been developed to speed up the convergence. Recently, Langville and Stewart (2004) proposed the nearest Kronecker product (NKP) preconditioner for SANs with great success. Encouraged by their work, we propose a new preconditioning method, called the tensor sum preconditioner (TSP), which uses a tensor sum preconditioner rather than a Kronecker product preconditioner. In TSP, we take into account as much as possible the effect of synchronization using term grouping, factorizations, and approximation techniques. We conducted an experimental study to compare our TSP with the NKP preconditioner, and the results show that TSP outperformed NKP on both the number of iterations and the execution time.