×
Jarlebring, Elias; Michiels, Wim; Meerbergen, Karl

A linear eigenvalue algorithm for the nonlinear eigenvalue problem. (English) Zbl 1256.65043

Numer. Math. 122, No. 1, 169-195 (2012).
A nonlinear matrix eigenvalue problem (NMEP) \(T(\lambda)x=0\) is transformed without loss of generality into a standard form \(\lambda B(\lambda)x=x\) (\(T\) and \(B\) analytic in \(\Omega\subset\mathbb{C}\)). This is then transformed into a linear operator eigenvalue problem (LOEP) of the form \(\lambda\mathcal{B}\varphi=\varphi\) (\(\varphi\in C_\infty(\mathbb{R},\mathbb{C}^n)\)). The eigenvalues of \(\mathcal{B}\) in LOEP are the reciprocals of the eigenvalues of \(B\) in the NMEP and the eigenfunction \(\varphi\) in LOEP is related to the NMEP eigenvector \(x\) by \(\varphi(\theta)=xe^{\lambda \theta}\). The classical Arnoldi method is translated in the operator terminology, hence keeping all its nice properties. Because of the definition of \(\mathcal{B}\), starting the Krylov sequence with a constant results in a sequence of (vector) polynomials. Defining an appropriate inner product allows for an efficient implementation. The generated polynomials can be expressed as a linear combination of either monomials or Chebyshev polynomials. Both of these are discussed and presented in algorithmic form and applied to numerical examples like a delay eigenvalue problem with quadratic term or an eigenvalue problem involving square roots.
Reviewer: Adhemar Bultheel (Leuven)

Cited in 4 Reviews
Cited in 34 Documents

MSC:

65H17 Numerical solution of nonlinear eigenvalue and eigenvector problems
65F15 Numerical computation of eigenvalues and eigenvectors of matrices

Keywords:

nonlinear eigenvalue problem; operator eigenvalue problem; Arnoldi algorithm; delay eigenvalue problem; Chebyshev polynomials; Krylov subspace method; numerical examples

Software:

NLEVP; SOAR; Matlab; Chebfun; ARPACK; eigs
Cite Review PDF
Full Text: DOI Link

References:

