Amy N. Langville
PhD Dissertation submitted to the Faculty of the North Carolina State University in partial fulfillment of the requirements for the degree of
PhD
in
Operations Research
Approved
William J. Stewart, Chair
Dr. Ilse Ipsen
Dr. Carl D. Meyer
Dr. David McAllister
March 18, 2002
Raleigh, North Carolina
Abstract
Many very large Markov chains can be modeled efficiently as Stochastic Automata Networks (SANs). A SAN is composed of individual automata that, 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. Although iterative or projection methods have been used to solve the system P Q =0, the convergence to the stationary solution P 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 promising finding on approximate inverse preconditioner is the nearest Kronecker product (NKP) approximation introduced by Pitsianis and Van Loan. In this dissertation, we approximate Q by the nearest Kronecker product for a SAN with a Kronecker product, A1 D A2 D . . . D AN. Then, we take M= A1-1 A2-1 D . . . D AN-1 as our SAN NKP preconditioner. We show how successful this NKP preconditioner is for SANs by testing it on several examples. We also introduce and catalogue some new results about the Kronecker product, an operation which is fundamental to this SAN research.