Innovative Sparse Matrix Algorithms

创新的稀疏矩阵算法

• 批准号: 9803599
• 负责人: Timothy Davis
• 金额: $ 19.27万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-08-01 至 2002-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9803599&HistoricalAwards=false
• 关键词: Innovative; Sparse; Matrix; Algorithms

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.

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