[1] Arnoldi W.: The principle of minimized iterations in the solution of the matrix eigenvalue problem. Q. Appl. Math. 9, 17–29 (1951) · Zbl 0042.12801
[2] Asakura J., Sakurai T., Tadano H., Ikegami T., Kimura K.: A numerical method for nonlinear eigenvalue problems using contour integrals. JSIAM Lett. 1, 52–55 (2009) · Zbl 1278.65072
[3] Bai Z., Su Y.: SOAR: A second-order Arnoldi method for the solution of the quadratic eigenvalue problem. SIAM J. Matrix Anal. Appl. 26(3), 640–659 (2005) · Zbl 1080.65024 · doi:10.1137/S0895479803438523
[4] Betcke, T., Higham, N.J., Mehrmann, V., Schröder, C., Tisseur, F.: NLEVP: a collection of nonlinear eigenvalue problems. Technical report, University of Manchester (2010) · Zbl 1295.65140
[5] Beyn, W.J.: An integral method for solving nonlinear eigenvalue problems. Linear Algebra Appl. (2011, in press). doi: 10.1016/j.laa.2011.03.030
[6] Breda D., Maset S., Vermiglio R.: Pseudospectral approximation of eigenvalues of derivative operators with non-local boundary conditions. Appl. Numer. Math. 56, 318–331 (2006) · Zbl 1099.65064 · doi:10.1016/j.apnum.2005.04.011
[7] Fassbender H., Mackey D., Mackey N., Schröder C.: Structured polynomial eigenproblems related to time-delay systems. Electron. Trans. Numer. Anal. 31, 306–330 (2008) · Zbl 1188.15007
[8] Gohberg I., Lancaster P., Rodman L.: Matrix polynomials. Academic press, New York (1982) · Zbl 0482.15001
[9] Hale J., Verduyn Lunel S.M.: Introduction to functional differential equations. Springer, Berlin (1993) · Zbl 0787.34002
[10] Hochstenbach M.E., Sleijpen G.L.: Harmonic and refined Rayleigh–Ritz for the polynomial eigenvalue problem. Numer. Linear Algebra Appl. 15(1), 35–54 (2008) · Zbl 1212.65150 · doi:10.1002/nla.562
[11] Jarlebring E., Meerbergen K., Michiels W.: A Krylov method for the delay eigenvalue problem. SIAM J. Sci. Comput. 32(6), 3278–3300 (2010) · Zbl 1226.65069 · doi:10.1137/10078270X
[12] Kressner D.: A block Newton method for nonlinear eigenvalue problems. Numer. Math. 114(2), 355–372 (2009) · Zbl 1191.65054 · doi:10.1007/s00211-009-0259-x
[13] Kressner D., Schröder C., Watkins D.S.: Implicit QR algorithms for palindromic and even eigenvalue problems. Numer. Algorithms 51(2), 209–238 (2009) · Zbl 1181.65054 · doi:10.1007/s11075-008-9226-3
[14] Lehoucq R., Sorensen D., Yang C.: ARPACK user’s guide. Solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM publications, Philadelphia (1998) · Zbl 0901.65021
[15] Liao B.-S., Bai Z., Lee L.-Q., Ko K.: Nonlinear Rayleigh–Ritz iterative method for solving large scale nonlinear eigenvalue problems. Taiwan. J. Math. 14(3), 869–883 (2010) · Zbl 1198.65072
[16] Mackey D., Mackey N., Mehl C., Mehrmann V.: Numerical methods for palindromic eigenvalue problems: Computing the anti-triangular Schur form. Numer. Linear Algebra 16, 63–86 (2009) · Zbl 1224.65099 · doi:10.1002/nla.612
[17] Meerbergen K.: The quadratic Arnoldi method for the solution of the quadratic eigenvalue problem. SIAM J. Matrix Anal. Appl. 30(4), 1463–1482 (2008) · Zbl 1176.65041 · doi:10.1137/07069273X
[18] Mehrmann V., Voss H.: Nonlinear eigenvalue problems: a challenge for modern eigenvalue methods. GAMM Mitteilungen 27, 121–152 (2004) · Zbl 1071.65074
[19] Neumaier A.: Residual inverse iteration for the nonlinear eigenvalue problem. SIAM J. Numer. Anal. 22, 914–923 (1985) · Zbl 0594.65026 · doi:10.1137/0722055
[20] Peters G., Wilkinson J.: Inverse iterations, ill-conditioned equations and Newton’s method. SIAM Rev. 21, 339–360 (1979) · Zbl 0424.65021 · doi:10.1137/1021052
[21] Ruhe A.: Algorithms for the nonlinear eigenvalue problem. SIAM J. Numer. Anal. 10, 674–689 (1973) · Zbl 0261.65032 · doi:10.1137/0710059
[22] Sleijpen G.L., Booten A.G., Fokkema D.R., van der Vorst H.A.: Jacobi–Davidson type methods for generalized eigenproblems and polynomial eigenproblems. BIT 36(3), 595–633 (1996) · Zbl 0861.65035 · doi:10.1007/BF01731936
[23] Su, Y., Bai, Z.: Solving rational eigenvalue problems via linearization. Technical report, Department of Computer Science and Mathematics, University of California, Davis (2008) · Zbl 1222.65034
[24] Trefethen L.N.: Spectral Methods in MATLAB. SIAM Publications, Philadelphia (2000) · Zbl 0953.68643
[25] Unger, H.: Nichtlineare Behandlung von Eigenwertaufgaben. Z. Angew. Math. Mech. 30, 281–282 (1950). English translation: http://www.math.tu-dresden.de/\(\sim\)schwetli/Unger.html · Zbl 0040.06602
[26] Voss H.: An Arnoldi method for nonlinear eigenvalue problems. BIT 44, 387–401 (2004) · Zbl 1066.65059 · doi:10.1023/B:BITN.0000039424.56697.8b
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.