Krylov Multigrid Methods for Eigenvalues and Linear Equations

点击翻译按钮获取中文摘要

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.