Mathematical Sciences: Stochastic Matrix Analysis

9403224 Meyer本研究的重点是分析随机矩阵和相关的马尔可夫链概念。讨论了理论和计算两方面的问题。其理论目标是对传统的随机矩阵和马尔可夫链的扰动理论产生重大影响。一个目标是完整地描述敏感马尔可夫链的性质和特征，并建立一个关于随机矩阵的特征系统的清晰而简明的扰动理论。这一扰动理论将被用来更好地理解计算平稳概率的各种多水平算法的收敛和稳定性特性。计算方面涉及与大规模不可约马氏链相关的平稳概率的数值确定，特别是那些几乎不耦合的(由一组松散耦合的子系统组成的系统)。重点是聚合/解聚算法的开发、实现和分析。迭代方法和精确聚合/解聚方法都将与一些混合A/D技术一起考虑。本研究的重点是分析随机矩阵及相关的马尔可夫链概念。马尔可夫链技术构成了一个统一的主题，是各种数学模型的基础，这些模型用于描述、预测和分析大型进化系统的动力学。马尔科夫链模型是工程、经济学、物理科学和社会科学等多个领域的基本数学工具。特别是，在涉及排队模型和网络、电信、计算机性能评估、经济建模和预测、制造系统建模的问题中，分析和计算与大规模马尔可夫链相关的平稳概率是主要关注的问题，并且更一般地，在使用随机模型来理解随时间演变的系统的行为的应用中。这个项目同时强调计算和理论问题，并特别关注几乎不耦合的问题(由一组松散耦合的子系统组成的系统)的分析。具体的研究课题如下：(1)随着时间的推移，许多物理系统最终会稳定到某种稳定状态。如果利用马尔可夫链理论对物理系统进行建模，则系统的稳态性质由一组称为“平稳概率”的概率来表征。因此，分析平稳概率的行为是一个基本问题。本研究的理论部分包括研究平稳概率的稳定性。这项研究的结果应该澄清对有助于被检查的基本物理系统的稳定性(或不稳定性)的机制的理解。(2)本项目的计算方面是开发计算平稳概率的新算法，并开发用于分析此类算法的新方法。在如上所述的实际应用中，所讨论的物理系统通常涉及极大量的组件，但这些组件通常可以被分组为集群，对于这些集群，在任何给定的集群内存在较强的相互作用，但集群之间的相互作用较弱(例如，考虑美国的经济)。这项研究工作致力于分析和计算这类系统的稳定性和稳态性质。从数学上讲，这涉及到计算和分析此类系统的平稳概率。为此，被称为聚集/分解技术的数值算法将被设计成具体地利用这些类型的近非耦合系统的特殊特征。

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.