9403224 Meyer This research focuses on the analysis of stochastic matrices and associated Markov chains concepts. Both theoretical and computational issues are addressed. The theoretical objective is to make a significant impact on the traditional perturbation theory for stochastic matrices and Markov chains. One goal is to completely describe the nature and characteristic features of sensitive Markov chains and to build a clear and concise theory of perturbations in the eigensystems of stochastic matrices. This perturbation theory will be used to better understand the convergence and stability properties of a variety of multilevel algorithms for computing stationary probabilities. The computational aspect is concerned with the numerical determination of stationary probabilities associated with large-scale irreducible Markov chains with special emphasis on those which are nearly uncoupled (systems comprised of a collection of loosely coupled subsystems). The focus is on the development, implementation, and analysis of aggregation/disaggregation algorithms. Both iterative and exact aggregation/disaggregation methods are to be considered along with some hybrid A/D techniques. This research focuses on the analysis of stochastic matrices and associated Markov chains concepts. Markov chain techniques constitute a unifying theme and are the basis for an extremely wide variety of mathematical models which are used to describe, predict, and analyze the dynamics of large evolutionary systems. Markov chain models are fundamental mathematical tools in areas as diverse as engineering, economics, physical science, and social science. In particular, analyzing and computing stationary probabilities associated with large scale Markov chains is a primary concern in problems involving queueing models and networks, telecommunications, computer performance evaluation, economic modeling and forecasting, manufacturing systems modeling, and more generally in applications where stochastic models are used to understand the behavior of systems that evolve with time. This project emphasizes both computational and theoretical issues, and special attention is devoted to the analysis of nearly uncoupled problems (systems comprised of a collection of loosely coupled subsystems). The following specific research topics are to be investigated: (1) As they evolve with time, many physical systems eventually settle down into some sort of steady state. If the physical system is modeled by utilizing the theory of Markov chains, then the steady state nature of the system is characterized by a set of probabilities called "stationary probabilities." Consequently, analyzing the behavior of the stationary probabilities is a fundamental issue. The theoretical component of this research involves studying the stability properties of stationary probabilities. The results of this research should clarify the understanding of the mechanisms which contribute to either the stability (or instability) of the underlying physical system being examined. (2) The computational facet of this project is to develop new algorithms for computing stationary probabilities and to develop new methods by means of which such algorithms can be analyzed. In practical applications such as those mentioned above, it is usually the case that the physical system under question involves an extremely large number of components, but these components can often be grouped into clusters for which there is strong interaction within any given cluster but weaker interaction among the clusters themselves (e.g., consider the economy of the United States). This research effort devotes special attention to analyzing and computing the stability and steady state nature of such systems. Mathematically, this involves computing and analyzing the stationary probabilities of such systems. To this end, numerical algorithms known as aggregation/disaggregation techniques will be designed to specifical ly to exploit the special features of these types of nearly uncoupled systems.
