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

AF：中：协作研究：大规模特征值问题的先进算法和高性能软件

• 批准号: 1505970
• 负责人: Yousef Saad
• 金额: $ 36.07万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-15 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1505970&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; research; Advanced

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.

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