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

Overview: Computations of eigenvalues of large matrices arise in a wide range of applications. Large scale problems are often inherently ill-conditioned. Then, the smaller eigenvalues computed in a floating point arithmetic by existing algorithms may have a low or even no accuracy if the matrix is extremely ill-conditioned. The main objective of this proposal 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 study various discretization schemes and derive suitable structured preconditioners to accurately compute smaller eigenvalues of biharmonic differential operators. Intellectual Merit : 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, our proposed works will open a new direction of research in large scale matrix computations where the numerical accuracy issue can be tackled in a widely applicable setting. New methods proposed to be developed will allow computations of eigenvalues of some broad classes of matrices at an accuracy that have previously been considered not possible. Broader Impacts : The results from the proposed research are expected to impact a large variety of applications that use the biharmonic operators in their modeling. Among them are traditionally the studies of rigid elastic materials such as beams, plates, or solids, but more recently, they also include constructions of multivariate splines, geometric modeling and computer graphics. A discrete version of biharmonic operators has found applications in circuits, image processing, mesh deformation, and manifold learning. With the discretized biharmonic operators easily becoming extremely ill-conditioned, our proposed algorithms will resolve the numerical accuracy issues that may present a significant challenge to the existing algorithms for these applications. It is also worth pointing out that loss of accuracy and ill-conditioning may be a not very well-understood issue outside of the numerical analysis community. Thus, the proposed research activities on biharmonic operators may also increase awareness on this potential problem among researchers in these applications.