\documentclass[draft]{siamltex}

\usepackage{amssymb}



\title{Structured Methods for Eigenproblems with Hamiltonian
Spectral Symmetry}
\author{Heike Fa\ss bender\thanks{TU Braunschweig, Carl-Friedrich-Gau\ss-Fakult\"at,
Institut Computational Mathematics, AG Numerik, 38023 Braunschweig,
Germany, \texttt{h.fassbender@tu-bs.de}}}

\newcommand {\R}        {{\mathbb{R}}}


\begin{document}
\maketitle
\section{Introduction}
It usually takes a long process of simplifications, linearizations
and discretizations before one comes up with the problem of
computing the eigenvalues or invariant subspaces of a matrix. These
techniques typically lead to highly structured matrix
representations, which, for example, may contain redundancy or
inherit some physical properties from the original problem. As a
simple example, let us consider a quadratic eigenvalue problem of
the form
\begin{equation} \label{eq:qep1}
    (\lambda^2 I_n + \lambda C + K)x = 0,
\end{equation}
where $C\in \R^{n\times n}$ is skew-symmetric ($C = -C^T$), $K\in
\R^{n\times n}$ is symmetric ($K = K^T$), and $I_n$ denotes the
$n\times n$ identity matrix. Eigenvalue problems of this type arise,
e.g., from gyroscopic systems~\cite{MehW00,TisM01} or Maxwell
equations~\cite{SchFZD03}; they have the physically relevant
property that all eigenvalues appear in quadruples
$\{\lambda,-\lambda,\bar \lambda, - \bar \lambda\}$, i.e., the
spectrum is symmetric with respect to the real and imaginary axes.

Linearization turns~(\ref{eq:qep1}) into a matrix eigenvalue
problem, e.g., the eigenvalues of~(\ref{eq:qep1}) can be obtained
from the eigenvalues of the matrix
\begin{equation} \label{eq:linear}
   A = \left[
   \begin{array}{cc}
      - \frac 1 2 C & \frac 1 4 C^2 - K \\
      I_n & -\frac 1 2 C
   \end{array}
   \right].
\end{equation}
This $2n\times 2n$ matrix is structured, its $4n^2$ entries depend
only on the $n^2$ entries necessary to define $C$ and $K$. The
matrix $A$ has the particular property that it is a Hamiltonian
matrix, i.e., $A$ is a two-by-two block matrix of the form
\[
    \left[\begin{array}{rr}
        B & G \\
        Q & -B^T
    \end{array}\right], \quad G  = G^T, \quad Q = Q^T,
\quad B, G, Q \in \R^{n \times n}.
\]
Considering $A$ to be Hamiltonian does not capture all the structure
present in $A$ but it captures an essential part: the spectrum of
any Hamiltonian matrix is symmetric with respect to the real and and
imaginary axes.

 Hamiltonian matrices also
arise in applications related to linear control theory for
continuous-time systems~\cite{Ben99}. Deciding whether a certain
Hamiltonian matrix has purely imaginary eigenvalues is the most
critical step in algorithms for computing the stability radius of a
matrix or the $H_{\infty}$ norm of a linear time-invariant system,
see, e.g.,~\cite{BoyBK89,Bye86}.

When computing the eigenvalues of a Hamiltonian eigenvalue problem
with a standard method like the $QR$ method, the computed
eigenvalues will not obey the eigenvalue pairing
$\{\lambda,-\lambda,\bar \lambda, - \bar \lambda\}$, for complex
eigenvalues with nonzero real part and $\{\lambda,-\lambda\}$ for
real and purely imaginary eigenvalues. The described eigenvalue
pairings often reflect important properties of the underlying
application and should thus be preserved in finite-precision
arithmetic. Numerical methods that take this structure into account
are capable of preserving the eigenvalue pairings of the original
eigenvalue problem~(\ref{eq:qep1}), despite the presence of roundoff
and other approximation errors. Besides the preservation of such
eigenvalue symmetries, there are several other benefits to be gained
from using structure-preserving algorithms in place of
general-purpose algorithms for computing eigenvalues. These benefits
include reduced computational time and improved
eigenvalue/eigenvector accuracy.

$QR$-like algorithms that achieve this goal have been developed
in~\cite{BenMX98,Bye86,Van85a} while Krylov subspace methods
tailored to Hamiltonian matrices can be found
in~\cite{BenF97,BenKM03,FerLW97,MehW00,Wat02b}. In this talk, we
will review these methods concentrating on the symplectic Lanczos
method endowed with an implicit restarting strategy. Unfortunately,
the implementation of efficient locking and purging strategies for
this method turns out to be even more complicated than in the
non-structured, implicitly restarted Arnoldi (IRA) method.  An
elegant away around this difficulty was presented for IRA by Stewart
\cite{Ste01a,Ste01}, using a Krylov-Schur decomposition technique.
In this talk, we will discuss the application of this idea for the
symplectic Lanczos process.  This will lead to fairly easy
implementable purging and locking strategies which improve the
convergence properties of the structured eigensolver based on the
symplectic Lanczos process significantly. We demonstrate the
efficiency of the new scheme by testing the algorithm on several
linear and quadratic eigenproblems with Hamiltonian spectral
symmetry.

