Volume 26, pp. 121-145, 2007.

The parametrized $SR$ algorithm for Hamiltonian matrices

H. Faßbender

Abstract

The heart of the implicitly restarted symplectic Lanczos method for Hamiltonian matrices consists of the $SR$ algorithm, a structure-preserving algorithm for computing the spectrum of Hamiltonian matrices. The symplectic Lanczos method projects the large, sparse $2n\times 2n$ Hamiltonian matrix $H$ onto a small, dense $2k\times 2k$ Hamiltonian $J$-Hessenberg matrix $\tilde{H}$, $k\ll n$. This $2k\times 2k$ Hamiltonian matrix is uniquely determined by $4k-1$ parameters. Using these $4k-1$ parameters, one step of the $SR$ algorithm can be carried out in $\mathcal{O}(k)$ arithmetic operations (compared to $\mathcal{O}(k^3)$ arithmetic operations when working on the actual Hamiltonian matrix). As in the context of the implicitly restarted symplectic Lanczos method the usual assumption, that the Hamiltonian eigenproblem to be solved is stable, does not hold, the case of purely imaginary eigenvalues in the $SR$ algorithm is treated here.

Full Text (PDF) [328 KB], BibTeX

Key words

Hamiltonian matrix, eigenvalue problem, $SR$ algorithm

AMS subject classifications

65F15

Links to the cited ETNA articles

[1]	Vol. 1 (1993), pp. 33-48 Gregory Ammar, Peter Benner, and Volker Mehrmann: A multishift algorithm for the numerical solution of algebraic Riccati equations
[15]	Vol. 8 (1999), pp. 115-126 Peter Benner, Volker Mehrmann, and Hongguo Xu: A note on the numerical solution of complex Hamiltonian and skew-Hamiltonian eigenvalue problems