Stochastic and Numerical Matrix Analysis

随机和数值矩阵分析

• 批准号: 9704847
• 负责人: Carl Meyer
• 金额: $ 16.9万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-07-15 至 2001-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9704847&HistoricalAwards=false
• 关键词: Stochastic; Numerical; Matrix; Analysis

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.

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