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

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

• 批准号: 1637566
• 负责人: Yang Peng
• 金额: $ 26.67万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637566&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倍的系统上在几秒钟内工作。对于上面提到的应用程序，求解器可能在一次运行中被调用100次或1000次。因此，这样的求解器需要满足几个重要的要求：1)它必须足够健壮，在这些运行之间不需要人为干预；2)必须足够快，能在合理的时间内完成所有工作。3)它必须能够处理应用中出现的非常不同的方程组。这个项目的目的是桥梁的理论和实践方面的设计有效的和鲁棒的求解线性系统的图拉普拉斯。pi计划开发具有良好实际性能以及在最坏情况下可证明的保证的代码包。这样做要求他们解决数值分析、组合学、高性能计算和数据结构中出现的一系列问题。他们计划解决现有的用于解决图拉普拉斯线性系统的软件包的缺点，特别是它们在存在广泛变化的边权时的鲁棒性。解决这个问题对于将这些求解器整合到优化算法（如迭代最小二乘、镜像下降和内点法）中的理论和实践之间的桥梁至关重要。具体而言，他们将从高性能计算的角度研究各种理论算法工具，重点关注数据结构、高性能计算、数值分析、科学计算和图论等核心主题。在这些方面的进展有可能为团队和他们将要训练的学生开辟新的研究领域。

项目成果

Faster Graph Embeddings via Coarsening

• 发表时间: 2020-07
• 作者: Matthew Fahrbach;Gramoz Goranci;Richard Peng;Sushant Sachdeva;Chi Wang-

Hardness Results for Structured Linear Systems

结构化线性系统的硬度结果

• DOI: 10.1109/focs.2017.69
• 发表时间: 2017
• 期刊: 58th IEEE Annual Symposium on Foundations of Computer Science,FOCS 2017
• 作者: Kyng, Rasmus;Zhang, Peng
• 通讯作者: Zhang, Peng

Incomplete nested dissection

不完整的嵌套解剖

• DOI: 10.1145/3188745.3188960
• 发表时间: 2018
• 期刊: STOC 2018
• 作者: Kyng, Rasmus;Peng, Richard;Schwieterman, Robert;Zhang, Peng
• 通讯作者: Zhang, Peng

Current Flow Group Closeness Centrality for Complex Networks?

• DOI: 10.1145/3308558.3313490
• 发表时间: 2018-02
• 期刊: The World Wide Web Conference
• 作者: Huan Li;Richard Peng;Liren Shan;Yuhao Yi;Zhongzhi Zhang

Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity

最佳离线动态 2、3 边/顶点连接

• 发表时间: 2019
• 期刊: Proceedings
• 作者: Peng, Richard;Sandlund, Bryce;Sleator, Daniel D
• 通讯作者: Sleator, Daniel D