Volume 58, pp. 402-431, 2023.

Fast computation of Sep$_\lambda$ via interpolation-based globality certificates

Tim Mitchell

Abstract

Given two square matrices $A$ and $B$, we propose a new approach for computing the smallest value $\varepsilon \geq 0$ such that $A+E$ and $A+F$ share an eigenvalue, where $\|E\|=\|F\|=\varepsilon$. In 2006, Gu and Overton proposed the first algorithm for computing this quantity, called $\mathrm{sep}_\lambda(A,B)$ (“sep-lambda”), using ideas inspired from an earlier algorithm of Gu for computing the distance to uncontrollability. However, the algorithm of Gu and Overton is extremely expensive, which limits it to the tiniest of problems, and until now, no other algorithms have been known. Our new algorithm can be orders of magnitude faster and can solve problems where $A$ and $B$ are of moderate size. Moreover, our method consists of many “embarrassingly parallel” computations, and so it can be further accelerated on multi-core hardware. Finally, we also propose the first algorithm to compute an earlier version of sep-lambda where $\|E\| + \|F\|=\varepsilon$.

Full Text (PDF) [1.4 MB], BibTeX

Key words

sep-lambda, eigenvalue separation, eigenvalue perturbation, pseudospectra, Hamiltonian matrix

AMS subject classifications

15A18, 15A22, 15A42, 65F15, 65F30

Links to the cited ETNA articles

[2]	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

Additional resources for this document

Additional files

< Back