More Web Proxy on the site http://driver.im/

research-article

An algorithm for the complete solution of quadratic eigenvalue problems

Authors:

Sven Hammarling,

Christopher J. Munro,

Françoise TisseurAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 39, Issue 3

Article No.: 18, Pages 1 - 19

https://doi.org/10.1145/2450153.2450156

Published: 03 May 2013 Publication History

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.

References

[1]

Amiraslani, A., Corless, R. M., and Lancaster, P. 2009. Linearization of matrix polynomials expressed in polynomial bases. IMA J. Numer. Anal. 29, 141--157.

[2]

Antoniou, E. N. and Vologiannidis, S. 2004. A new family of companion forms of polynomial matrices Electron. J. Linear Algebra 11, 78--87.

[3]

Antoniou, E. N. and Vologiannidis, S. 2006. Linearizations of polynomial matrices with symmetries and their applications. Electron. J. Linear Algebra 15, 107--114.

[4]

Betcke, T. 2008. Optimal scaling of generalized and polynomial eigenvalue problems. SIAM J. Matrix Anal. Appl. 30, 4, 1320--1338.

Digital Library

[5]

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.

Digital Library

[6]

Chandrasekaran, S. and Ipsen, I. C. F. 1994. On rank-revealing factorisations. SIAM J. Matrix Anal. Appl. 15, 2, 592--622.

Digital Library

[7]

Dedieu, J.-P. and Tisseur, F. 2003. Perturbation theory for polynomial eigenvalue problems in homogeneous form. Linear Algebra Appl. 358, 1--3, 71--94.

[8]

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.

Digital Library

[9]

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.

[10]

Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations 3rd Ed. Johns Hopkins University Press, Baltimore, MD.

Digital Library

[11]

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.

[12]

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.

[13]

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.

Digital Library

[14]

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.

Digital Library

[15]

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.

Digital Library

[16]

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.

[17]

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.

[18]

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.

Digital Library

[19]

Lancaster, P. 2008. Linearization of regular matrix polynomials. Electron. J. Linear Algebra 17, 21--27.

[20]

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.

[21]

Lemonnier, D. and Van Dooren, P. M. 2006. Balancing regular matrix pencils. SIAM J. Matrix Anal. Appl. 28, 1, 253--263.

Digital Library

[22]

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.

[23]

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.

Digital Library

[24]

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.

Digital Library

[25]

Moler, C. B. and Stewart, G. W. 1973. An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10, 2, 241--256.

Digital Library

[26]

NAG Toolbox for MATLAB. NAG Ltd., Oxford. http://www.nag.co.uk/.

[27]

Tisseur, F. 2000. Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl. 309, 339--361.

[28]

Tisseur, F. and Meerbergen, K. 2001. The quadratic eigenvalue problem. SIAM Rev. 43, 2, 235--286.

Digital Library

[29]

Watkins, D. S. 2000. Performance of the QZ algorithm in the presence of infinite eigenvalues. SIAM J. Matrix Anal. Appl. 22, 364--375.

Digital Library

Cited By

Gao LFeng F(2024)Solving the Scattering and Reflecting Properties of Guided Waves in CFRP under Arbitrary Oblique Incidence Based on Spectral MethodJournal of Physics: Conference Series10.1088/1742-6596/2822/1/0121122822:1(012112)Online publication date: 1-Sep-2024
https://doi.org/10.1088/1742-6596/2822/1/012112
Yang ZLai SYang JLiu AFu J(2024)Coupled dynamic instability of graphene platelet-reinforced dielectric porous arches under electromechanical loadingThin-Walled Structures10.1016/j.tws.2023.111534197(111534)Online publication date: Apr-2024
https://doi.org/10.1016/j.tws.2023.111534
Meyer-Gohde ASaecker J(2024)Solving linear DSGE models with Newton methodsEconomic Modelling10.1016/j.econmod.2024.106670133(106670)Online publication date: Apr-2024
https://doi.org/10.1016/j.econmod.2024.106670
Show More Cited By

Index Terms

An algorithm for the complete solution of quadratic eigenvalue problems
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 39, Issue 3

April 2013

149 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2450153

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 May 2013

Accepted: 01 September 2012

Revised: 01 May 2012

Received: 01 December 2011

Published in TOMS Volume 39, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
584
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)6

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gao LFeng F(2024)Solving the Scattering and Reflecting Properties of Guided Waves in CFRP under Arbitrary Oblique Incidence Based on Spectral MethodJournal of Physics: Conference Series10.1088/1742-6596/2822/1/0121122822:1(012112)Online publication date: 1-Sep-2024
https://doi.org/10.1088/1742-6596/2822/1/012112
Yang ZLai SYang JLiu AFu J(2024)Coupled dynamic instability of graphene platelet-reinforced dielectric porous arches under electromechanical loadingThin-Walled Structures10.1016/j.tws.2023.111534197(111534)Online publication date: Apr-2024
https://doi.org/10.1016/j.tws.2023.111534
Meyer-Gohde ASaecker J(2024)Solving linear DSGE models with Newton methodsEconomic Modelling10.1016/j.econmod.2024.106670133(106670)Online publication date: Apr-2024
https://doi.org/10.1016/j.econmod.2024.106670
Meyer-Gohde A(2024)Solving Linear DSGE Models with Bernoulli IterationsComputational Economics10.1007/s10614-024-10708-zOnline publication date: 26-Sep-2024
https://doi.org/10.1007/s10614-024-10708-z
Liu CKuo CChang C(2023)Regularized Normalization Methods for Solving Linear and Nonlinear Eigenvalue ProblemsMathematics10.3390/math1118399711:18(3997)Online publication date: 20-Sep-2023
https://doi.org/10.3390/math11183997
Hawkins RKhalid MSmetana KTrampert J(2023)Model order reduction for seismic waveform modelling: inspiration from normal modesGeophysical Journal International10.1093/gji/ggad195234:3(2255-2283)Online publication date: 9-May-2023
https://doi.org/10.1093/gji/ggad195
Sadkane M(2023)A note on the computation of invariant pairs of quadratic matrix polynomialsJournal of Computational and Applied Mathematics10.1016/j.cam.2023.115334(115334)Online publication date: May-2023
https://doi.org/10.1016/j.cam.2023.115334
Liu CKuo CChang C(2022)Free Vibrations of Multi-Degree Structures: Solving Quadratic Eigenvalue Problems with an Excitation and Fast Iterative Detection MethodVibration10.3390/vibration50400535:4(914-935)Online publication date: 18-Dec-2022
https://doi.org/10.3390/vibration5040053
Drmač ZGlibić I(2022)An Algorithm for the Complete Solution of the Quartic Eigenvalue ProblemACM Transactions on Mathematical Software10.1145/349452848:1(1-34)Online publication date: 16-Feb-2022
https://dl.acm.org/doi/10.1145/3494528
Dopico FQuintana MDooren P(2022)Strongly Minimal Self-Conjugate Linearizations for Polynomial and Rational MatricesSIAM Journal on Matrix Analysis and Applications10.1137/21M145354243:3(1354-1381)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1137/21M1453542
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents