TITLE: Kronecker Operations to Define Large Markov Chains Underlying Structured Representations RESEARCH FELLOW: Tugrul Dayar, Ph.D. HOST: Peter Buchholz, Ph.D. HOST INSTITUTION: Dresden University of Technology, Germany SUPPORT: Alexander von Humboldt Foundation DURATION: 1 September 2002 - 30 June 2003 ABSTRACT: The concept of using Kronecker operations to define large Markov chains (MCs) underlying structured representations appears in compositional Markovian models such as stochastic automata networks (SANs) and different classes of superposed Stochastic Petri Nets (SPNs), or in hierarchical Markovian models. Currently an open research problem is that of devising strong preconditioners to be used with projection methods for MCs underlying structured representations. This project aims at providing effective implementations of block Gauss-Seidel (BGS) and an (adaptive) multilevel method for a sum of Kronecker products. Then it plans on using BGS and the multilevel method as preconditioners in projection methods, such as BiCGStab and TFQMR. Finally, it intends on seeking better orderings of components and states inside components of structured representations so as to enhance the performance of Kronecker based numerical analysis techniques. All improvemenets will be studied existing test cases and new models to be developed from the area of communication systems. KEY WORDS: Kronecker based numerical techniques, Markov chains, multilevel methods, orderings, preconditioners.