A Kronecker product approximate preconditioner for SANs

✍ Scribed by Amy N. Langville; William J. Stewart

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 220 KB
• Volume: 11
• Category: Article
• ISSN: 1070-5325
• DOI: 10.1002/nla.344

✦ Synopsis

Abstract

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 infrequent interaction. SANs represent the generator matrix Q of the underlying Markov chain compactly 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 π__Q__=0, the time until these methods converge to the stationary solution π 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 Q matrix for an SAN with a Kronecker product, A~1~ ⊗ A~2~ ⊗…⊗ A~N~. Then, we take M = A ⊗ A ⊗…⊗ A as our SAN NKP preconditioner. Copyright © 2004 John Wiley & Sons, Ltd.