Sven Hammarling
Abstract
We develop a new algorithm for the computation of all the eigenvalues and optionally the right and left eigenvectors of dense quadratic matrix polynomials. It incorporates scaling of the problem parameters prior to the computation of eigenvalues, a choice of linearization with favorable conditioning and backward stability properties, and a preprocessing step that reveals and deflates the zero and infinite eigenvalues contributed by singular leading and trailing matrix coefficients. The algorithm is backward-stable for quadratics that are not too heavily damped. Numerical experiments show that our MATLAB implementation of the algorithm, quadeig, outperforms the MATLAB function polyeig in terms of both stability and efficiency.
- Amiraslani, A., Corless, R. M., and Lancaster, P. 2009. Linearization of matrix polynomials expressed in polynomial bases. IMA J. Numer. Anal. 29, 141--157.Google Scholar
Cross Ref
- Antoniou, E. N. and Vologiannidis, S. 2004. A new family of companion forms of polynomial matrices Electron. J. Linear Algebra 11, 78--87.Google ScholarCross Ref
- Antoniou, E. N. and Vologiannidis, S. 2006. Linearizations of polynomial matrices with symmetries and their applications. Electron. J. Linear Algebra 15, 107--114.Google ScholarCross Ref
- Betcke, T. 2008. Optimal scaling of generalized and polynomial eigenvalue problems. SIAM J. Matrix Anal. Appl. 30, 4, 1320--1338. Google ScholarDigital Library
- Betcke, T., Higham, N. J., Mehrmann, V., Schröder, C., and Tisseur, F. 2013. NLEVP: A collection of nonlinear eigenvalue problems. ACM Trans. Math. Softw. 39, 2, Article 7. Google ScholarDigital Library
- Chandrasekaran, S. and Ipsen, I. C. F. 1994. On rank-revealing factorisations. SIAM J. Matrix Anal. Appl. 15, 2, 592--622. Google ScholarDigital Library
- Dedieu, J.-P. and Tisseur, F. 2003. Perturbation theory for polynomial eigenvalue problems in homogeneous form. Linear Algebra Appl. 358, 1--3, 71--94.Google ScholarCross Ref
- Fan, H.-Y., Lin, W.-W., and Van Dooren, P. 2004. Normwise scaling of second order polynomial matrices. SIAM J. Matrix Anal. Appl. 26, 1, 252--256. Google ScholarDigital Library
- Gaubert, S. and Sharify, M. 2009. Tropical scaling of polynomial matrices. In Lecture Notes in Control and Information Sciences, vol. 389, Springer, Berlin, 291--303.Google Scholar
- Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations 3rd Ed. Johns Hopkins University Press, Baltimore, MD. Google ScholarDigital Library
- Grammont, L., Higham, N. J., and Tisseur, F. 2011. A framework for analyzing nonlinear eigenproblems and parameterized linear systems. Linear Algebra Appl. 435, 3, 623--640.Google ScholarCross Ref
- Higham, N. J. 1990. Analysis of the Cholesky decomposition of a semi-definite matrix. In Reliable Numerical Computation, M. G. Cox and S. J. Hammarling, Eds., Oxford University Press, 161--185.Google Scholar
- Higham, N. J., Li, R.-C., and Tisseur, F. 2007. Backward error of polynomial eigenproblems solved by linearization. SIAM J. Matrix Anal. Appl. 29, 4, 1218--1241. Google ScholarDigital Library
- Higham, N. J., Mackey, D. S., Mackey, N., and Tisseur, F. 2006. Symmetric linearizations for matrix polynomials. SIAM J. Matrix Anal. Appl. 29, 1, 143--159. Google ScholarDigital Library
- Higham, N. J., Mackey, D. S., and Tisseur, F. 2006. The conditioning of linearizations of matrix polynomials. SIAM J. Matrix Anal. Appl. 28, 4, 1005--1028. Google ScholarDigital Library
- Higham, N. J., Mackey, D. S., Tisseur, F., and Garvey, S. D. 2008. Scaling, sensitivity and stability in the numerical solution of quadratic eigenvalue problems. Int. J. Numer. Methods Eng. 73, 3, 344--360.Google ScholarCross Ref
- Hilliges, A., Mehl, C., and Mehrmann, V. 2004. On the solution of palindromic eigenvalue problems. In Proceedings of the European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS'04). P. Neittaanmaki, et al. Eds. http://www.mit.jyu.fi/eccomas2004/proceedings/proceed. html.Google Scholar
- Kågström, B. and Kressner, D. 2006. Multishift variants of the QZ algorithm with agressive early deflation. SIAM J. Matrix Anal. Appl. 29, 199--227. Google ScholarDigital Library
- Lancaster, P. 2008. Linearization of regular matrix polynomials. Electron. J. Linear Algebra 17, 21--27.Google ScholarCross Ref
- Lancaster, P. and Psarrakos, P. 2005. A note on weak and strong linearizations of regular matrix polynomials. Numerical analysis rep. 470, Manchester Centre for Computational Mathematics, Manchester, UK.Google Scholar
- Lemonnier, D. and Van Dooren, P. M. 2006. Balancing regular matrix pencils. SIAM J. Matrix Anal. Appl. 28, 1, 253--263. Google ScholarDigital Library
- Mackey, D. S., Mackey, N., Mehl, C., and Mehrmann, V. 2006a. Structured polynomial eigenvalue problems: Good vibrations from good linearizations. MIMS EPrint 2006.38, The University of Manchester, UK.Google Scholar
- Mackey, D. S., Mackey, N., Mehl, C., and Mehrmann, V. 2006b. Structured polynomial eigenvalue problems: Good vibrations from good linearizations. SIAM J. Matrix Anal. Appl. 28, 4, 1029--1051. Google ScholarDigital Library
- Mackey, D. S., Mackey, N., Mehl, C., and Mehrmann, V. 2006c. Vector spaces of linearizations for matrix polynomials. SIAM J. Matrix Anal. Appl. 28, 4, 971--1004. Google ScholarDigital Library
- Moler, C. B. and Stewart, G. W. 1973. An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10, 2, 241--256.Google ScholarDigital Library
- NAG Toolbox for MATLAB. NAG Ltd., Oxford. http://www.nag.co.uk/.Google Scholar
- Tisseur, F. 2000. Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl. 309, 339--361.Google ScholarCross Ref
- Tisseur, F. and Meerbergen, K. 2001. The quadratic eigenvalue problem. SIAM Rev. 43, 2, 235--286. Google ScholarDigital Library
- Watkins, D. S. 2000. Performance of the QZ algorithm in the presence of infinite eigenvalues. SIAM J. Matrix Anal. Appl. 22, 364--375. Google ScholarDigital Library
Index Terms
- An algorithm for the complete solution of quadratic eigenvalue problems
Recommendations
Locking and Restarting Quadratic Eigenvalue Solvers
This paper studies the solution of quadratic eigenvalue problems by the quadratic residual iteration method. The focus is on applications arising from finite-element simulations in acoustics. One approach is the shift-and-invert Arnoldi method applied to ...
The Quadratic Eigenvalue Problem
We survey the quadratic eigenvalue problem, treating its many applications, its mathematical properties, and a variety of numerical solution techniques. Emphasis is given to exploiting both the structure of the matrices in the problem (dense, sparse, ...
The Conditioning of Linearizations of Matrix Polynomials
The standard way of solving the polynomial eigenvalue problem of degree $m$ in $n\times n$ matrices is to “linearize” to a pencil in $mn\times mn$ matrices and solve the generalized eigenvalue problem. For a given polynomial, $P$, infinitely many ...
Comments