×

On the method by Rostami for computing the real stability radius of large and sparse matrices. (English) Zbl 1339.65053

Summary: In a recent paper, M. W. Rostami [SIAM J. Sci. Comput. 37, No. 5, S447–S471 (2015; Zbl 1325.65067)] has presented an interesting algorithm for the computation of the real pseudospectral abscissa and the real stability radius (aka the distance to instability) of a square matrix \(A \in \mathbb R^{n,n}\) in the spectral norm. The method is particularly well suited for large sparse matrices. The algorithm to compute the stability radius is based on the alternation of an iterative method in the rank-\(2\) manifold of real matrices and a Lyapunov inverse iteration. The algorithm shows quadratic convergence in all experiments, but this peculiar property is only conjectured. In this paper, we provide a rigorous proof and propose a modification which replaces the Lyapunov inverse iteration and speeds up the method. Moreover, we interpret the algorithm to compute the real \(\varepsilon\)-pseudospectral abscissa as a nonstandard discretization of the ODE-based method given in [N. Guglielmi and C. Lubich, SIAM J. Matrix Anal. Appl. 34, No. 1, 40–66 (2013; Zbl 1272.65032)]. Several numerical illustrations comparing the modified algorithm with that proposed by Rostami conclude the paper.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
65F10 Iterative numerical methods for linear systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Byers, {\it A bisection method for measuring the distance of a stable matrix to the unstable matrices}, SIAM J. Sci. Statist. Comput., 9 (1988), pp. 875-881, http://dx.doi.org/10.1137/0909059. · Zbl 0658.65044
[2] J. V. Burke, A. S. Lewis, and M. L. Overton, {\it Robust stability and a criss-cross algorithm for pseudospectra}, IMA J. Numer. Anal., 23 (2003), pp. 359-375, http://dx.doi.org/10.1093/imanum/23.3.359. · Zbl 1042.65060
[3] R. F. Boisvert, R. Pozo, K. Remington, R. F. Barrett, and J. J. Dongarra, {\it Matrix Market: A web resource for test matrix collections}, in Quality of Numerical Software, Chapman & Hall, London, 1997, pp. 125-137.
[4] M. A. Freitag and A. Spence, {\it A new approach for calculating the real stability radius}, BIT, 54 (2014), pp. 381-400, http://dx.doi.org/10.1007/s10543-013-0457-x. · Zbl 1317.65097
[5] N. Guglielmi, D. Kressner, and C. Lubich, {\it Low rank differential equations for Hamiltonian matrix nearness problems}, Numer. Math., 129 (2015), pp. 279-319, http://dx.doi.org/10.1007/s00211-014-0637-x. · Zbl 1312.65070
[6] N. Guglielmi and C. Lubich, {\it Low-rank dynamics for computing extremal points of real pseudospectra}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 40-66, http://dx.doi.org/10.1137/120862399. · Zbl 1272.65032
[7] N. Guglielmi and M. Manetta, {\it Approximating real stability radii}, IMA J. Numer. Anal., 35 (2015), pp. 1402-1425, http://dx.doi.org/10.1093/imanum/dru038. · Zbl 1328.65168
[8] N. Guglielmi and M. L. Overton, {\it 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, http://dx.doi.org/10.1137/100817048. · Zbl 1248.65034
[9] D. Hinrichsen and A. J. Pritchard, {\it Mathematical Systems Theory I: Modelling, State Space Analysis, Stability and Robustness}, Springer, Berlin, Heidelberg, New York, 2005, http://dx.doi.org/10.1007/b137541. · Zbl 1074.93003
[10] T. Kato, {\it Perturbation Theory for Linear Operators}, Classics Math., Springer-Verlag, Berlin, 1995. · Zbl 0836.47009
[11] M. Karow, M. Kokiopoulou, and D. Kressner, {\it On the computation of structured singular values and pseudospectra}, Systems Control Lett., 59 (2010), pp. 122-129, http://dx.doi.org/10.1016/j.sysconle.2009.12.007. · Zbl 1186.93032
[12] D. Kressner and B. Vandereycken, {\it Subspace methods for computing the pseudospectral abscissa and the stability radius}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 292-313, http://dx.doi.org/10.1137/120869432. · Zbl 1306.65187
[13] R. B. Lehoucq and D. C. Sorensen, {\it Deflation techniques for an implicitly restarted Arnoldi iteration}, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 789-821, http://dx.doi.org/10.1137/S0895479895281484. · Zbl 0863.65016
[14] R. B. Lehoucq, D. C. Sorensen, and C. Yang, {\it ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods}, Software Environ. Tools 6, SIAM, Philadelphia, 1998, http://dx.doi.org/10.1137/1.9780898719628.
[15] W. Michiels, {\it private communication}, 2015.
[16] L. Qiu, B. Bernhardsson, A. Rantzer, E. J. Davison, P. M. Young, and J. C. Doyle, {\it A formula for computation of the real stability radius}, Automatica J. IFAC, 31 (1995), pp. 879-890, http://dx.doi.org/10.1016/0005-1098(95)00024-Q. · Zbl 0839.93039
[17] L. Qiu, A. L. Tits, and Y. G. Yang, {\it On the computation of the real Hurwitz-stability radius}, IEEE Trans. Automat. Control, 40 (1995), pp. 1475-1476, http://dx.doi.org/10.1109/9.402245. · Zbl 0825.93608
[18] M. W. Rostami, {\it New algorithms for computing the real structured pseudospectral abscissa and the real stability radius of large and sparse matrices}, SIAM J. Sci. Comput., 37 (2015), pp. S447-S471, http://dx.doi.org/10.1137/140975413. · Zbl 1325.65067
[19] J. Sreedhar, P. Van Dooren, and A. L. Tits, {\it A fast algorithm to compute the real structured stability radius}, in Stability Theory, Birkhäuser, Basel, 1996, pp. 219-230. · Zbl 0872.93027
[20] L. N. Trefethen and M. Embree, {\it Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators}, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
[21] T. G. Wright, {\it EigTool Package: A Graphical Tool for Nonsymmetric Eigenproblems}, Oxford University Computing Laboratory, Oxford, UK, 2002; available online from http://www.comlab.ox.ac.uk/pseudospectra/eigtool.
[22] K. Zhou, K. Glover, and J. Doyle, {\it Robust and Optimal Control}, Prentice-Hall, Upper Saddle River, NJ, 1995. · Zbl 0999.49500
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.