Accurate Preconditioing for Computing Eigenvalues of Large and Extremely Ill-conditioned Matrices

用于计算大型和极病态矩阵特征值的精确预处理

• 批准号: 1620082
• 负责人: Qiang Ye
• 金额: $ 22.5万
• 依托单位: University of Kentucky Research Foundation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1620082&HistoricalAwards=false
• 关键词: Accurate; Preconditioing; Computing; Eigenvalues; Large

Computations of eigenvalues of large matrices arise in a wide range of scientific and engineering applications, including, for example, page ranking of the Google Search Engine. Large scale eigenvalue problems are often inherently ill-conditioned which implies that their eigenvalues differ vastly in magnitude. This poses a significant challenge to the existing eigenvalue algorithms in the sense that smaller eigenvalues computed may have a poor accuracy, caused by roundoff errors in computer arithmetic. This project will develop new algorithms to address this numerical difficulty. The research results will have applications in a variety of problems where extreme ill-conditioning arises. In particular, a notable ill-conditioning problem is the biharmonic differential operator, which has been used in modeling and design of rigid elastic structures such as beams, plates, or solids, in constructions of multivariate splines, as well as in geometric modeling and computer graphics. A discrete version of the biharmonic operator has also found applications in circuits, image processing, mesh deformation, and manifold learning. With the discretized biharmonic operators easily becoming extremely ill-conditioned, this research will resolve the numerical accuracy issues of the existing algorithms for these applications.Computing smaller eigenvalues of large and extremely ill-conditioned matrices is an important and intellectually challenging task. Indeed, the effect of ill-conditioning on accuracy is often regarded as an unsolvable problem that is attributable to the formulation of the eigenvalue problem itself. While recent research results have shown that this may be mitigated by exploring structures of matrices, the main objective of this project is to propose an innovative use of preconditioning as a new general methodology to solve the accuracy issue caused by ill-conditioning. We will develop new methods that combine preconditioning with accurate structured inversion methods to accurately compute smaller eigenvalues of an extremely ill-conditioned matrix. As an application, we will also study various discretization schemes and derive suitable structured preconditioners for biharmonic differential operators.

大型矩阵特征值的计算出现在广泛的科学和工程应用中，包括，例如，谷歌搜索引擎的页面排名。大规模特征值问题通常本质上是病态的，这意味着它们的特征值在大小上差异很大。这对现有的特征值算法提出了重大挑战，因为计算的较小特征值可能具有较差的精度，这是由计算机算术中的舍入误差引起的。该项目将开发新的算法来解决这一数值难题。研究结果将应用于解决出现极端病态的各种问题。特别是，一个值得注意的病态问题是双调和微分算子，它已用于梁、板或实体等刚性弹性结构的建模和设计、多元样条的构造以及几何建模和计算机中图形。双调和算子的离散版本也在电路、图像处理、网格变形和流形学习中得到了应用。由于离散双调和算子很容易变得极其病态，这项研究将解决这些应用中现有算法的数值精度问题。计算大型且极其病态矩阵的较小特征值是一项重要且具有智力挑战性的任务。事实上，病态对准确性的影响通常被认为是一个无法解决的问题，这可归因于特征值问题本身的表述。虽然最近的研究结果表明，可以通过探索矩阵结构来缓解这一问题，但该项目的主要目标是提出预处理的创新用途，作为一种新的通用方法来解决病态引起的精度问题。我们将开发新方法，将预处理与精确的结构化反演方法相结合，以精确计算极端病态矩阵的较小特征值。作为应用，我们还将研究各种离散化方案，并为双调和微分算子导出合适的结构化预处理器。

项目成果

Eigenvalue Normalized Recurrent Neural Networks for Short Term Memory

用于短期记忆的特征值归一化递归神经网络

• DOI: 10.1609/aaai.v34i04.5831
• 发表时间: 2019-11-18
• 作者: Kyle E. Helfrich;Q. Ye
• 通讯作者: Q. Ye

Improving RNA secondary structure prediction via state inference with deep recurrent neural networks

通过深度循环神经网络的状态推断改进 RNA 二级结构预测

• DOI: 10.1515/cmb-2020-0002
• 发表时间: 2019-06-26
• 期刊: Computational and Mathematical Biophysics
• 作者: Devin Willmott;D. Murrugarra;Q. Ye
• 通讯作者: Q. Ye

Complex Unitary Recurrent Neural Networks Using Scaled Cayley Transform

使用缩放凯莱变换的复杂酉循环神经网络

• DOI: 10.1609/aaai.v33i01.33014528
• 发表时间: 2019-07
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Maduranga, Kehelwala D.;Helfrich, Kyle E.;Ye, Qiang
• 通讯作者: Ye, Qiang