Extended and improved criss-cross algorithms for computing the spectral value set abscissa and radius. (English) Zbl 1457.93066

In this paper, the authors extend the original criss-cross algorithms for computing the \(\varepsilon\)-pseudospectral abscissa and radius to general spectral value sets. By proposing new root-finding-based strategies for the horizontal/radial search subphases, authors significantly reduce the number of expensive Hamiltonian eigenvalue decompositions incurred, which typically translates to meaningful speedups in overall computation times. Furthermore, and partly necessitated by our root-finding approach, authors develop a new way of handling the singular pencils or problematic interior searches that can arise when computing the \(\varepsilon\)-spectral value set radius. Compared to would-be direct extensions of the original algorithms, that is, without this additional modifications, their improved criss-cross algorithms are not only noticeably faster but also more robust and numerically accurate, for both spectral value set and pseudospectral problems (From the Summary).


93D09 Robust stability
93C05 Linear systems in control theory
93B36 \(H^\infty\)-control
Full Text: DOI arXiv


[1] P. Benner, V. Mehrmann, V. Sima, S. V. Huffel, and A. Varga, SLICOT - a subroutine library in systems and control theory, in Applied and Computational Control, Signals, and Circuits, B. N. Datta, ed., vol. 1, Birkhäuser, Boston, MA, 1999, ch. 10, pp. 499–539. · Zbl 1051.93500
[2] P. Benner and T. Mitchell, Faster and more accurate computation of the \(\mathcal{H}_\infty\) norm via optimization, SIAM J. Sci. Comput., 40 (2018), pp. A3609–A3635. · Zbl 1401.93087
[3] P. Benner and M. Voigt, A structured pseudospectral method for \(\mathcal{H}_\infty \)-norm computation of large-scale descriptor systems, Math. Control Signals Systems, 26 (2014), pp. 303–338. · Zbl 1290.93083
[4] J. V. Burke, A. S. Lewis, and M. L. Overton, Robust stability and a criss-cross algorithm for pseudospectra, IMA J. Numer. Anal., 23 (2003), pp. 359–375. · Zbl 1042.65060
[5] R. Byers, A bisection method for measuring the distance of a stable matrix to matrices unstable matrices, SIAM J. Sci. Statist. Comput., 9 (1988), pp. 875–881. · Zbl 0658.65044
[6] L. Dai, Singular Control Systems, Lect. Notes Control Inf. Sci. 118, Springer-Verlag, Berlin, 1989. · Zbl 0669.93034
[7] F. Freitas, J. Rommes, and N. Martins, Gramian-based reduction method applied to large sparse power system descriptor models, IEEE Trans. Power Syst., 23 (2008), pp. 1258–1270.
[8] N. Guglielmi, M. Gürbüzbalaban, and M. L. Overton, Fast approximation of the \(H_\infty\) norm via optimization over spectral value sets, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 709–737. · Zbl 1271.93057
[9] N. Guglielmi and M. L. Overton, Fast algorithms for the approximation of the pseudospectral abscissa and pseudospectral radius of a matrix, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1166–1192. · Zbl 1248.65034
[10] D. Hinrichsen and A. J. Pritchard, Mathematical Systems Theory I, Springer-Verlag, Berlin, 2005. · Zbl 1074.93003
[11] D. Hinrichsen and N. K. Son, Stability radii of linear discrete-time systems and symplectic pencils, Internat. J. Robust Nonlinear Control, 1 (1991), pp. 79–97. · Zbl 0754.93060
[12] P. Lancaster, On eigenvalues of matrices dependent on a parameter, Numer. Math., 6 (1964), pp. 377–387. · Zbl 0133.26201
[13] A. Laub, Efficient multivariable frequency response computations, IEEE Trans. Automat. Control, 26 (1981), pp. 407–408.
[14] E. Mengi, Measures for Robust Stability and Controllability, Ph.D. thesis, New York University, New York, NY, 2006.
[15] E. Mengi and M. L. Overton, Software for Robust Stability and Controllability, http://home.ku.edu.tr/ emengi/software/robuststability.html. · Zbl 1082.65043
[16] E. Mengi and M. L. Overton, Algorithms for the computation of the pseudospectral radius and the numerical radius of a matrix, IMA J. Numer. Anal., 25 (2005), pp. 648–669. · Zbl 1082.65043
[17] T. Mitchell and M. L. Overton, Hybrid expansion-contraction: A robust scaleable method for approximating the \(H_\infty\) norm, IMA J. Numer. Anal., 36 (2016), pp. 985–1014. · Zbl 1433.93100
[18] M. L. Overton and R. S. Womersley, Second derivatives for optimizing eigenvalues of symmetric matrices, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 697–718. · Zbl 0832.65036
[19] L. N. Trefethen, Computation of pseudospectra, Acta Numer., 8 (1999), pp. 247–295. · Zbl 0945.65039
[20] L. N. Trefethen and M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
[21] L. N. Trefethen, A. E. Trefethen, S. C. Reddy, and T. A. Driscoll, Hydrodynamic stability without eigenvalues, Science, 261 (1993), pp. 578–584. · Zbl 1226.76013
[22] P. Van Dooren and M. Verhaegen, On the use of unitary state-space transformations, in Linear Algebra and Its Role in Systems Theory (Brunswick, Maine, 1984), Contemp. Math. 47, American Mathematical Society, Providence, RI, 1985, pp. 447–463.
[23] C. F. Van Loan, How near is a stable matrix to an unstable matrix?, in Linear Algebra and Its Role in Systems Theory (Brunswick, ME, 1984), Contemp. Math. 47, American Mathematical Society, Providence, RI, 1985, pp. 465–478.
[24] T. G. Wright, EigTool, 2002, http://www.comlab.ox.ac.uk/pseudospectra/eigtool/.
[25] T. G. Wright and L. N. Trefethen, Large-scale computation of pseudospectra using ARPACK and Eigs, SIAM J. Sci. Comput., 23 (2001), pp. 591–605. · Zbl 0992.65030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.