Fast and backward stable computation of the eigenvalues and eigenvectors of matrix polynomials
Aurentz J, Mach T, Robol L, Vandebril R, Watkins D S
Computational Mathematics 65L07 FOS: Mathematics Product eigenvalue problem eigenvector Mathematics - Numerical Analysis Algebra and Number Theory Eigenvalues 65F15 Matrix polynomial Eigenvectors Core chasing algorithm Applied Mathematics Numerical Analysis (math.NA) eigenvalue
In the last decade matrix polynomials have been investigated with the primary focus on adequate linearizations and good scaling techniques for computing their eigenvalues and eigenvectors. In this article we propose a new method for computing a factored Schur form of the associated companion pencil. The algorithm has a quadratic cost in the degree of the polynomial and a cubic one in the size of the coefficient matrices. Also the eigenvectors can be computed at the same cost. The algorithm is a variant of Francis's implicitly shifted QR algorithm applied on the companion pencil. A preprocessing unitary equivalence is executed on the matrix polynomial to simultaneously bring the leading matrix coefficient and the constant matrix term to triangular form before forming the companion pencil. The resulting structure allows us to stably factor each matrix of the pencil as a product of k matrices of unitary-plus-rank-one form, admitting cheap and numerically reliable storage. The problem is then solved as a product core chasing eigenvalue problem. A backward error analysis is included, implying normwise backward stability after a proper scaling. Computing the eigenvectors via reordering the Schur form is discussed as well. Numerical experiments illustrate stability and efficiency of the proposed methods.
Source: MATHEMATICS OF COMPUTATION (ONLINE), vol. 88, pp. 313-347
[2] J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, A note on companion pencils, Contemporary Mathematics, 658 (2016), pp. 91{101.
[3] P. Benner, V. Mehrmann, and H. Xu, Perturbation analysis for the eigenvalue problem of a formal product of matrices, BIT Numerical Mathematics, 42 (2002), pp. 1{43.
[4] T. Betcke, N. J. Higham, V. Mehrmann, C. Schroder, and F. Tisseur, NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Software, 39 (2013), pp. 7:1{ 7:28.
[5] D. Bini and B. Meini, On the solution of a nonlinear matrix equation arising in queueing problems, SIAM Journal on Matrix Analysis and Applications, 17 (1996), pp. 906{926.
[6] D. A. Bini and V. Noferini, Solving polynomial eigenvalue problems by means of the Ehrlich{Aberth method, Linear Algebra and its Applications, 439 (2013), pp. 1130{1149.
[7] 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.
[9] S. Delvaux, K. Frederix, and M. Van Barel, An algorithm for computing the eigenvalues of block companion matrices, Numerical Algorithms, 62 (2012), pp. 261{287.
[10] F. M. Dopico, P. Lawrence, J. Perez, 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.
[11] C. Effenberger and D. Kressner, Chebyshev interpolation for nonlinear eigenvalue problems, BIT Numerical Mathematics, 52 (2012), pp. 933{951.
[12] Y. Eidelman, I. C. Gohberg, and I. Haimovici, Separable Type Representations of Matrices and Fast Algorithms { Volume 2: Eigenvalue Method, no. 235 in Operator Theory: Advances and Applications, Springer Basel, 2013.
[13] J. G. F. Francis, The QR Transformation a unitary analogue to the LR transformation{ Part 1, The Computer Journal, 4 (1961), pp. 265{271.
[14] , The QR Transformation{Part 2, The Computer Journal, 4 (1962), pp. 332{345.
[15] F. R. Gantmacher, The Theory of Matrices, Vol II, Chelsea, New York, 1974.
[16] I. Gohberg, P. Lancaster, and L. Rodman, Matrix polynomials, vol. 58, Siam, 1982.
[17] N. J. Higham, Accuracy and Stability of numerical algorithms, SIAM, 1996.
[18] N. J. Higham, D. S. Mackey, and F. Tisseur, The conditioning of linearizations of matrix polynomials, SIAM Journal on Matrix Analysis and Applications, 28 (2006), pp. 1005{1028.
[19] P. Lancaster, Lambda-matrices and vibrating systems, Courier Corporation, 2002.
[20] D. S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann, Structured polynomial eigenvalue problems: good vibrations from good linearizations, SIAM Journal on Matrix Analysis and Applications, 28 (2006), pp. 1029{1051.
[21] , Vector spaces of linearizations for matrix polynomials, SIAM Journal on Matrix Analysis and Applications, 28 (2006), pp. 971{1004.
[22] C. B. Moler and G. W. Stewart, An algorithm for generalized matrix eigenvalue problems, SIAM Journal on Numerical Analysis, 10 (1973), pp. 241{256.
[23] L. Robol, Exploiting rank structures for the numerical treatment of matrix polynomials, PhD thesis, University of Pisa, Italy, 2015.
[24] F. Tisseur, Backward error and condition of polynomial eigenvalue problems, Linear Algebra and its Applications, 309 (2000).
[25] M. Van Barel, Designing rational lter functions for solving eigenvalue problems by contour integration, Linear Algebra and its Applications, 502 (2016), pp. 346{365.
[26] R. Vandebril, Chasing bulges or rotations? A metamorphosis of the QR-algorithm, SIAM Journal on Matrix Analysis and Applications, 32 (2011), pp. 217{247.
[27] R. Vandebril and D. S. Watkins, An extension of the QZ algorithm beyond the Hessenberg-upper triangular pencil, Electronic Transactions on Numerical Analysis, 40 (2012), pp. 17{35.
[28] D. S. Watkins, Product eigenvalue problems, SIAM Review, 47 (2005), pp. 3{40. , The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods, SIAM, Philadelphia, USA, 2007.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:385202,
title = {Fast and backward stable computation of the eigenvalues and eigenvectors of matrix polynomials},
author = {Aurentz J and Mach T and Robol L and Vandebril R and Watkins D S},
doi = {10.1090/mcom/3338 and 10.48550/arxiv.1611.10142},
year = {2019}
}
0000-0002-6545-1748Bibliographic record
Deposited version
DOI
10.1090/mcom/3338
10.48550/arxiv.1611.10142
