Innovative Sparse Matrix Algorithms

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

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.