×

Differential equations for real-structured defectivity measures. (English) Zbl 1320.65053

Summary: Let \(A\) be a real matrix with all distinct eigenvalues. We propose a new method for the computation of the distance \(w_\mathbb R(A)\) of the matrix \(A\) from the set of real defective matrices, i.e., the set of those real matrices with at least one multiple eigenvalue with algebraic multiplicity larger than its geometric multiplicity. For \(0 < \varepsilon \leq w_\mathbb R(A)\), this problem is closely related to the computation of the most ill-conditioned \(\varepsilon\)-pseudoeigenvalues of \(A\), that is, points in the \(\epsilon\)-pseudospectrum of \(A\) characterized by the highest condition number. The method we propose couples a system of differential equations on a low-rank manifold which determines the \(\varepsilon\)-pseudoeigenvalue closest to coalescence, with a fast Newton-like iteration aiming to determine the minimal value \(\varepsilon\) such that an \(\varepsilon\)-pseudoeigenvalue becomes defective. The method has a local behavior; this means that, in general, we find upper bounds for \(w_\mathbb R(A)\). However, these bounds usually provide good approximations, in those (simple) cases where we can check this. The methodology can be extended to a structured matrix, where it is required that the distance be computed within some manifold defining the structure of the matrix. In this paper we extensively examine the case of real matrices. As far as we know, there do not exist methods in the literature able to compute such distance.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] R. O. Akinola, M. A. Freitag, and A. Spence, {\it The calculation of the distance to a nearby defective matrix}, Numer. Linear Algebra Appl., 21 (2014), pp. 403-414. · Zbl 1340.65072
[2] R. Alam, {\it Wilkinson’s problem revisited}, J. Anal., 14 (2006), pp. 175-205. · Zbl 1193.65035
[3] R. Alam and S. Bora, {\it On sensitivity of eigenvalues and eigendecompositions of matrices}, Linear Algebra Appl., 396 (2005), pp. 273-301. · Zbl 1084.15017
[4] R. Alam, S. Bora, R. Byers, and M. L. Overton, {\it Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components}, Linear Algebra Appl., 435 (2011), pp. 494-513. · Zbl 1228.65062
[5] 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 The Quality of Numerical Software: Assessment and Enhancement, R. F. Boisvert, ed., Chapman & Hall, London, 1997, pp. 125-137; also available online from \burlhttp://math.nist.gov/MatrixMarket/.
[6] P. Buttà, N. Guglielmi, and S. Noschese, {\it Computing the structured pseudospectrum of a Toeplitz matrix and its extreme points}, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 1300-1319. · Zbl 1263.65039
[7] R. Byers and D. Kressner, {\it On the condition of a complex eigenvalue under real perturbations}, BIT, 44 (2004), pp. 209-214. · Zbl 1071.15004
[8] J. B. Conway and P. R. Halmos, {\it Finite-dimensional points of continuity of Lat}, Linear Algebra Appl., 31 (1980), pp. 93-102. · Zbl 0435.15005
[9] J. W. Demmel, {\it A Numerical Analyst’s Jordan Canonical Form}, Ph.D. thesis, Computer Science Division, University of California, Berkeley, 1983.
[10] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, 2013.
[11] N. Guglielmi and C. Lubich, {\it Differential equations for roaming pseudospectra: Paths to extremal points and boundary tracking}, SIAM J. Numer. Anal., 49 (2011), pp. 1194-1209. · Zbl 1232.15009
[12] 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. · Zbl 1248.65034
[13] N. Guglielmi, M. L. Overton, and G. W. Stewart, {\it An efficient algorithm for computing the generalized null space decomposition}, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 38-54. · Zbl 1327.65072
[14] M. Karow, D. Kressner, and F. Tisseur, {\it Structured eigenvalue condition numbers}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 1052-1068. · Zbl 1130.65054
[15] O. Koch and C. Lubich, {\it Dynamical low-rank approximation}, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 434-454. · Zbl 1145.65031
[16] 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. · Zbl 0901.65021
[17] A. N. Malyshev, {\it A formula for the 2-norm distance from a matrix to the set of matrices with multiple eigenvalues}, Numer. Math., 83 (1999), pp. 443-454. · Zbl 0972.15011
[18] E. Mengi, E. A. Yildirim, and M. Kiliç, {\it Numerical optimization of eigenvalues of Hermitian matrix functions}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 699-724. · Zbl 1307.65043
[19] C. D. Meyer and G. W. Stewart, {\it Derivatives and perturbations of eigenvectors}, SIAM J. Numer. Anal., 25 (1988), pp. 679-691. · Zbl 0646.15005
[20] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, PWS Publishing, Boston, 1996. · Zbl 1031.65047
[21] A. Spence and C. Poulton, {\it Photonic band structure calculations using nonlinear eigenvalue techniques}, J. Comput. Phys., 204 (2005), pp. 65-81. · Zbl 1143.82336
[22] 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
[23] J. H. Wilkinson, {\it The Algebraic Eigenvalue Problem}, Clarendon Press, Oxford, UK, 1965. · Zbl 0258.65037
[24] M. A. Woodbury, {\it Inverting Modified Matrices}, Memo. Rep. no. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950.
[25] T. G. Wright, {\it EigTool: A Graphical Tool for Nonsymmetric Eigenproblems}, Oxford University Computing Laboratory, http://www.comlab.ox.ac.uk/pseudospectra/eigtool/ (2002).
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.