Theory and Applications of Parallel Sparse Vector Methods (Minority Research Initiation)

并行稀疏向量方法的理论与应用（少数研究发起）

• 批准号: 8915357
• 负责人: Ramon Betancourt
• 金额: $ 11.9万
• 依托单位: San Diego State University Foundation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1990
• 资助国家: 美国
• 起止时间: 1990-01-01 至 1993-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8915357&HistoricalAwards=false
• 关键词: Theory; Applications; Parallel; Sparse; Vector

The central focus of this work is to develop a computational theory of numerical techniques for parallel processing and to apply state of the art computing machinery and methods to large systems problems. More specific objectives are to develop and expand the theory of sparse vector methods and factorization paths to the design of parallel algorithms for matrix operations including applications to problems in large system analysis using supercomputer technology. There are many instances where these algorithms might represent dramatic improvements over present techniques: three immediate appplications of the parallel sparse vector methods are parallel triangular factorization, inversion, and partition of matrices. A graph-theoretic analysis of the factorization path graph has not yet been accomplished and it is essential to the understanding of these methods. It is also fundamental for efficient conventional and parallel sparse vector operations to have effective ordering procedures. New methods are proposed in this research. The methods proposed will be tested on the particular problem of power systems using supercomputers. The essential problem that arises with vector computers is matching the corresponding matrix elements from source and target rows when performing operations using sparse vector techniques. This work elaborates on the earlier proposed approaches Scatter- Gather and Explicit-Enumeration and brings out their relative advantages. Arguments are given for the unification of both techniques in an efficient sparse solver and it is expected that an Overlap-Scatter sparse matrix representation will be used to achieve this goal. This research relates to the statistical properties of parallel sparse vector methods in detail. This includes the computational complexity of conventional and parallel sparse vector applications in matrix triangular factorization, matrix inversion, refactorization, partition, network reduction, state estimation and Hessian optimization algorithms, as well as the computational complexity of ordering schemes. The techniques of parallel sparse vector methods algorithms are completely general and due to the significant savings in time and space the methods have many potential applications in other studies. The expected result of this research is powerful new parallel methods for a variety of large matrix problems.

这项工作的中心重点是制定一个 并行数值技术计算理论 处理和应用最先进的计算技术 解决大系统问题的方法和手段。 更 具体目标是发展和扩大理论 的稀疏向量方法和因式分解路径， 矩阵运算的并行算法设计 包括应用于大系统中的问题 利用超级计算机技术进行分析。 有 在很多情况下，这些算法可能代表 对现有技术的巨大改进：三个 并行稀疏向量的直接应用 方法是并行三角分解，反演， 和矩阵的划分。 的图论分析 因式分解路径图还没有被 这是一个很好的理解， 这些方法。 这也是高效的基础 传统的和并行的稀疏向量运算， 有有效的订购程序。 新方法 在这项研究中提出。 建议的方法将是 测试电力系统的特殊问题， 超级计算机 出现的主要问题是， 向量计算机正在匹配相应的矩阵 元素时， 使用稀疏向量技术的操作。 这项工作 详细阐述了先前提出的方法分散- 收集和显式枚举，并带出他们的 相对优势。 参数是为 在一个有效的稀疏求解器中统一这两种技术 并且可以预期重叠散射稀疏矩阵 我们将利用代表性来实现这一目标。 这 研究涉及并行的统计特性， 稀疏向量方法的详细介绍。 这包括 传统和并行的计算复杂度 稀疏向量在三角矩阵中的应用 分解，矩阵求逆，重构，分割， 网络约简、状态估计和Hessian 优化算法，以及计算 排序方案的复杂性。 的技术 并行稀疏向量法算法是完全 一般而言，由于节省了大量时间， 空间的方法有许多潜在的应用， 其他研究。 这项研究的预期结果是 强大的新的并行方法，为各种大型 矩阵问题