Innovative Sparse Matrix Algorithms

9803599戴维斯解决科学和工程中的计算问题通常涉及求解稀疏线性方程组。在这项研究中，Davis和Hager专注于直接求解技术和以下研究途径：(1)数值更新和更新方法，(2)减少填充的排序方法，包括强大的优化方法，以及(3)并行非对称因式分解算法。分析方程组中微小变化的影响的问题出现在广泛的应用中，包括最优化、有限元问题、偏微分方程组和统计学等等。将开发稀疏技术，以同时考虑方程的稀疏模式和系统变化的增量性质。稀疏案件虽然早已被认为是一个重要的问题，但并没有得到充分发展。在开发一种将在广泛的应用中有效的算法时，将解决的一些重要特征包括多个等级更新和降级、矩阵重新排序和重构、密集矩阵核的使用以及矩阵顺序的改变。当线性系统的系数矩阵具有矩阵的特殊但重要的形式乘以其转置时，将发展不需要显式形成矩阵乘积的填充缩减排序技术。这种结构出现在QR分解、稀疏部分旋转方法、内点方法、线性规划的对偶有效集方法和外积稀疏LU分解方法中。此外，还将开发一种不同的旋转策略，使用最优化理论来解决参数化二次规划问题。当该参数为1时，该策略生成最小度方案；将该参数设置为矩阵维度的一半会生成全局嵌套解剖类型策略。由此，得到了局部贪婪策略和全局策略之间的连续体。当旋转问题以这种方式被重塑为优化问题时，可以使用强大的优化算法和分析工具来确定最优枢轴(在约束意义上)以及近似最优。对于大型稀疏非对称矩阵，将发展一种并行、分布式存储、非对称模式多前沿分解方法。其基本思想是在非对称稀疏矩阵因式分解产生的有向图或二部图上使用图划分技术。图的分离分量的因式分解将由粗分隔子树指导，并且基于密集的矩阵核。粗分隔符树中的每个节点将由单个处理器分解。

9803599DavisSolving computational problems in science and engineering often involves solving sparse linear systems of equations. In this research, Davis and Hager focus on direct solution techniques, and the following avenues of research: (1) numerical update and downdate methods, (2) ordering methods for reducing fill-in, including a powerful optimization approach, and (3) parallel unsymmetric factorization algorithms.The problem of analyzing the effect of small changes in a system of equations arises in a wide range of applications, including optimization, finite-element problems, partial differential equations, and statistics, to name a few. Sparse techniques will be developed to take into account both the sparsity pattern of the equations and the incremental nature of the system change. Although long recognized as an important problem, the sparse case has not been fully developed. In developing an algorithm that will be effective in a wide range of applications, some of the important features that will be addressed include multiple rank updates and downdates, matrix reordering and refactorization, the use of dense matrix kernels, and changes in matrix order. When the coefficient matrix of a linear system has the special, but important, form of a matrix times its transpose, techniques for fill-reducing orderings will be developed that do not require the explicit formation of the matrix product. This structure arises in QR factorization, in sparse partial pivoting methods, in interior point methods, in a dual active set approach for linear programming, and in outer-product sparse LU factorization methods. In addition, a different pivoting strategy will be developed that uses optimization theory to solve a parameterized quadratic programming problem. When the parameter is 1, this strategy yields the minimum degree scheme; setting the parameter to half the matrix dimension yields global nested dissection type strategies. Hence, a continuum between local greedy and global strategies is obtained. When the pivoting problem is recast in this way as an optimization problem, powerful optimization algorithms and analytical tools can be used to determine both optimal pivots (in a constrained sense) as well as approximate optima. For large, sparse unsymmetric matrices, a parallel, distributed-memory, unsymmetric-pattern multifrontal factorization method will be developed. The basic idea is to use graph partitioning techniques on the directed or bipartite graphs arising from the factorization of unsymmetric sparse matrices. Factorization of the separated components of the graph will be guided by a coarse separator tree, and be based on dense matrix kernels. Each node in the coarse separator tree will be factorized by a single processor.