AitF: Collaborative Research: High Performance Linear System Solvers with Focus on Graph Laplacians

AitF：协作研究：关注图拉普拉斯算子的高性能线性系统求解器

• 批准号: 1637523
• 负责人: Gary Miller
• 金额: $ 26.67万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637523&HistoricalAwards=false
• 关键词: AitF; Collaborative; Research; Performance; Linear

Fast and robust solvers for systems of linear equations are the work horse of many communities in the sciences, engineering, business, and industry. Few pieces of software are so important of all these areas. Recent theoretical progress on efficient solvers for special cases of linear systems, including Symmetric Diagonally Dominant matrices, have sparked a renaissance in faster algorithms for wide classes of optimization problems that have not seen improvements in many years.The main goal of this project is to take the next step to find and implement fast robust solvers that work in seconds on systems that are a factor of 100 to 1000 times larger than is now possible on a modern large workstation. For the applications mentioned above the solver may be called 100s or 1000s times for a single run. As a result, such a solver needs to meet several important requirements: 1) it must be robust enough to not need human intervention between these runs; 2) it must be fast enough to finish all work in a reasonable amount of time. 3) it must be able to handle the very different systems of equations that arise in applications.This project aims to bridge the theoretical and practical aspects of designing efficient and robust solvers for linear systems in graph Laplacians. The PIs plan to develop code packages that have good practical performances as well as provable guarantees in the worst case. Doing so requires them to address a range of issues arising from numerical analysis, combinatorics, high performance computing, and data structures.They plan to address shortcomings of existing packages for solving linear systems in graph Laplacians, specifically their robustness in the presence of widely varying edge weights. Resolving this issue is crucial for bridging the theory and practice of incorporating these solvers in optimization algorithms such as iterative least squares, mirror descent, and interior point methods. Specifically, they will study a variety of theoretical algorithmic tools from the perspective of high performance computing, focusing on topics at the core of data structures, high performance computing, numerical analysis, scientific computing, and graph theory. Progresses on them have the potential of opening up novel lines of investigations on well-studied topics for the team and the students that they will train.

快速和强大的线性方程组解算器是科学、工程、商业和工业中许多社区的工作重点。在所有这些领域中，很少有软件如此重要。在线性系统的特殊情况下，包括对称对角占优矩阵的高效求解器的最新理论进展，引发了更快的算法的复兴，用于多年来没有得到改善的大类优化问题。这个项目的主要目标是下一步寻找并实现快速健壮的求解器，它在几秒钟内就能在比现代大型工作站上可能的系数大100到1000倍的系统上工作。对于上面提到的应用程序，求解器在一次运行中可能被调用100s或1000s次。因此，这样的求解器需要满足几个重要的要求：1)它必须足够健壮，不需要在这些运行之间进行人工干预；2)它必须足够快，以便在合理的时间内完成所有工作。3)它必须能够处理应用中出现的非常不同的方程系统。这个项目的目的是在理论和实践方面架起桥梁，设计高效和健壮的线性系统的拉普拉斯求解器。PI计划开发具有良好实际性能的代码包，并在最坏的情况下提供可证明的保证。要做到这一点，他们需要解决数值分析、组合数学、高性能计算和数据结构所产生的一系列问题。他们计划解决现有图拉普拉斯求解线性系统的软件包的缺点，特别是在边权值变化很大的情况下的健壮性。解决这个问题对于将这些求解器结合到优化算法(如迭代最小二乘法、镜像下降法和内点法)中的理论和实践是至关重要的。具体地说，他们将从高性能计算的角度研究各种理论算法工具，重点关注数据结构、高性能计算、数值分析、科学计算和图论的核心主题。在这些方面的进展有可能为团队和他们将培训的学生开辟关于研究充分的主题的新的调查路线。

项目成果

Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions

• DOI: 10.1109/focs.2018.00042
• 发表时间: 2018-05
• 期刊: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: T. Chu;Yu Gao;Richard Peng;Sushant Sachdeva;Saurabh Sawlani;Junxing Wang

Graph Sketching against Adaptive Adversaries Applied to the Minimum Degree Algorithm

• DOI: 10.1109/focs.2018.00019
• 发表时间: 2018-04
• 期刊: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Matthew Fahrbach;G. Miller;Richard Peng;Saurabh Sawlani;Junxing Wang;Shen Chen Xu