\documentstyle{article}

\textwidth 159mm
\textheight 233mm
\topmargin 0mm
\oddsidemargin 0mm
\evensidemargin 0mm

\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}{Notation}[section]
\newtheorem{example}{Example}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{problem}{Problem}

\newcommand{\cc}{\mbox{\boldmath$C$}}
\newcommand{\rr}{\mbox{\boldmath$R$}}
\newcommand{\ul}{\underline}
\newcommand{\KK}{{\cal K}}

\title{The computation of eigenvalues of definite matrix pencils by the
        rational Krylov method}
\author{Karl Meerbergen \thanks{%
        LMS Numerical Technologies, Interleuvenlaan~70,
        3001 Heverlee, Belgium. {\tt karl.meerbergen@lms.be}}
}
\date{March 1998}

\begin{document}

\maketitle

The subject of this paper is the computation of a number of eigenvalues and
the corresponding eigenvectors of the matrix pencil
\begin{equation}\label{eq:eigval}
A x = \lambda B x
\end{equation}
where $A$ and $B$ are symmetric and $B$ is positive definite.
Applications of this form arise from structural and
acoustic modal analysis.
The most commonly used methods are the spectral transformation Lanczos method
and its block version.
The Lanczos method builds a $B$ orthonormal basis of the Krylov space
$$\KK_k((A-\mu B)^{-1} B, v_1) = {\rm span} \{ v_1,(A-\mu B)^{-1} B v_1,
..., ((A-\mu B)^{-1} B)^{k-1} v_1\} \ .$$
Here $(A-\mu B)^{-1} B$ is the spectral transformation.
The method typically converges fast for the eigenvalues of
(\ref{eq:eigval}) near $\mu$.
A problem may arise when a relatively large number of eigenvalues is wanted.
This may require a Krylov space of large dimension, which is not possible
in practice due to memory restrictions.
Especially when also a number of eigenvalues far away from $\mu$ is wanted, the
memory and orthogonalization costs become extremely large.
In the literature, two solutions have been proposed to this problem.
The first one is to restart the method with a new pole $\mu$ closer to the
eigenvalues that are not yet computed accurately enough.
The second one is the implicitly restarted Lanczos method.
The current Lanczos basis is compressed into a basis of smaller dimension
by throwing away a part of the subspace that will probably not contribute to
the convergence of the wished eigenpairs.
The compressed subspace can be expanded again by additional Lanczos steps.

The spectral transformation Lanczos method requires the solution of a large
number of linear systems with the same matrix.
Usually, a direct method is used, since one can take advantage of
factoring only once.
In order to compensate for the factorization cost, it may be interesting to use
the implicitly restarted Lanczos method to compute many eigenvalues near $\mu$,
rather than changing the pole at each restart.
On the other hand, the convergence speeds up by altering the pole from
time to time.
Unfortunately, moving the pole requires a complete restart of the method.

In this paper, we present a practical algorithm for the computation of
eigenpairs of (\ref{eq:eigval}) by the rational Krylov method with $B$
orthogonalization and implicit restarts.
The implementation is based on the experience with the spectral transformation
Lanczos method.
The only point of difference with the latter method is the fact that the pole
can be altered.
We also prove that the pole should be changed with care in order to maintain
the numerical stability of the method.
More precisely, we prove that when the pole is chosen close to a Ritz value
with small residual norm, the method might lose numerical stability.
Clearly, chosing a pole near a `converged' eigenvalue is not a good idea
in practice, since also the linear solver suffers from this.

The theory and the algorithm are illustrated for the computation of acoustic
modes of a car exhaust pipe filled with air, discretized by 39254 3D hexagon
acoustic finite elements.
This leads to a problem of the form (\ref{eq:eigval}) of size $n=46966$.

\end{document}