Stochastic and Numerical Matrix Analysis

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

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.