Iterative methods for PDE eigenvalue problems

Prof Ivan Graham
When steady solutions of complex physical problems are computed numerically it is often crucial to compute their <em>stability</em> in order to, for example, check that the computed solution is "physical", or carry out a sensitivity analysis, or help understand complex nonlinear phenomena near a bifurcation point. Usually a stability analysis requires the solution of an <em>eigenvalue problem</em> which may arise in its own right or as an appropriate linearisation. In the case of discretized PDEs the corresponding matrix eigenvalue problem will often be of generalised form: \\ $Ax=\lambda Mx$ (1) \\ with $A$ and $M$ large and sparse. In general $A$ is unsymmetric and $M$ is positive semi-definite. Only a small number of "dangerous" eigenvalues are usually required, often those (possibly complex) eigenvalues nearest the imaginary axis. In this context it is usually necessary to perform "shift-invert" iterations, which require repeated solution of systems of the form \\ $(A - \sigma M)y = Mx$, (2) \\ for some <em>shift</em> $\sigma$ (which may be near a spectral point) and for various right-hand sides $x$. In large applications systems (2) have to be solved iteratively, requiring <em>"inner iterations"</em>. \\ \\ In this talk we will describe recent progress in the construction, analysis and implementation of fast algorithms for finding such eigenvalues, utilising algebraic domain decomposition techniques for the inner iterations. \\ \\ In the first part we will describe an analysis of inverse iteration techniques for (1) for a model problem in the presence of errors arising from inexact solves of (2). The delicate interplay between the convergence of the (outer) inverse iteration and the choice of tolerance for the inner solves can be used to determine an efficient iterative method provided a good preconditioner for $A$ is available. \\ \\ In the second part we describe an application to the computation of bifurcations in Navier-Stokes problems discretised by mixed finite elements applied to the velocity-pressure formulation. We describe the construction of appropriate preconditioners for the corresponding (3 x 3 block) version of (2). These use additive Schwarz methods and can be applied to any unstructured mesh in 2D or 3D and for any selected elements. An important part of the preconditioner is the adaptive coarsening strategy. At the heart of this are recent extensions of the Bath domain decomposition code DOUG, carried out by Eero Vainikko. \\ \\ An application to the computation of a Hopf bifurcation of planar flow around a cylinder will be given. \\ \\ This is joint work with Jörg Berns-Müller, Andrew Cliffe, Alastair Spence and Eero Vainikko and is supported by EPSRC Grant GR/M59075.
  • Computational Mathematics and Applications Seminar