×

Fast and backward stable computation of eigenvalues and eigenvectors of matrix polynomials. (English) Zbl 1434.65030

The authors propose a novel approach for solving polynomial eigenvalue problems, i.e., to find eigenvalues \(\lambda\) as well as eigenvectors \(v\) satisfying \(P(\lambda)v=0\), where \(P(\lambda)=\sum_{j=0}^d P_j\lambda^j\) and \(P_j\in\mathbb{C}^{n\times n}\). This approach employs the standard block-companion matrix pencil linearization, and the Francis implicitly shifted QR algorithm.
The authors show that the whole calculation is feasible, since the matrices can be stored in a numerically reliable way. They also provide a stability analysis, thus showing that their approach is normwise backward stable after a proper scaling. These results are illustrated by numerical examples.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A22 Matrix pencils
15A18 Eigenvalues, singular values, and eigenvectors

Software:

NLEVP; mctoolbox
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aurentz, Jared L.; Mach, Thomas; Vandebril, Raf; Watkins, David S., Fast and backward stable computation of roots of polynomials, SIAM J. Matrix Anal. Appl., 36, 3, 942-973 (2015) · Zbl 1319.65034
[2] Aurentz, Jared L.; Mach, Thomas; Vandebril, Raf; Watkins, David S., A note on companion pencils. A Panorama of Mathematics: Pure and Applied, Contemp. Math. 658, 91-101 (2016), Amer. Math. Soc., Providence, RI · Zbl 1347.65068
[3] Benner, Peter; Mehrmann, Volker; Xu, Hongguo, Perturbation analysis for the eigenvalue problem of a formal product of matrices, BIT, 42, 1, 1-43 (2002) · Zbl 1003.65032
[4] Betcke, Timo; Higham, Nicholas J.; Mehrmann, Volker; Schr\"oder, Christian; Tisseur, Fran\c{c}oise, NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Software, 39, 2, Art. 7, 28 pp. (2013) · Zbl 1295.65140
[5] Bini, Dario; Meini, Beatrice, On the solution of a nonlinear matrix equation arising in queueing problems, SIAM J. Matrix Anal. Appl., 17, 4, 906-926 (1996) · Zbl 0861.65040
[6] Bini, Dario A.; Noferini, Vanni, Solving polynomial eigenvalue problems by means of the Ehrlich-Aberth method, Linear Algebra Appl., 439, 4, 1130-1149 (2013) · Zbl 1281.65061
[7] bojanczyk1992periodic A. W. Bojanczyk, G. H. Golub, and P. Van Dooren, Periodic Schur decomposition: algorithms and applications, in San Diego’92, International Society for Optics and Photonics, 1992, pp. 31-42.
[8] Ca16 T. R. Cameron and N. I. Steckley, On the application of Laguerre’s method to the polynomial eigenvalue problem, Arxiv:1703.08767, 2017.
[9] Delvaux, Steven; Frederix, Katrijn; Van Barel, Marc, An algorithm for computing the eigenvalues of block companion matrices, Numer. Algorithms, 62, 2, 261-287 (2013) · Zbl 1260.65024
[10] DoLaPeVD16 F. M. Dopico, P. Lawrence, J. P\'erez, and P. Van Dooren, Block Kronecker linearizations of matrix polynomials and their backward errors, Tech. Rep. 2016.34, Manchester Institute for Mathematical Sciences, School of Mathematics, The University of Manchester, 2016. · Zbl 1416.65094
[11] Edelman, Alan; Murakami, H., Polynomial roots from companion matrix eigenvalues, Math. Comp., 64, 210, 763-776 (1995) · Zbl 0833.65041
[12] Effenberger, Cedric; Kressner, Daniel, Chebyshev interpolation for nonlinear eigenvalue problems, BIT, 52, 4, 933-951 (2012) · Zbl 1263.65048
[13] Eidelman, Yuli; Gohberg, Israel; Haimovici, Iulian, Separable Type Representations of Matrices and Fast Algorithms. Vol. 2, Operator Theory: Advances and Applications 235, xii+359 pp. (2014), Birkh\"auser/Springer Basel AG, Basel · Zbl 1280.65034
[14] Francis, J. G. F., The \(QR\) transformation: a unitary analogue to the \(LR\)transformation. I, Comput. J., 4, 265-271 (1961/1962) · Zbl 0104.34304
[15] Francis, J. G. F., The \(QR\) transformation. II, Comput. J., 4, 332-345 (1961/1962) · Zbl 0104.34304 · doi:10.1093/comjnl/4.4.332
[16] Ga74 F. R. Gantmacher, The Theory of Matrices, Vol II, Chelsea, New York, USA, 1974.
[17] Gohberg, I.; Lancaster, P.; Rodman, L., Matrix Polynomials, Classics in Applied Mathematics 58, xxiv+409 pp. (2009), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1170.15300
[18] Higham, Nicholas J., Accuracy and Stability of Numerical Algorithms, xxviii+688 pp. (1996), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0847.65010
[19] Higham, Nicholas J.; Mackey, D. Steven; Tisseur, Fran\c{c}oise, The conditioning of linearizations of matrix polynomials, SIAM J. Matrix Anal. Appl., 28, 4, 1005-1028 (2006) · Zbl 1131.65034
[20] Lancaster, Peter, Lambda-Matrices and Vibrating Systems, xx+193 pp. (2002), Dover Publications, Inc., Mineola, NY · Zbl 1048.34002
[21] Mach, Thomas; Vandebril, Raf, On deflations in extended QR algorithms, SIAM J. Matrix Anal. Appl., 35, 2, 559-579 (2014) · Zbl 1301.65025
[22] Mackey, D. Steven; Mackey, Niloufer; Mehl, Christian; Mehrmann, Volker, Structured polynomial eigenvalue problems: good vibrations from good linearizations, SIAM J. Matrix Anal. Appl., 28, 4, 1029-1051 (2006) · Zbl 1132.65028
[23] Mackey, D. Steven; Mackey, Niloufer; Mehl, Christian; Mehrmann, Volker, Vector spaces of linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl., 28, 4, 971-1004 (2006) · Zbl 1132.65027
[24] Moler, C. B.; Stewart, G. W., An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal., 10, 241-256 (1973) · Zbl 0253.65019
[25] Ro15b L. Robol, Exploiting rank structures for the numerical treatment of matrix polynomials, PhD thesis, University of Pisa, Italy, 2015.
[26] Tisseur, Fran\c{c}oise, Backward error and condition of polynomial eigenvalue problems, Linear Algebra Appl.. Proceedings of the International Workshop on Accurate Solution of Eigenvalue Problems (University Park, PA, 1998), 309, 1-3, 339-361 (2000) · Zbl 0955.65027
[27] Van Barel, Marc, Designing rational filter functions for solving eigenvalue problems by contour integration, Linear Algebra Appl., 502, 346-365 (2016) · Zbl 1386.65115
[28] Vandebril, Raf, Chasing bulges or rotations? A metamorphosis of the QR-algorithm, SIAM J. Matrix Anal. Appl., 32, 1, 217-247 (2011) · Zbl 1218.65035
[29] Vandebril, Raf; Watkins, David S., An extension of the QZ algorithm beyond the Hessenberg-upper triangular pencil, Electron. Trans. Numer. Anal., 40, 17-35 (2013) · Zbl 1288.65053
[30] Watkins, David S., Product eigenvalue problems, SIAM Rev., 47, 1, 3-40 (2005) · Zbl 1075.65055
[31] Watkins, David S., The matrix eigenvalue problem, x+442 pp. (2007), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1142.65038 · doi:10.1137/1.9780898717808
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.