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.

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