Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory-efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree $d$. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor $d$. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so called Q-Arnoldi and TOAR methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift-and-invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree $30$ arising from the interpolation of nonlinear eigenvalue problems which stem from boundary element discretizations of PDE eigenvalue problems.Daniel Kressner; Román Moltó, JE. (2014). Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis. Numerical Linear Algebra with Applications. 21(4):569-588. doi:10.1002/nla.1913569588214Mackey, D. S., Mackey, N., Mehl, C., & Mehrmann, V. (2006). Vector Spaces of Linearizations for Matrix Polynomials. SIAM Journal on Matrix Analysis and Applications, 28(4), 971-1004. doi:10.1137/050628350Mackey, D. S., Mackey, N., Mehl, C., & Mehrmann, V. (2006). Structured Polynomial Eigenvalue Problems: Good Vibrations from Good Linearizations. SIAM Journal on Matrix Analysis and Applications, 28(4), 1029-1051. doi:10.1137/050628362Higham, N. J., Mackey, D. S., & Tisseur, F. (2006). The Conditioning of Linearizations of Matrix Polynomials. SIAM Journal on Matrix Analysis and Applications, 28(4), 1005-1028. doi:10.1137/050628283Adhikari, B., Alam, R., & Kressner, D. (2011). Structured eigenvalue condition numbers and linearizations for matrix polynomials. Linear Algebra and its Applications, 435(9), 2193-2221. doi:10.1016/j.laa.2011.04.020Bai, Z., & Su, Y. (2005). SOAR: A Second-order Arnoldi Method for the Solution of the Quadratic Eigenvalue Problem. SIAM Journal on Matrix Analysis and Applications, 26(3), 640-659. doi:10.1137/s0895479803438523Meerbergen, K. (2009). The Quadratic Arnoldi Method for the Solution of the Quadratic Eigenvalue Problem. SIAM Journal on Matrix Analysis and Applications, 30(4), 1463-1482. doi:10.1137/07069273xLin, Y., Bao, L., & Wei, Y. (2010). Model-order reduction of large-scalekth-order linear dynamical systems via akth-order Arnoldi method. International Journal of Computer Mathematics, 87(2), 435-453. doi:10.1080/00207160802130164Stewart, G. W. (2001). Matrix Algorithms. doi:10.1137/1.9780898718058Kamiya, N., Andoh, E., & Nogae, K. (1993). Eigenvalue analysis by the boundary element method: new developments. Engineering Analysis with Boundary Elements, 12(3), 151-162. doi:10.1016/0955-7997(93)90011-9Bindel D Hood A Localization theorems for nonlinear eigenvalues. arXiv: 1303.4668 2013Botchev, M. A., Sleijpen, G. L. G., & Sopaheluwakan, A. (2009). An SVD-approach to Jacobi–Davidson solution of nonlinear Helmholtz eigenvalue problems. Linear Algebra and its Applications, 431(3-4), 427-440. doi:10.1016/j.laa.2009.03.024Effenberger, C., & Kressner, D. (2012). Chebyshev interpolation for nonlinear eigenvalue problems. BIT Numerical Mathematics, 52(4), 933-951. doi:10.1007/s10543-012-0381-5Van Beeumen, R., Meerbergen, K., & Michiels, W. (2013). A Rational Krylov Method Based on Hermite Interpolation for Nonlinear Eigenvalue Problems. SIAM Journal on Scientific Computing, 35(1), A327-A350. doi:10.1137/120877556Sitton, G. A., Burrus, C. S., Fox, J. W., & Treitel, S. (2003). Factoring very-high-degree polynomials. IEEE Signal Processing Magazine, 20(6), 27-42. doi:10.1109/msp.2003.1253552Amiraslani, A., Corless, R. M., & Lancaster, P. (2008). Linearization of matrix polynomials expressed in polynomial bases. IMA Journal of Numerical Analysis, 29(1), 141-157. doi:10.1093/imanum/drm051Betcke, T., & Kressner, D. (2011). Perturbation, extraction and refinement of invariant pairs for matrix polynomials. Linear Algebra and its Applications, 435(3), 514-536. doi:10.1016/j.laa.2010.06.029Beyn, W. J., & Thümmler, V. (2010). Continuation of Invariant Subspaces for Parameterized Quadratic Eigenvalue Problems. SIAM Journal on Matrix Analysis and Applications, 31(3), 1361-1381. doi:10.1137/080723107Kressner, D. (2009). A block Newton method for nonlinear eigenvalue problems. Numerische Mathematik, 114(2), 355-372. doi:10.1007/s00211-009-0259-xLehoucq, R. B., Sorensen, D. C., & Yang, C. (1998). ARPACK Users’ Guide. doi:10.1137/1.9780898719628Hernandez, V., Roman, J. E., & Vidal, V. (2005). SLEPc. ACM Transactions on Mathematical Software, 31(3), 351-362. doi:10.1145/1089014.1089019Clenshaw, C. W. (1955). A note on the summation of Chebyshev series. Mathematics of Computation, 9(51), 118-118. doi:10.1090/s0025-5718-1955-0071856-0Stewart, G. W. (2002). A Krylov--Schur Algorithm for Large Eigenproblems. SIAM Journal on Matrix Analysis and Applications, 23(3), 601-614. doi:10.1137/s0895479800371529Su Y A compact Arnoldi algorithm for polynomial eigenvalue problems 2008 http://math.cts.nthu.edu.tw/Mathematics/RANMEP%20Slides/Yangfeng%20Su.pdfSteinbach, O., & Unger, G. (2009). A boundary element method for the Dirichlet eigenvalue problem of the Laplace operator. Numerische Mathematik, 113(2), 281-298. doi:10.1007/s00211-009-0239-1Effenberger, C., Kressner, D., Steinbach, O., & Unger, G. (2012). Interpolation-based solution of a nonlinear eigenvalue problem in fluid-structure interaction. PAMM, 12(1), 633-634. doi:10.1002/pamm.201210305Betcke, T., Higham, N. J., Mehrmann, V., Schröder, C., & Tisseur, F. (2013). NLEVP. ACM Transactions on Mathematical Software, 39(2), 1-28. doi:10.1145/2427023.2427024Grammont, L., Higham, N. J., & Tisseur, F. (2011). A framework for analyzing nonlinear eigenproblems and parametrized linear systems. Linear Algebra and its Applications, 435(3), 623-640. doi:10.1016/j.laa.2009.12.03