This is joint work with Peter Benner (TU Chemnitz, Germany) and
Martin Stoll (University of Oxford, England).

\begin{thebibliography}{10}

\bibitem{Ben99}
P.~Benner.
\newblock Computational methods for linear-quadratic optimization.
\newblock {\em Supplemento ai Rendiconti del Circolo Matematico di Palermo,
  Serie II}, No. 58:21--56, 1999.

\bibitem{BenF97}
P.~Benner and H.~F{a\ss b}ender.
\newblock An implicitly restarted symplectic {L}anczos method for the
  {H}amiltonian eigenvalue problem.
\newblock {\em Linear Algebra Appl.}, 263:75--111, 1997.

\bibitem{BenKM03}
P.~Benner, D.~Kressner, and V.~Mehrmann.
\newblock Skew-{H}amiltonian and {H}amiltonian eigenvalue problems: Theory,
  algorithms and applications.
\newblock In Z.~Drma\v{c}, M.~Maru\v{s}i\'{c}, and Z.~Tutek, editors, {\em
  Proceedings of the Conference on Applied Mathematics and Scientific
  Computing, Brijuni (Croatia), June 23-27, 2003}, pages 3--39.
  Springer-Verlag, 2005.

\bibitem{BenMX98}
P.~Benner, V.~Mehrmann, and H.~Xu.
\newblock A numerically stable, structure preserving method for computing the
  eigenvalues of real {H}amiltonian or symplectic pencils.
\newblock {\em Numer. Math.}, 78(3):329--358, 1998.

\bibitem{BoyBK89}
S.~Boyd, V.~Balakrishnan, and P.~Kabamba.
\newblock A bisection method for computing the {$\mathcal{H}_{\infty}$} norm of
  a transfer matrix and related problems.
\newblock {\em Math. Control, Signals, Sys.}, 2:207--219, 1989.

\bibitem{Bye86}
R.~Byers.
\newblock A {H}amiltonian ${Q}{R}$ algorithm.
\newblock {\em SIAM J. Sci. Statist. Comput.}, 7(1):212--229, 1986.

\bibitem{FerLW97}
W.~R. Ferng, W.-W. Lin, and C.-S. Wang.
\newblock The shift-inverted {$J$-Lanczos} algorithm for the numerical
  solutions of large sparse algebraic {R}iccati equations.
\newblock {\em Comput. Math. Appl.}, 33(10):23--40, 1997.

\bibitem{MehW00}
V.~Mehrmann and D.~S. Watkins.
\newblock Structure-preserving methods for computing eigenpairs of large sparse
  skew-{H}amiltonian/{H}amiltonian pencils.
\newblock {\em SIAM J. Sci. Comput.}, 22(6):1905--1925, 2000.

\bibitem{SchFZD03}
F.~Schmidt, T.~Friese, L.~Zschiedrich, and P.~Deuflhard.
\newblock Adaptive multigrid methods for the vectorial {M}axwell eigenvalue
  problem for optical waveguide design.
\newblock In W.~J\"{a}ger and H.-J. Krebs, editors, {\em Mathematics. Key
  Technology for the Future}, pages 279--292, 2003.

\bibitem{Ste01a}
{\sc G.W. Stewart}, {\em A {Krylov-Sch}ur algorithm for large
eigenproblems},
  {SIAM} J. Matrix Anal. Appl., 23 (2001), pp.~601--614.

\bibitem{Ste01}
\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Matrix
Algorithms,
  {V}olume {II}: Eigensystems}, SIAM , Philadelphia, USA, 2001.

\bibitem{TisM01}
F.~Tisseur and K.~Meerbergen.
\newblock The quadratic eigenvalue problem.
\newblock {\em SIAM Rev.}, 43(2):235--286, 2001.

\bibitem{Van85a}
C.~F. {Van Loan}.
\newblock A symplectic method for approximating all the eigenvalues of a
  {H}amiltonian matrix.
\newblock {\em Linear Algebra Appl.}, 61:233--251, 1984.

\bibitem{Wat02b}
D.~S. Watkins.
\newblock On {H}amiltonian and symplectic {L}anczos processes.
\newblock {\em Linear Algebra Appl.}, 385:23--45, 2004.



\end{thebibliography}

\end{document}
