On the backward error incurred by the compact rational Krylov linearization. (English) Zbl 1473.65045

Summary: One of the most successful methods for solving a polynomial (PEP) or rational eigenvalue problem (REP) is to recast it, by linearization, as an equivalent but larger generalized eigenvalue problem which can be solved by standard eigensolvers. In this work, we investigate the backward errors of the computed eigenpairs incurred by the application of the well-received compact rational Krylov (CORK) linearization. Our treatment is unified for the PEPs or REPs expressed in various commonly used bases, including Taylor, Newton, Lagrange, orthogonal, and rational basis functions. We construct one-sided factorizations that relate the eigenpairs of the CORK linearization and those of the PEPs or REPs. With these factorizations, we establish upper bounds for the backward error of an approximate eigenpair of the PEPs or REPs relative to the backward error of the corresponding eigenpair of the CORK linearization. These bounds suggest a scaling strategy to improve the accuracy of the computed eigenpairs. We show, by numerical experiments, that the actual backward errors can be successfully reduced by scaling and the errors, before and after scaling, are both well predicted by the bounds.


65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
Full Text: DOI


[1] Amiraslani, A.; Corless, RM; Lancaster, P., Linearization of matrix polynomials expressed in polynomial bases, IMA J. Numer. Anal., 29, 1, 141-157 (2008) · Zbl 1158.15022
[2] Antoniou, EN; Vologiannidis, S., A new family of companion forms of polynomial matrices, Electr. J. Linear Algebra, 11, 411, 78-87 (2004) · Zbl 1085.15010
[3] Berljafa, M., Güttel, S.: A rational Krylov toolbox for Matlab, MIMS EPrint 2014.56. Manchester Institute for Mathematical Sciences, The University of Manchester, UK pp. 1-21 (2014)
[4] Betcke, T., Optimal scaling of generalized and polynomial eigenvalue problems, SIAM J. Matrix Anal. Appl., 30, 4, 1320-1338 (2008) · Zbl 1176.65038
[5] Betcke, T.; Higham, NJ; Mehrmann, V.; Schröder, C.; Tisseur, F., NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Softw., 39, 7, 1-28 (2013) · Zbl 1295.65140
[6] Driscoll, T.A., Hale, N., Trefethen, L.N.: Chebfun Guide. Pafnuty Publications (2014). http://www.chebfun.org/docs/guide/
[7] Effenberger, C.; Kressner, D., Chebyshev interpolation for nonlinear eigenvalue problems, BIT Numer. Math., 52, 4, 933-951 (2012) · Zbl 1263.65048
[8] Fiedler, M., A note on companion matrices, Linear Algebra App., 372, 325-331 (2003) · Zbl 1031.15014
[9] Gaubert, S., Sharify, M.: Tropical scaling of polynomial matrices. In: Positive systems, pp. 291-303. Springer (2009) · Zbl 1186.15007
[10] Gohberg, I.; Lancaster, P.; Rodman, L., Matrix Polynomials (2009), New York: SIAM, New York · Zbl 1170.15300
[11] Grammont, L.; Higham, NJ; Tisseur, F., A framework for analyzing nonlinear eigenproblems and parametrized linear systems, Linear Algebra Appl., 435, 623-640 (2011) · Zbl 1288.65049
[12] Güttel, S.; Tisseur, F., The nonlinear eigenvalue problem, Acta Numerica, 26, 1-94 (2017) · Zbl 1377.65061
[13] Güttel, S.; Van Beeumen, R.; Meerbergen, K.; Michiels, W., NLEIGS: a class of fully rational Krylov methods for nonlinear eigenvalue problems, SIAM J. Sci. Comput., 36, 6, A2842-A2864 (2014) · Zbl 1321.47128
[14] Higham, NJ; Li, RC; Tisseur, F., Backward error of polynomial eigen problems solved by linearization, SIAM J. Matrix Anal. Appl., 29, 4, 1218-1241 (2007) · Zbl 1159.65042
[15] Hilliges, A., Mehl, C., Mehrmann, V.: On the solution of palindromic eigenvalue problems. In: Proceedings of the 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS). Jyväskylä, Finland (2004)
[16] Karlsson, L.; Tisseur, F., Algorithms for Hessenberg-triangular reduction of Fiedler linearization of matrix polynomials, SIAM J. Sci. Comput., 37, 3, C384-C414 (2015) · Zbl 1320.65056
[17] Lawrence, PW; Corless, RM, Backward error of polynomial eigenvalue problems solved by linearization of Lagrange interpolants, SIAM J. Matrix Anal. Appl., 36, 4, 1425-1442 (2015) · Zbl 1327.65073
[18] Lawrence, PW; Van Barel, M.; Van Dooren, P., Backward error analysis of polynomial eigenvalue problems solved by linearization, SIAM J. Matrix Anal. Appl., 37, 1, 123-144 (2016) · Zbl 1382.65101
[19] Mackey, DS; Mackey, N.; Mehl, C.; Mehrmann, V., Vector spaces of linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl., 28, 4, 971-1004 (2006) · Zbl 1132.65027
[20] Tisseur, F., Backward error and condition of polynomial eigenvalue problems, Linear Algebra Appl., 309, 1-3, 339-361 (2000) · Zbl 0955.65027
[21] Tisseur, F.; Higham, NJ, Structured pseudospectra for polynomial eigenvalue problems, with applications, SIAM J. Matrix Anal. Appl., 23, 1, 187-208 (2001) · Zbl 0996.65042
[22] Van Beeumen, R.; Meerbergen, K.; Michiels, W., Compact rational Krylov methods for nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl., 36, 2, 820-838 (2015) · Zbl 1319.65042
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.