×

New algorithms for computing the real structured pseudospectral abscissa and the real stability radius of large and sparse matrices. (English) Zbl 1325.65067

Summary: We present two new algorithms for investigating the stability of large and sparse matrices subject to real perturbations. The first algorithm computes the real structured pseudospectral abscissa and is based on the algorithm for computing the pseudospectral abscissa proposed by N. Guglielmi and M. L. Overton [SIAM J. Matrix Anal. Appl. 32, No. 4, 1166–1192 (2011; Zbl 1248.65034)]. It entails finding the rightmost eigenvalues for a sequence of large matrices, and we demonstrate that these eigenvalue problems can be solved in a robust manner by an unconventional eigenvalue solver. We also develop an algorithm for computing the real stability radius of a real and stable matrix, which utilizes a recently developed technique for detecting the loss of stability in a large dynamical system. Both algorithms are tested on large and sparse matrices.

MSC:

65F50 Computational methods for sparse matrices
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
15A24 Matrix equations and identities

Citations:

Zbl 1248.65034
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] A. C. Antoulas, D. C. Sorensen, and Y. Zhou, {\it On the Decay of Hankel Singular Values and Related Issues}, Technical Report 01-09, Department of Computational and Applied Mathematics, Rice University, Houston, 2001; available from http://www.caam.rice.edu/ sorensen/Tech_Reports.html. · Zbl 1003.93024
[2] R. H. Bartels and G. W. Stewart, {\it Algorithm 432: Solution of the matrix equation AX+XB=C}, Comm. ACM, 15 (1972), pp. 820-826. · Zbl 1372.65121
[3] R. Boisvert, R. Pozo, K. Remington, B. Miller, and R. Lipman, {\it Matrix Market}, http://math.nist.gov/MatrixMarket/.
[4] 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. · Zbl 1042.65060
[5] K. A. Cliffe, T. J. Garratt, and A. Spence, {\it Eigenvalues of block matrices arising from problems in fluid mechanics}, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 1310-1318. · Zbl 0807.65030
[6] V. Druskin and V. Simoncini, {\it Adaptive rational Krylov subspaces for large-scale dynamical systems}, Systems Control Lett., 60 (2011), pp. 546-560. · Zbl 1236.93035
[7] H. Elman, D. Silvester, and A. Wathen, {\it Finite Elements and Fast Iterative Solvers}, Oxford University Press, Oxford, UK, 2005. · Zbl 1083.76001
[8] H. C. Elman, {\it Preconditioning strategies for models of incompressible flow}, J. Sci. Comput., 25 (2005), pp. 347-366. · Zbl 1203.76098
[9] H. C. Elman, K. Meerbergen, A. Spence, and M. Wu, {\it Lyapunov inverse iteration for identifying Hopf bifurcations in models of incompressible flow}, SIAM J. Sci. Comput., 34 (2012), pp. A1584-A1606. · Zbl 1247.65047
[10] H. C. Elman, A. Ramage, and D. J. Silvester, {\it Algorithm 866: IFISS, a MATLAB toolbox for modelling incompressible flow}, ACM Trans. Math. Software, 33 (2007), pp. 14:1-14:18. · Zbl 1365.65326
[11] H. C. Elman and M. W. Rostami, {\it Efficient iterative algorithms for linear stability analysis of incompressible flows}, IMA J. Numer. Anal. (2015), DOI:10.1093/imanum/drv003. · Zbl 1425.65052
[12] H. C. Elman and R. S. Tuminaro, {\it Boundary conditions in approximate commutator preconditioners for the Navier-Stokes equations}, Electron. Trans. Numer. Anal., 35 (2009), pp. 257-280. · Zbl 1391.76539
[13] H. C. Elman and M. Wu, {\it Lyapunov inverse iteration for computing a few rightmost eigenvalues of large generalized eigenvalue problems}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1685-1707. · Zbl 1425.65053
[14] M. A. Freitag and A. Spence, {\it A Newton-based method for the calculation of the distance to instability}, Linear Algebra Appl., 435 (2011), pp. 3189-3205. · Zbl 1228.65065
[15] M. A. Freitag and A. Spence, {\it A new approach for calculating the real stability radius}, BIT Numer. Math., 54 (2014), pp. 381-400. · Zbl 1317.65097
[16] W. Govaerts, {\it Numerical Methods for Bifurcations of Dynamical Equilibria}, SIAM, Philadelphia, 2000. · Zbl 0935.37054
[17] L. Grasedyck, {\it Low-rank solutions of the Sylvester equation}, Numer. Linear Algebra Appl., 11 (2004), pp. 371-389. · Zbl 1164.65381
[18] 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. · Zbl 1272.65032
[19] N. Guglielmi and M. Manetta, {\it Approximating real stability radii}, IMA J. Numer. Anal., 35 (2015), pp. 1402-1425. · Zbl 1328.65168
[20] N. Guglielmi and M. 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. · Zbl 1248.65034
[21] R. A. Horn and C. R. Johnson, {\it Matrix Analysis}, Cambridge University Press, Cambridge, UK, 1990. · Zbl 0704.15002
[22] I. M. Jaimoukha and E. M. Kasenally, {\it Krylov subspace methods for solving large Lyapunov equations}, SIAM J. Numer. Anal., 31 (1994), pp. 227-251. · Zbl 0798.65060
[23] D. Kressner and C. Tobler, {\it Low-rank Tensor Krylov Subspace Methods for Parameterized Linear Systems}, Technical report 2010-16, ETH Zurich, 2010; available from http://www.math.ethz.ch/ kressner/. · Zbl 1208.65044
[24] K. Meerbergen and D. Roose, {\it Matrix transformations for computing rightmost eigenvalues of large sparse non-symmetric eigenvalue problems}, IMA J. Numer. Anal., 16 (1996), pp. 297-346. · Zbl 0856.65033
[25] K. Meerbergen and A. Spence, {\it Inverse iteration for purely imaginary eigenvalues with application to the detection of Hopf bifurcation in large scale problems}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1982-1999. · Zbl 1205.65156
[26] T. Penzl, {\it Eigenvalue decay bounds for solutions of Lyapunov equations: The symmetric case}, Systems Control Lett., 40 (2000), pp. 139-144. · Zbl 0977.93034
[27] 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, 31 (1995), pp. 879-890. · Zbl 0839.93039
[28] Y. Saad, {\it Numerical Solution of Large Lyapunov Equations}, in Signal Processing, Scattering, Operator Theory, and Numerical Methods, M. A. Kaashoek, J. H. van Schuppen, and A. C. Ran, eds., Birkhauser, Boston, 1990, pp. 503-511.
[29] Y. Saad, {\it Numerical Methods for Large Eigenvalue Problems}, Manchester University Press, Manchester, UK, 1992. · Zbl 0991.65039
[30] V. Simoncini, {\it A new iterative method for solving large-scale Lyapunov matrix equations}, SIAM J. Sci. Comput., 29 (2007), pp. 1268-1288. · Zbl 1146.65038
[31] D. C. Sorensen, {\it Implicit application of polynomial filters in a k-step Arnoldi method}, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 357-385. · Zbl 0763.65025
[32] J. Sreedhar, P. Van Dooren, and A. L. Tits, {\it A fast algorithm to compute the real structured stability radius}, in Stability Theory, Internet Ser. Numer. Math. 121, Birkhauser, Boston, 1996, pp. 219-230. · Zbl 0872.93027
[33] G. W. Stewart, {\it Matrix Algorithms Volume II: Eigensystems}, SIAM, Philadelphia, 2001. · Zbl 0984.65031
[34] 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
[35] T. G. Wright, {\it EigTool: A Graphical Tool for Nonsymmetric Eigenproblems}, Tech. report, Oxford University Computing Laboratory, Oxford, UK, 2002; available from http://www.comlab.ox.ac.uk/pseudospectra/eigtool/.
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.