<p>Many very large Markov chains can be modeled efficiently as Stochastic Automata Networks (SANs). A SAN iscomposed of individual automata that, for the most part, act independently, requiring only infrequentinteraction. SANs represent the generator matrix Q of the underlying Markov chain compactly as the sum ofKronecker products of smaller matrices. Thus, storage savings are immediate. The benefit of a SAN's compactrepresentation, known as the descriptor, is often outweighed by its tendency to make analysis of theunderlying 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 hasmade the next logical research step of preconditioning thorny. Several preconditioners for SANs have beenproposed and tested, yet each has enjoyed little or no success. Encouraged by the recent success ofapproximate inverses as preconditioners, we have explored their potential as SAN preconditioners. Onepromising finding on approximate inverse preconditioner is the nearest Kronecker product (NKP) approximationintroduced by Pitsianis and Van Loan. In this dissertation, we approximate Q by the nearest Kronecker productfor 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 ourSAN NKP preconditioner. We show how successful this NKP preconditioner is for SANs by testing it on severalexamples. We also introduce and catalogue some new results about the Kronecker product, an operation which isfundamental to this SAN research.<P>
| Identifer | oai:union.ndltd.org:NCSU/oai:NCSU:etd-20020326-002140 |
| Date | 01 April 2002 |
| Creators | Langville, Amy N. |
| Contributors | William J. Stewart, Dr. Ilse Ipsen, Dr. Carl D. Meyer, Dr. David McAllister |
| Publisher | NCSU |
| Source Sets | North Carolina State University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://www.lib.ncsu.edu/theses/available/etd-20020326-002140 |
| Rights | unrestricted, I hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to NC State University or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report. |
Page generated in 0.0072 seconds