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.
