Numerical Methods for large Eigenvalue Problems: Parallizable Fast Algorithms and Inner-Outer iterations

本研究计画包含两个主要部分：大型稠密特征值问题的可平行化快速演算法与大型稀疏特征值问题的不精确/内-外迭代法。 针对大型稠密特征值问题，提出了一种基于有理变换和矩阵平方的可并行快速算法，该算法仅使用矩阵-矩阵乘法和QR分解作为构造块。现在，一个一般的理论是建立包括类的算法开发，并提供指导，推导出新的算法。 将全面研究对于算法的实际实施极其重要的错误分析、鲁棒的放气技术和停止标准。 这部分的研究将导致更深入的理解理论的一类新的广义特征值求解器，并提供一类算法，是真正的高并行效率和鲁棒性。 偏微分方程特征值问题的有效算法是本研究第二部分的主要内容。将为子空间迭代和Lanczos算法开发内外迭代类型的算法，并将所获得的见解应用于PDE情况。它表明，不同的迭代过程中表现出很大的不同，相对于每个内部迭代的精度分布，每个迭代过程需要仔细分析，以找到分配策略，将给最小数量的总内部迭代步骤。本文还对变精度内外迭代法和逐次内外迭代法两种算法作了进一步的分析，并解释了它们的收敛性。PDE特征问题将通过在希尔伯特空间设置中放置诸如Lanczos方法的迭代过程来解决。在每个Lanczos迭代步骤中，矩阵-向量乘法对应于求解边界值 问题的微分算子，不同的离散化将被用来提高效率。 该研究将导致更深入的理解，并提供良好的理论结果的各种迭代过程中解决大型稀疏特征值问题的设置不精确的矩阵向量乘法。它也将提供更有效的算法来解决在许多科学和工程领域出现的大型稀疏特征值问题。

This research project consists of two major parts: parallelizable fast algorithms for large dense eigenproblems and inexact/inner-outer iteration methods for large sparse eigenproblems. Techniques of rational transformation and matrix-squaring for designing parallelizable fast algorithms for large dense eigenproblems have been developed which only use matrix- matrix multiplications and QR decompositions as building blocks. Now a general theory is to be established to encompass the class of algorithms developed and to also provide guidance to the derivation of new algorithms. Error analysis, robust deflation techniques and stopping criteria which are extremely important for the practical implementation of the algorithms will be fully investigated. This part of the research will result in deeper understanding of the theory of a new class of generalized eigensolvers and deliver a class of algorithms that are truly of high parallel efficiency and robustness. Efficient algorithms for eigenproblems of partial differential equations is the major topic of the second part of this research. Inner-outer iteration type of algorithms will be developed for the subspace iteration and Lanczos algorithms and the insight obtained will be applied to the PDE case. It is demonstrated that different iterative processes behave quite differently with respect to the distribution of the accuracy of each inner iteration, and each iterative process needs a careful analysis in order to find the distribution strategy that will give the minimum number of total inner iteration steps. Two algorithms, the variable-accuracy inner-outer iteration method and the successive inner-outer iteration method will be further analyzed and their convergence behavior explained. A PDE eigenproblem will be solved by putting an iterative process such as the Lanczos method in a Hilbert space setting. At each Lanczos iteration step, the matrix-vector multiplication corresponds to solving a boundary value problem for the differential operator, and different discretizations will be used to enhance efficiency. The research will result in deeper understanding and provide sound theoretical results of various iterative processes for solving large sparse eigenproblems in the setting of inexact matrix-vector multiplication. It will also give more efficient algorithms for solving large sparse eigenproblems that arise in many science and engineering areas.