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.