AF: Medium: Collaborative research: Advanced algorithms and high-performance software for large scale eigenvalue problems

从物理学、化学、计算机科学到经济学和统计学等领域的科学家和工程师都非常关注矩阵的“特征值”和“特征向量”的计算。它们是抗震结构振动研究、固态物理能量计算以及网络搜索结果排序的核心。尽管在过去的几十年里，大特征值问题的求解方法取得了巨大的进步，但在处理新一代问题时，当前最先进的方法仍然令人不满意，这些问题需要数以万计的特征向量来处理矩阵，这些矩阵的大小可以达到数千万。近年来出现了一类新的技术，可以通过部分计算大矩阵的特征对。在这些方法中，频谱的“窗口”或“切片”可以彼此独立地计算，并且不再需要在不同切片中特征向量之间的正交化。当要计算的特征对数量非常大时，这种分而治之的方法变得强制性，因为正交化非常大的基是禁止的。由此产生的内特征值问题出现在许多其他情况下，现在被线性代数界认为是最具挑战性的数值问题之一，处理它们的解决方法仍然滞后。本计画的目标是推进内部特征值问题的解方法的最新状态。该项目的主要推力是开发基于Krylov或块Krylov投影技术和复杂有理滤波器相结合的新算法。本研究的起点是FEAST方法。这个项目在几个领域解决了许多有趣的问题，从解决特征值问题的方法开始，到设计合理过滤函数的近似理论问题，并以有效的并行实现结束。我们还将考虑基于域分解框架的方法来处理矩阵（或广义情况下的矩阵对）是分布的常见情况。这个项目的更广泛的影响突出了对培训、传播新的高效软件以及在特定应用中使用软件副产品的影响。在这个项目下开发的所有通用代码都将被免费分发到公共领域。该项目将对研究生和本科生的培训产生影响，这对学术界、工业界和政府实验室的需求至关重要。

Scientists and engineers in areas ranging from physics, chemistry, computer science, to economics, and statistics focus considerable attention on computing "eigenvalues" and "eigenvectors" of matrices. They are central to the study of vibrations when building earthquake-resistant structures, to energy computation in solid-state physics, and to ranking web search results. In spite of the enormous progress that has been made in the last few decades in solution methods for large eigenvalue problems, the current state-of-the-art methods remains unsatisfactory when dealing with the new generation of problems that need tens of thousands of eigenvectors for matrices that can have sizes in the tens of millions.In recent years a new class of techniques has emerged that can compute wanted eigenpairs of large matrices by parts. In these methods, 'windows' or 'slices' of the spectrum can be computed independently of one another and orthogonalization between eigenvectors in different slices is no longer necessary. When the number of eigenpairs to be computed is very large this divide-and-conquer approach becomes mandatory because orthogonalizing very large bases is prohibitive. The resulting interior eigenvalue problems arise in a number of other situations and are now considered by the linear algebra community to be among the most challenging numerical problems to solve, and solution methods for handling them are still lagging.The goal of this project is to advance the state of the art in solution methods for interior eigenvalue problems. The main thrust of the project is the development of novel algorithms based on a combination of Krylov or block-Krylov projection techniques and complex rational filters. A starting point in this investigation is the FEAST approach. This project addresses many interesting questions in several areas, starting with methodologies for solving eigenvalue problems, to approximation theory questions for designing rational filter functions, and ending with effective parallel implementations. Methods based on a domain decomposition framework will also be considered to deal with the common situation where the matrix (or pair of matrices in the generalized case) is (are) distributed.The broader impacts of this project highlight the impact on training, the dissemination of new efficient software, and the use of the software by-products in specific applications. All general-purpose codes that are developed under this project will be freely distributed into the public domain. This project will have an impact on the training of graduate and undergraduate students in a field that is vital to the needs of academia, industry, and government laboratories.