Krylov Multigrid Methods for Eigenvalues and Linear Equations

与矩阵相关的特征值(特征值)在整个科学中都很重要。对于飞机，特征值给出了振动的自然频率，因此特征值的知识可以用来防止破坏性共振。为了类似的目的，对地震区的建筑物计算本征值，并且本征值也被用于广泛的其他环境中，例如在寻找原子和分子的能级时。随着数学模型变得更加精确和复杂，计算越来越大的矩阵的特征值变得必要，这需要增加计算时间。这个项目的计划是利用通过在问题域上放置不同大小的网格而开发的不同大小的矩阵。通过在较小的矩阵上进行大量工作，有可能大幅减少计算费用。本征值的另一个应用是改进线性方程组的收敛。本项目将研究具有较少点的网格的特征值如何有效地加速迭代线性方程解算器在具有多个点的网格上的收敛。这个项目在许多科学领域都有潜在的影响，因为许多科学应用导致偏微分方程组通过基于网格的特征值问题来求解。研究了大型特征值问题和线性方程组的新方法。该方法将多重网格和Krylov迭代相结合，以解决困难问题。常规多重网格方法用于在网格上求解的微分方程组，它们在不同的网格大小中循环。他们为一些问题(如不确定或太不对称)而苦苦挣扎。所提出的方法更稳健，因为它们在规则多重网格失效的情况下是有效的。对于特征值问题，提出了一种在粗网格上计算特征值，在细网格上改进特征值的方法。与标准的Arnoldi方法不同，采用了Arnoldi型方法，它可以接受初始近似特征向量。计划开发和测试这种方法，包括用于多个网格级别。还需要分析，以解释为什么精细网格收敛出人意料地与常规阿诺尔迪网格收敛相匹配。近克里洛夫理论将为此而发展。当存在较小的特征值时，迭代线性方程解算器的收敛速度很慢。该方法利用粗网格的近似特征向量，从本质上去除特征值，提高算法的收敛速度。这种方法可用于包括多重网格预条件在内的预条件系统。有可能极大地改进困难的特征值问题和线性方程的计算。

The characteristic values (eigenvalues) associated with a matrix are important throughout science. For an airplane, eigenvalues give the natural frequencies of vibration, and thus knowledge of eigenvalues can be used to prevent destructive resonance. Eigenvalues are computed for buildings in earthquake zones for similar purposes, and eigenvalues are employed in a wide variety of other contexts as well, for example in finding the energy levels of atoms and molecules. As mathematical models become more accurate and sophisticated, it becomes necessary to compute eigenvalues of ever larger matrices, requiring increasing computational time. The plan for this project is to take advantage of different sizes of matrices that are developed by placing different size grids on the domain of the problem. By doing much of the work on a smaller matrix, there is potential to substantially reduce the computational expense. Another application of eigenvalues is to improve convergence of systems of linear equations. This project will look at how eigenvalues from a grid with fewer points can effectively speed up the convergence for an iterative linear equations solver on a grid with many points. This project has potential impact in many areas of science, since many scientific applications lead to partial differential equations that are solved with grid-based eigenvalue problems.New methods are studied for large eigenvalue problems and systems of linear equations. The methods combine multigrid with Krylov iterations in order to solve difficult problems. Regular multigrid methods are for differential equations that are solved on a grid, and they cycle through different grid sizes. They struggle for some problems (such as indefinite or too nonsymmetric). The proposed methods are more robust in that they can be effective in situations where regular multigrid fails. For eigenvalue problems, a method is proposed that computes eigenvalues on a coarse grid and improves them on the fine grid. An Arnoldi-type method is used that, unlike standard Arnoldi methods, can accept initial approximate eigenvectors. It is planned to develop and test this approach including for multiple grid levels. Also needed is analysis to explain why fine grid convergence unexpectedly matches that of regular Arnoldi. Near-Krylov theory will be developed for this. Iterative linear equations solvers suffer slow convergence when there are small eigenvalues. The plan is to use approximate eigenvectors from the coarse grid to essentially remove eigenvalues and improve the convergence. This approach can be used on preconditioned systems including with multigrid preconditioning. There is potential to very significantly improve computations for difficult eigenvalue problems and linear equations.