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

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

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.