×

Solving singular generalized eigenvalue problems by a rank-completing perturbation. (English) Zbl 1435.65056

Summary: Generalized eigenvalue problems involving a singular pencil are very challenging to solve, with respect to both accuracy and efficiency. The existing package Guptri is very elegant but may be time-demanding, even for small and medium-sized matrices. We propose a simple method to compute the eigenvalues of singular pencils, based on one perturbation of the original problem of a certain specific rank. For many problems, the method is both fast and robust. This approach may be seen as a welcome alternative to staircase methods.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
15A22 Matrix pencils
15A21 Canonical forms, reductions, classification
47A55 Perturbation theory of linear operators
65F22 Ill-posedness and regularization problems in numerical linear algebra

Software:

MultiParEig; JDQZ; JDQR
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] F. V. Atkinson, Multiparameter Eigenvalue Problems, Academic Press, New York, 1972.
[2] A. Boralevi, J. van Doornmalen, J. Draisma, M. E. Hochstenbach, and B. Plestenjak, Uniform determinantal representations, SIAM J. Appl. Algebra Geometry, 1 (2017), pp. 415-441.
[3] P. Benner, P. Losse, V. Mehrmann, and M. Voigt, Numerical linear algebra methods for linear differential-algebraic equations, in Surveys in Differential-Algebraic Equations III, A. Ilchmann and T. Reis, eds., Differ.-Algebr. Equ. Forum, Springer, Cham, 2015, pp. 117-175. · Zbl 1343.65100
[4] R. Byers, C. He, and V. Mehrmann, Where is the nearest non-regular pencil?, Linear Algebra Appl., 285 (1998), pp. 81-105. · Zbl 0935.15013
[5] N. Cottin, Dynamic model updating–a multiparameter eigenvalue problem, Mechanical Systems Signal Processing, 15 (2001), pp. 649-665.
[6] E. J. Davison and S. H. Wang, Properties and calculation of transmission zeros of linear multivariable systems, Automatica, 10 (1974), pp. 643-658. · Zbl 0299.93018
[7] F. De Terán and F. M. Dopico, Low rank perturbation of Kronecker structures without full rank, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 496-529. · Zbl 1142.15010
[8] F. De Terán and F. M. Dopico, A note on generic Kronecker orbits of matrix pencils with fixed rank, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 491-496. · Zbl 1165.15012
[9] F. De Terán, F. M. Dopico, and J. Moro, First order spectral perturbation theory of square singular matrix pencils, Linear Algebra Appl., 429 (2008), pp. 548-576. · Zbl 1154.15012
[10] J. Demmel, Generalized non-Hermitian eigenproblems, in Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., Software Environ. Tools 11, SIAM, Philadelphia, 2000, pp. 28-36.
[11] J. Demmel and B. K\aagström, Computing stable eigendecompositions of matrix pencils, Linear Algebra Appl., 88/89 (1987), pp. 139-186. · Zbl 0627.65032
[12] J. Demmel and B. K\aagström, Accurate solutions of ill-posed problems in control theory, SIAM J. Matrix. Anal. Appl., 9 (1988), pp. 126-145.
[13] J. Demmel and B. K\aagström, The generalized Schur decomposition of an arbitrary pencil A \(-\lambda B\)-robust software with error bounds and applications. Part I: Theory and algorithms, ACM Trans. Math. Software, 19 (1993), pp. 160-174.
[14] A. Edelman and Y. Ma, Staircase failures explained by orthogonal versal forms, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1004-1025. · Zbl 0965.65066
[15] A. Emami-Naeini and P. Van Dooren, Computation of zeros of linear multivariable systems, Automatica 18 (1982), pp. 415-430. · Zbl 0484.93029
[16] F. R. Gantmacher, Theory of Matrices, Chelsea, New York, 1959.
[17] Guptri, Software for Singular Pencils, http://www8.cs.umu.se/research/nla/singular_pairs/guptri/.
[18] M. E. Hochstenbach, T. Košir, and B. Plestenjak, A Jacobi-Davidson type method for the nonsingular two-parameter eigenvalue problem, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 477-497. · Zbl 1077.65036
[19] M. E. Hochstenbach, A. Muhič, and B. Plestenjak, On linearizations of the quadratic two-parameter eigenvalue problem, Linear Algebra Appl., 436 (2012), pp. 2725-2743. · Zbl 1245.65042
[20] E. Jarlebring and M. E. Hochstenbach, Polynomial two-parameter eigenvalue problems and matrix pencil methods for stability of delay-differential equations, Linear Algebra Appl., 431 (2009), pp. 369-380. · Zbl 1170.65063
[21] E. Jarlebring, S. Kvaal, and W. Michiels, Computing all pairs \(( \lambda,\mu )\) such that \(\lambda\) is a double eigenvalue of A \(+\mu B\), SIAM J. Matrix Anal. Appl., 32 (2011), pp. 902-927. · Zbl 1245.65043
[22] B. K\aagström, Singular matrix pencils, in Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds, Software Environ. Tools 11, SIAM, Philadelphia, 2000, pp. 260-277,
[23] P. Kunkel and V. Mehrmann, Differential-Algebraic Equations: Analysis and Numerical Solution, EMS Publishing House, Zürich, Switzerland, 2006. · Zbl 1095.34004
[24] A. J. Laub and B. C. Moore, Calculation of transmission zeros using \(QZ\) techniques, Automatica, 14 (1978), pp. 557-566. · Zbl 0393.93026
[25] D. S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann, Skew-symmetric matrix polynomials and their Smith forms, Linear Algebra Appl., 438 (2013), pp. 4625-4653. · Zbl 1281.15020
[26] D. S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann, Möbius transformations of matrix polynomials, Linear Algebra Appl., 470 (2015), pp. 120-184. · Zbl 1309.65042
[27] C. Mehl, V. Mehrmann, and M. Wojtylak, On the distance to singularity via low rank perturbations, Oper. Matrices, 9 (2015), pp. 733-772. · Zbl 1342.15006
[28] C. Mehl, V. Mehrmann, and M. Wojtylak, Parameter-dependent rank-one perturbations of singular Hermitian or symmetric pencils, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 72-95. · Zbl 1354.15007
[29] C. Mehl, V. Mehrmann, and M. Wojtylak, Linear algebra properties of dissipative Hamiltonian descriptor systems, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 1489-1519. · Zbl 1403.15009
[30] V. Mehrmann, private communication, 2018.
[31] A. Muhič and B. Plestenjak, On the singular two-parameter eigenvalue problem, Electron. J. Linear Algebra, 18 (2009), pp. 420-437. · Zbl 1190.15011
[32] A. Muhič and B. Plestenjak, On the quadratic two-parameter eigenvalue problem and its linearization, Linear Algebra Appl., 432 (2010), pp. 2529-2542. · Zbl 1189.65070
[33] A. Muhič and B. Plestenjak, A method for computing all values \(\lambda\) such that A \(+\lambda B\) has a multiple eigenvalue, Linear Algebra Appl., 440 (2014), pp. 345-359. · Zbl 1292.65039
[34] MCS Toolbox. The Matrix Canonical Structure Toolbox for Matlab, http://www.cs.umu.se/english/research/groups/matrix-computations/stratigraph.
[35] MultiParEig. Toolbox for Multiparameter Eigenvalue Problems, http://www.mathworks.com/matlabcentral/fileexchange/47844-multipareig.
[36] Multiprecision Computing Toolbox, Advanpix, Tokyo, www.advanpix.com.
[37] B. Plestenjak and M. E. Hochstenbach, Roots of bivariate polynomial systems via determinantal representations, SIAM J. Sci. Comput., 38 (2016), pp. A765-A788. · Zbl 1376.65056
[38] N. Valeev, On a spectral property of irregular pencils, Ufa Math. J., 4 (2012), pp. 44-52.
[39] N. Valeev, On quasiregular spectrum of matrix pencils, Dokl. Math., 88 (2013), pp. 545-547. · Zbl 1281.15014
[40] P. Van Dooren, The computation of Kronecker’s canonical form of a singular pencil, Linear Algebra Appl., 27 (1979), pp. 103-140. · Zbl 0416.65026
[41] P. Van Dooren, Reducing subspaces: Definitions, properties and algorithms, in Matrix Pencils, B. K\aagström and A. Ruhe, eds., Lecture Notes in Math. 973. Springer, Berlin, 1983, pp. 58-73.
[42] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, Oxford, UK, 1965.
[43] J. H. Wilkinson, Kronecker’s canonical form and the \(QZ\) algorithm, Linear Algebra Appl., 28 (1979), pp. 285-303. · Zbl 0458.65022
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.