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

这项工作的中心焦点是发展并行处理的数值技术的计算理论，并将最先进的计算机器和方法应用于大型系统问题。更具体的目标是发展和扩展稀疏向量方法和因式分解的理论，以设计用于矩阵运算的并行算法，包括应用于使用超级计算机技术的大型系统分析中的问题。在许多情况下，这些算法可能代表着对现有技术的显著改进：并行稀疏向量方法的三个直接应用是并行三角分解、求逆和矩阵划分。对因式分解路图的图论分析还没有完成，这对于理解这些方法是必不可少的。对于高效的常规和并行稀疏向量运算来说，具有有效的排序过程也是基本的。本研究提出了新的研究方法。所提出的方法将在使用超级计算机的电力系统的特定问题上进行测试。向量计算机产生的基本问题是，当使用稀疏向量技术执行运算时，匹配来自源行和目标行的对应矩阵元素。该工作详细阐述了早期提出的分散聚集和显式枚举法，并展示了它们的相对优势。论证了在有效的稀疏求解器中这两种技术的统一，预计将使用重叠-散射稀疏矩阵表示来实现这一目标。本研究对并行稀疏向量法的统计性质进行了详细的研究。这包括传统和并行稀疏向量在矩阵三角分解、矩阵求逆、重构、划分、网络约简、状态估计和海森优化算法中的计算复杂性，以及排序方案的计算复杂性。并行稀疏向量法的技术是完全通用的，并且由于在时间和空间上的显着节省，该方法在其他研究中有许多潜在的应用。这项研究的预期结果是针对各种大型矩阵问题的强大的新的并行方法。

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.