![]() |
![]() |
ETNA - Electronic Transactions on Numerical Analysis
|
![]() |
Verlag der Österreichischen Akademie der Wissenschaften Austrian Academy of Sciences Press
A-1011 Wien, Dr. Ignaz Seipel-Platz 2
Tel. +43-1-515 81/DW 3420, Fax +43-1-515 81/DW 3400 https://verlag.oeaw.ac.at, e-mail: verlag@oeaw.ac.at |
![]() |
|
DATUM, UNTERSCHRIFT / DATE, SIGNATURE
BANK AUSTRIA CREDITANSTALT, WIEN (IBAN AT04 1100 0006 2280 0100, BIC BKAUATWW), DEUTSCHE BANK MÜNCHEN (IBAN DE16 7007 0024 0238 8270 00, BIC DEUTDEDBMUC)
|
ETNA - Electronic Transactions on Numerical Analysis, pp. 402-431, 2023/04/28
Given two square matrices $A$ and $B$, we propose a new approach for computingthe 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 computingthis quantity,called $\mathrm{sep}_\lambda(A,B)$ (“sep-lambda”), using ideas inspired from an earlier algorithmof 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 otheralgorithms have been known.Our new algorithm can be orders of magnitude faster and can solveproblems 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 computean earlier version of sep-lambda where $\|E\| + \|F\\|=\varepsilon$.
Keywords: sep-lambda, eigenvalue separation, eigenvalue perturbation, pseudospectra, Hamiltonian matrix