C. Kristopher Garrett
Zhaojun Bai
Abstract
A variation of Kublanovskaya's nonlinear QR method for solving banded nonlinear eigenvalue problems is presented in this article. The new method is iterative and specifically designed for problems too large to use dense linear algebra techniques. For the unstructurally banded nonlinear eigenvalue problem, a new data structure is used for storing the matrices to keep memory and computational costs low. In addition, an algorithm is presented for computing several nearby nonlinear eigenvalues to already-computed ones. Finally, numerical examples are given to show the efficacy of the new methods, and the source code has been made publicly available.
- T. Betcke, N. J. Higham, V. Mehrmann, C. Schröder, and F. Tisseur. 2008. NLEVP: A Collection of Nonlinear Eigenvalue Problems. MIMS EPrint 2008.40, Manchester Institute for Mathematical Sciences, The University of Manchester, UK, Apr. 2008.Google Scholar
- T. Betcke, N. J. Higham, V. Mehrmann, C. Schröder, and F. Tisseur. 2013. NLEVP: A collection of nonlinear eigenvalue problems. ACM Trans. Math. Softw. 39 (2013), 7:1--7:28. Google ScholarDigital Library
- T. Chan. 1987. Rank-revealing QR factorizations, Linear Algebr. Appl. 88/89 (1987), 67--82.Google ScholarCross Ref
- S. Chandrasekaran and I. C. F. Ipsen. 1994. On rank-revealing factorisations. SIAM J. Matrix Anal. Appl. 15 (1994), 592--622. Google ScholarDigital Library
- J. Demmel. 1997. Applied Numerical Linear Algebra. SIAM, Philadelphia, PA, 1997. Google ScholarDigital Library
- L. Foster. 1986. Rank and Null Space Calculations using Matrix. Decomposition Without Column Interchanges. Linear Algebr. Appl. 74 (1986), 47--71.Google ScholarCross Ref
- C. K. Garrett and R.-C. Li. 2013. Unstructurally Banded Nonlinear. Eigenvalue Solver Software, http://www.csm.ornl.gov/newsite/software.html, (2013).Google Scholar
- G. H. Golub and C. F. Van Loan. 1996. Matrix Computations, 3rd ed. John Hopkins University Press, Baltimore, MD, 1996. Google ScholarDigital Library
- M. Gu and S. C. Eisenstat. 1996. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM J. Sci. Comput. 17 (1996), 848--869. Google ScholarDigital Library
- S. Güttel, R. Van Beeumen, K. Meerbergen, and W. Michiels. 2014. NLEIGS: A Class of Fully Rational Krylov Methods for Nonlinear Eigenvalue Problems. SIAM J. Sci. Comput. 36(6) (2014), A2842--A2864.Google Scholar
- Y. P. Hong and C.-T. Pan. 1992. Rank-Revealing QR Factorizations and the Singular Value Decomposition. Math. Comp. 58 (1992), 213--232.Google Scholar
- X. Huang, Z. Bai, and Y. Su. 2010. Nonlinear Rank-One Modification of the Symmetric Eigenvalue Problem, J. Comp. Math. 28 (2010), 218--234.Google ScholarCross Ref
- N. K. Jain and K. Singhal. 1983. On Kublanovskaya's Approach to the Solution of the Generalized Latent Value Problems for Functional λ-Matrices. SIAM J. Numer. Anal. 20 (1983), 1062--1067.Google ScholarCross Ref
- W. Kahan. 1966. Numerical Linear Algebra. Can. Math. Bull. (1966). 757--801.Google Scholar
- V. N. Kublanovskaya. 1970. On an Approach to the Solution of the Generalized Latent Value Problems for λ-Matrices. SIAM J. Numer. Anal. 7 (1970), 532--537.Google ScholarCross Ref
- R.-C. Li. 1989. QR decomposition and nonlinear eigenvalue problems. Math. Numer. Sinica 11 (1989), 374--385. {in Chinese}Google Scholar
- R.-C. Li. 1992. Compute multiple nonlinear eigenvalues. J. Comp. Math. 10 (1992), 1--20.Google Scholar
- V. Mehrmann and H. Voss. 2004. Nonlinear eigenvalue problems: A challenge for modern eigenvalue methods. GAMM Rep. 27 (2004), 121--152.Google ScholarCross Ref
- G. W. Stewart. 1998. Matrix Algorithms Vol. I: Basic Decompositions. SIAM, Philadelphia, PA, 1998.Google ScholarCross Ref
- D. B. Szyld and F. Xue. 2013. Local Convergence Analysis of Several Inexact Newton-Type Algorithms for General Nonlinear Eigenvalue Problems. Numer. Math. 123 (2013), 333--362. Google ScholarDigital Library
- F. Tisseur and K. Meerbergen. 2001. The quadratic eigenvalue problem. SIAM Rev. 43 (2001), 235--386. Google ScholarDigital Library
- R. Van Beeumen, K. Meerbergen, and W. Michiels. 2015. Compact rational Krylov methods for nonlinear eigenvalue problems. SIAM. J. Matrix Anal. Appl. 36(2) (2015), 820--838.Google Scholar
- H. Voss. 2004. An Arnoldi method for nonlinear eigenvalue problems. BIT Numer Math. 44 (2004), 387--401.Google ScholarDigital Library
- J. H. Wilkinson. 1965. The Algebraic Eigenvalue Problem. Oxford University Press, London, 1965.Google ScholarDigital Library
Index Terms
- A Nonlinear QR Algorithm for Banded Nonlinear Eigenvalue Problems
Recommendations
Compact Two-Sided Krylov Methods for Nonlinear Eigenvalue Problems
We describe a generalization of the compact rational Krylov (CORK) methods for polynomial and rational eigenvalue problems that usually, but not necessarily, come from polynomial or rational approximations of genuinely nonlinear eigenvalue problems. CORK is a ...
A Newton-Type Method with Nonequivalence Deflation for Nonlinear Eigenvalue Problems Arising in Photonic Crystal Modeling
The numerical simulation of the band structure of three-dimensional dispersive metallic photonic crystals with face-centered cubic lattices leads to large-scale nonlinear eigenvalue problems, which are very challenging due to a high-dimensional ...
Compact Rational Krylov Methods for Nonlinear Eigenvalue Problems
We propose a new uniform framework of compact rational Krylov (CORK) methods for solving large-scale nonlinear eigenvalue problems $A(\lambda) x = 0$. For many years, linearizations were used for solving polynomial and rational eigenvalue problems. On the ...
Comments