Stochastic and Numerical Matrix Analysis

随机和数值矩阵分析DMS-9704847卡尔d迈耶技术描述。本项目关注应用数学中三个计算领域的问题。1. 第一组问题涉及随机矩阵特征系统和相关马尔可夫链模型的分析和计算。特别注意的是几乎不耦合的马尔可夫链。这些是由松散耦合子系统集合组成的大型系统，目的是用聚合/分解（或A/D）算法分析和计算这些系统的稳定性和稳态性质。具体目标是通过使用遍历系数代替传统的基于范数的边界，为分析（a /D）误差提供更具体的基础；更好地了解多电平数模处理的错误性质，从而促进多电平数模算法的发展和性能的改进；并开发了解随机矩阵特征系统耦合的新技术。2. 第二组问题集中于直接投影和隐式因式分解算法的发展和分析，这些算法用于求解在偏微分方程和常微分方程数值解中遇到的线性代数方程的大型稀疏系统。具体目标是利用隐式分解算法构造显式近似逆预条件，在高性能矢量和并行计算机上利用类共轭梯度方法求解正定系统时获得优势。3. 第三组问题源于制造应用，涉及到在其表面的不同点上描述或测量制造项目的必要性，以便建立一个精确的计算机模型，以便该项目可以通过自动工具设备进行加工。当这些描述或测量在制造过程中使用时，约束由计算机代码自动生成，以考虑复杂的几何形状，确保平滑，并考虑被加工表面的材料可变性。但是这些计算机代码通常会产生许多冗余约束，如何区分必要约束和冗余约束是一个重要的问题。该项目的这一方面致力于开发新的数值算法来进行这种区分。该策略是通过开发新的用于估计矩阵的最小奇异值/向量的保持稀疏的行作用算法来改进目前用于识别冗余的昂贵的秩揭示技术。非技术描述。本项目关注应用数学中三个计算领域的问题。1. 第一组问题涉及随机矩阵和相关马尔可夫链的计算。马尔可夫链模型的理论和应用在工程、经济、物理和社会科学的许多问题中都是一个反复出现的主题。特别是，分析和计算与大规模马尔可夫链相关的稳态概率是排队模型和网络、电信、计算机性能评估、经济建模和预测、制造系统建模等领域的基本问题，更普遍的是，在使用离散模型来理解和分析大型进化系统动态的应用中。这个项目强调计算和理论问题，并特别关注几乎不耦合的问题。这些是由松散耦合子系统的集合组成的大型系统（例如，美国的经济），目的是使用聚合/分解技术来分析和计算这些系统的稳定性和稳态性质。具体目标是提高和扩展聚集/解聚过程中的误差理论，并开发新的聚集/解聚算法来估计近不耦合系统的稳态行为。2. 第二组问题侧重于开发和分析一类新的算法，用于求解线性代数方程组，这些方程组出现在解决工程和物理科学中大规模问题时通常遇到的偏微分方程和常微分方程的数值解中。正在开发的算法是针对高性能多处理器计算机的。第三组问题源于制造应用，涉及到在其表面的不同点上描述或测量制造项目的必要性，以便建立一个精确的计算机模型，以便该项目可以通过自动工具设备进行加工。当这些描述或测量在制造过程中使用时，约束由计算机代码自动生成，以考虑复杂的几何形状，确保平滑，并考虑被加工表面的材料可变性。但是这些计算机代码通常会产生许多冗余约束，如何区分必要约束和冗余约束是一个重要的问题。该项目的这一方面致力于开发新的数值算法来进行这种区分。

STOCHASTIC AND NUMERICAL MATRIX ANALYSIS DMS-9704847 Carl D. Meyer TECHNICAL DESCRIPTION. This project focuses on issues from three computational areas in applied mathematics. 1. The first set of problems concerns the analysis and computation of eigensystems of stochastic matrices and associated Markov chain models. Special attention is devoted to nearly uncoupled Markov chains. These are large systems comprised of collections of loosely coupled subsystems, and the purpose is to analyze and compute the stability and steady state nature of such systems with aggregation/disaggregation (or A/D) algorithms. Specific goals are to provide a more concrete foundation for analyzing (A/D) errors through the use of ergodicity coefficients instead of tradition norm based bounds; to provide a better understanding of the nature of errors in multilevel A/D processes thereby facilitating improvements in the development and performance of multilevel A/D algorithms; and to develop new techniques for uncoupling the eigensystems for stochastic matrices. 2. The second set of problems focuses on the development and analysis of direct projection and implicit factorization algorithms used to solve large sparse systems of linear algebraic equations encountered in the numerical solution of partial and ordinary differential equations. Specific goals are to gain an advantage when solving positive definite systems by means of conjugate gradient-like methods on high-performance vector and parallel computers by utilizing implicit factorization algorithms to construct explicit approximate inverse preconditioners. 3. The third set of problems stems from manufacturing applications involving the necessity to describe or measure a manufactured item at various points on its surface in order to build an accurate computer model so that the item can be machined by automatic tooling devices. When these description s or measurements are used in the manufacturing process, constraints are automatically generated by computer codes to account for complex geometries, to insure smoothness, and to account for material variability in the surfaces being tooled. But these computer codes usually generate many redundant constraints, and it is a significant problem is to distinguish the necessary constraints from the redundant ones. This facet of the project is dedicated to developing new numerical algorithms for making such distinctions. The strategy is to improve on costly rank-revealing techniques currently used to identify redundancies by developing new sparsity-preserving, row-action algorithms for estimating the smallest singular value/vector of a matrix. NON-TECHNICAL DESCRIPTION. This project focuses on issues from three computational areas in applied mathematics. 1. The first set of problems concerns computations involving stochastic matrices and associated Markov chains. The theory and application of Markov chain models is a recurring theme in many problems from engineering, economics, and physical and social science. In particular, analyzing and computing steady-state probabilities associated with large-scale Markov chains is a fundamental concern in areas such as queueing models and networks, telecommunications, computer performance evaluation, economic modeling and forecasting, manufacturing systems modeling, and more generally, in applications where discrete models are used to understand and analyze the dynamics of large evolutionary systems. This project emphasizes computational as well as theoretical issues, and special attention is devoted to nearly uncoupled problems. These are large systems comprised of collections of loosely coupled subsystems (e.g., the economy of the United States), and the purpose is to analyze and compute the stability and stea dy-state nature of such systems with techniques known as aggregation/disaggregation. Specific goals are to sharpen and extend the theory of errors in aggregation/disaggregation processes and to develop new aggregation/disaggregation algorithms for estimating steady-state behavior in nearly uncoupled systems. 2. The second set of problems focuses on the development and analysis of a new class of algorithms for solving systems of linear algebraic equations arising in the numerical solution of partial and ordinary differential equations of the type typically encountered in solving large-scale problems in engineering and physical science. The algorithms under development are aimed at high-performance multiprocessor computers 3. The third set of problems stems from manufacturing applications involving the necessity to describe or measure a manufactured item at various points on its surface in order to build an accurate computer model so that the item can be machined by automatic tooling devices. When these descriptions or measurements are used in the manufacturing process, constraints are automatically generated by computer codes to account for complex geometries, to insure smoothness, and to account for material variability in the surfaces being tooled. But these computer codes usually generate many redundant constraints, and it is a significant problem is to distinguish the necessary constraints from the redundant ones. This facet of the project is dedicated to developing new numerical algorithms for making such distinctions.