Research

Inner-outer Iterative Methods for Eigenvalue Problems - Convergence and Preconditioning


Reference:

Freitag, M., 2007. Inner-outer Iterative Methods for Eigenvalue Problems - Convergence and Preconditioning. Thesis (Doctor of Philosophy (PhD)). University of Bath.

Related documents:

[img]
Preview
PDF (thesis.pdf) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (2401kB) | Preview

    Abstract

    Many methods for computing eigenvalues of a large sparse matrix involve shift-invert transformations which require the solution of a shifted linear system at each step. This thesis deals with shift-invert iterative techniques for solving eigenvalue problems where the arising linear systems are solved inexactly using a second iterative technique. This approach leads to an inner-outer type algorithm. We provide convergence results for the outer iterative eigenvalue computation as well as techniques for efficient inner solves. In particular eigenvalue computations using inexact inverse iteration, the Jacobi-Davidson method without subspace expansion and the shift-invert Arnoldi method as a subspace method are investigated in detail. A general convergence result for inexact inverse iteration for the non-Hermitian generalised eigenvalue problem is given, using only minimal assumptions. This convergence result is obtained in two different ways; on the one hand, we use an equivalence result between inexact inverse iteration applied to the generalised eigenproblem and modified Newton's method; on the other hand, a splitting method is used which generalises the idea of orthogonal decomposition. Both approaches also include an analysis for the convergence theory of a version of inexact Jacobi-Davidson method, where equivalences between Newton's method, inverse iteration and the Jacobi-Davidson method are exploited. To improve the efficiency of the inner iterative solves we introduce a new tuning strategy which can be applied to any standard preconditioner. We give a detailed analysis on this new preconditioning idea and show how the number of iterations for the inner iterative method and hence the total number of iterations can be reduced significantly by the application of this tuning strategy. The analysis of the tuned preconditioner is carried out for both Hermitian and non-Hermitian eigenproblems. We show how the preconditioner can be implemented efficiently and illustrate its performance using various numerical examples. An equivalence result between the preconditioned simplified Jacobi-Davidson method and inexact inverse iteration with the tuned preconditioner is given. Finally, we discuss the shift-invert Arnoldi method both in the standard and restarted fashion. First, existing relaxation strategies for the outer iterative solves are extended to implicitly restarted Arnoldi's method. Second, we apply the idea of tuning the preconditioner to the inner iterative solve. As for inexact inverse iteration the tuned preconditioner for inexact Arnoldi's method is shown to provide significant savings in the number of inner solves. The theory in this thesis is supported by many numerical examples.

    Details

    Item Type Thesis (Doctor of Philosophy (PhD))
    CreatorsFreitag, M.
    Uncontrolled Keywordsgmres, convergence, jacobi-davidson method, inverse iteration, preconditioning, iterative methods, eigenvalue problem, minres, linear systems, arnoldi method
    DepartmentsFaculty of Science > Mathematical Sciences
    StatusUnpublished
    ID Code393

    Export

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...