Parallel Sparse Matrix Computations

本项目研究在高性能并行计算机上解决大型稀疏方程组和最小二乘问题中出现的几个问题的算法的设计、实现和分析。稀疏矩阵算法所需的存储器访问的不规则性使得良好的性能很难实现。能够比传统顺序方法更好地并发性的创新算法方法以及利用存储器层次结构的实现对于获得良好的性能是必不可少的。研究了以下问题：(1)在并行计算机上划分数据和计算以及在计算嵌套分解排序时出现的划分问题的代数方法；(2)稀疏矩阵重新排序以最小化的问题及其在计算不完全因式分解中的应用；(3)在并行计算机上求解稀疏三角系统的乘积形式逆方法；(4)在顺序计算机和并行计算机上求解秩亏最小二乘问题。

This project investigates the design, implementation, analysis of algorithms for several problems that arise in the solution of large, sparse systems of equations and least squares problems on high-performance parallel computers. The irregular nature of the memory access required by sparse matrix algorithms makes good performance difficult to achieve. Innovative algorithmic approaches capable of better concurrency than the traditional sequential approaches, and implementations that exploit the memory hierarchy are essential to obtain good performance. The following problems are being investigated: (1) An algebraic approach to the partitioning problem that arises in partitioning data and computation on parallel computers, and in computing nested dissection orderings, (2) The problem of reordering sparse matrices to minimize with applications to computing incomplete factorization (3) The product-form-inverse approach to the solution of sparse triangular systems on parallel computers, (4) The solution of rank-deficient least-squares problems on sequential and parallel computers.