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

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

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.