Low-rank Diagonally Compensated Matrix Decompositions in the Design of Solvers and Partitioners

科学和工程中的许多问题的计算模拟需要使用黑盒矩阵求解器。可靠的黑盒求解器的发展的主要挑战在于未知的起源，需要解决的问题。该项目将提供一种新的方法来确定问题的性质和根源，然后开发有效的黑盒矩阵工具。这些结果将使研究人员能够使他们的计算模拟器在大规模上更加可行。特别是，制定的问题，如那些从社会和信息网络科学产生的大规模的图表将更成功地处理。这个项目提供了一个统一的步骤，在大规模的稀疏对称正定矩阵，有可能有所需的最佳复杂性，并在实践中是有效的黑盒求解器和预处理器。更具体地说，这个项目提出了使用一般矩阵分解成一个容易可逆的矩阵减去一个低秩对称半正定矩阵的总和。分解为研究提供了几个方向。在稀疏对称正定矩阵的情况下，分解自然地定义了真正的黑盒稀疏矩阵求解器的组件，包括先前研究的支持图预处理器的替代方案，以及代数多重网格（或AMG）方法的自然组件，例如收敛平滑器和用于创建精确粗糙向量空间的工具。此外，该项目提供了新的算法划分（图和有限元网格），这是依赖于给定的矩阵项。例如，如果矩阵表示某些物理现象（如地下流、电磁场、弹性体）的离散模拟，则所得网格划分器将反映下划线的物理过程。该项目更广泛的影响是，其结果有可能使研究人员，包括那些处于离散数学和信息学接口的数值偏微分方程领域之外的研究人员，使他们的模拟在大规模上更加可行。特别是，可以更成功地处理在大规模图表上提出的问题（在科学和社会及信息网络中出现的问题）。通过为该项目开发的（算法）工具提供严格的理论基础，它将有可能在教育和研究方面产生坚实的实践影响。

The computational simulation of many problems in science and engineering requires the use of black-box matrix solvers. The main challenge in the development of reliable black-box solver lies on the unknown origin of the problems that need to be solved. This project will provide a new approach to identify the nature and the origin of the problems and then develop efficient black-box matrix tools. The results will enable researchers to make their computational simulators more feasible at large scale. In particular, problems formulated on large-scale graphs such as those arising from social and information network sciences will be more successfully approached. This project offers a unifying step towards building black-box solvers and preconditioners for sparse symmetric positive definite matrices at large scale that have the potential to have desired optimal complexity and be efficient in practice. More specifically, this project proposes the use of a general matrix decomposition into a sum of an easily invertible matrix minus a sum of low-rank symmetric positive semi-definite matrices. The decomposition offers several directions for research. In the case of sparse symmetric positive definite matrices the decomposition naturally defines components for genuine black-box sparse matrix solvers including alternatives to previously studied support graph preconditioners as well as natural components for algebraic multigrid (or AMG) methods, such as convergent smoothers and tools for creating accurate coarse vector spaces. Also, the project offers new algorithms for partitioning (of graphs and finite element meshes), which are dependent on the given matrix entries. For example, if the matrix represents a discrete analog of some physical phenomenon (such as subsurface flow, electromagnetic field, elastic body), the resulting mesh partitioners will reflect the underlined physical process. The broader impact of the project is that its results can have the potential to enable researchers, including ones outside the area of numerical PDEs that are at the interface of discrete mathematics and informatics, to make their simulations more feasible at large scale. In particular, problems formulated on large-scale graphs (arising in sciences and social and information networks) could be more successfully approached. By providing the (algorithmic) tools with rigorous theoretical foundation developed by the project, it will have the potential for solid impact in practice, both in education and research.