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

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

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.