Restarted Generalized Second-Order Krylov Subspace Methods for Solving Quadratic Eigenvalue Problems

Authors: Liping Zhou, Liang Bao, Yiqin Lin, Yimin Wei, Qinghua Wu

Abstract:

This article is devoted to the numerical solution of large-scale quadratic eigenvalue problems. Such problems arise in a wide variety of applications, such as the dynamic analysis of structural mechanical systems, acoustic systems, fluid mechanics, and signal processing. We first introduce a generalized second-order Krylov subspace based on a pair of square matrices and two initial vectors and present a generalized second-order Arnoldi process for constructing an orthonormal basis of the generalized second-order Krylov subspace. Then, by using the projection technique and the refined projection technique, we propose a restarted generalized second-order Arnoldi method and a restarted refined generalized second-order Arnoldi method for computing some eigenpairs of largescale quadratic eigenvalue problems. Some theoretical results are also presented. Some numerical examples are presented to illustrate the effectiveness of the proposed methods.

Keywords: Quadratic eigenvalue problem, Generalized secondorder Krylov subspace, Generalized second-order Arnoldi process, Projection technique, Refined technique, Restarting.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1074299

References:

[1] W. E. Arnoldi, The principle of minimized iterations in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9(1951), pp. 17-29.
[2] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, Philadelphia, 2000.
[3] Z. Bai and Y. Su, SOAR: a second-order Arnoldi method for the solution of the quadratic eigenvalue problem, SIAM J. Matrix Anal. Appl., 26(2005), pp. 640-659.
[4] A. Berm'udez, R. G. Dur'an, R. Rodr'─▒guez and J. Solomin, Finite element analysis of a quadratic eigenvalue problem arising in dissipative acoustics, SIAM J. Numer. Anal., 38(2000), pp. 267-91.
[5] J. V. Clark, N. Zhou and K. S. J. Pister, Modified nodal analysis for MEMS with multienergy domains, in International Conference on Modeling and Simulation of Microsystems, Semiconductors, Sensors and Actuators, San Diego, CA, March 27-29, 2000.
[6] R. W. Clough and J. Penzien, Dynamics of Structures, McGraw-Hill, Dusseldorf, 1975.
[7] J. W. Daniel, W. B. Gragg, L. Kaufman, and G. W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comp., 30(1976), pp. 772-795.
[8] C. E. Davila, A subspace approach to estimation of autoregressive parameters from noisy measurements, IEEE Trans. Signal Processing, 46(1998), pp. 531-534.
[9] J. Demmel, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1997.
[10] R. W. Freund and N. M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60(1991), pp. 315-339.
[11] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd edition, Johns Hoplins University Press, Baltimore, 1996.
[12] C.-H. Guo, Numerical solution of a quadratic eigenvalue problem, Linear Algebra Appl., 385(2004), pp. 391-406.
[13] J.-S. Guo, W.-W. Lin and C.-S. Wang, Numerical solutions for large sparse quadratic eigenvalue problems, Linear Algebra Appl., 225(1995), pp. 57-89.
[14] R. S. Heeg and B. J. Geurts, Spatial instabilities of the incompressible attachment-line flow using sparse matrix Jacobi-Davidson techniques, Appl. Sci. Res., 59(1998), pp. 315-329.
[15] A. Hilliges, C. Mehl and V. Mehrmann, On the solution of palindromic eigenvalue problems, in Proceedings of the 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS), Jyv¨askyl¨a, Finland, 2004.
[16] M. E. Hochstenbach and H. A. van der Vorst, Alternatives to the Rayleigh quotient for the quadratic eigenvalue problem, SIAM J. Sci. Comput., 25(2003), pp. 591-603.
[17] U. B. Holz, G. Golub and K. H. Law, A subspace approximation method for the quadratic eigenvalue problem, SIAM J. Matrix Anal. Appl., 26(2005), pp. 498-521.
[18] T.-M. Hwang, W.-W. Lin and V. Mehrmann, Numerical solution of quadratic eigenvalue problems with structure-preserving methods, SIAM J. Sci. Comput., 24(2003), pp. 1283-1302.
[19] T.-M. Huang, W.-W. Lin and J. Qian, Structure-preserving algorithms for palindromic quadratic eigenvalue problems arising from vibration of fast trains, SIAM J. Matrix Anal. Appl., 30(2009), pp. 1566-1592.
[20] Z. Jia, Refined iterative algorithm based on Arnoldi-s process for large unsymmetric eigenproblems, Linear Algebra Appl., 259(1997), pp. 1-23.
[21] Z. Jia, A refined subspace iteration algorithm for large spares eigenproblems, Appl. Numer. Math., 32(2000), pp. 35-52.
[22] J. Lampe and H. Voss, On a quadratic eigenproblem occurring in regularized total least squares, Comput. Stat. Data Anal., 52(2007), pp. 1090-1102.
[23] J. Lampe and H. Voss, Global convergence of RTLSQEP: a solver of regularized total least squares problems via quadratic eigenproblems, Math. Modelling Anal., 13(2008), pp. 55-66.
[24] R. Li and Q. Ye, A Krylov subspace method for quadratic matrix polynomials with application to constrained least squares problems, SIAM J. Matrix Anal. Appl., 25(2003), pp. 405-428.
[25] The MathWorks, Inc., MATLAB 7, September 2004.
[26] K. Meerbergen, Locking and restarting quadratic eigenvalue solvers, SIAM J. Sci. Comput., 22(2001), pp. 1814-1839.
[27] K. Meerbergen, The quadratic Arnoldi method for the solution of the quadratic eigenvalue problem, SIAM J. Matrix Anal. Appl., 30(2008), pp. 1463-1482.
[28] J. Qian and W.-W. Lin, A numerical method for quadratic eigenvalue problems of gyroscopic systems, J. Sound Vibration, 306(2007), pp. 284- 296.
[29] F. A. Raeven, A new Arnoldi approach for polynomial eigenproblems, In Proceedings of the Copper Mountain Conference on Iterative Methods, 1996.
[30] G. X. Ren and Z. C. Zheng, A reformulated Arnoldi algorithm for nonclassically damped eigenvalue problems, Int. J. Numer. Methods Eng., 40(1997), pp. 3537-3555.
[31] A. Ruhe, Numerical aspects of Gramm-Schmidt orthogonalization of vectors, Linear Algebra Appl., 52(1983), pp. 591-601.
[32] Y. Saad, Variations on Arnoldi-s method for computing eigenproblems of large non-Hermitian matrices, Linear Algebra Appl., 34(1980), pp. 269-295.
[33] Y. Saad and M. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7(1986), pp. 856-869.
[34] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM, Philadelphia, 2003.
[35] H. Schmitz, K. Volk and W. L. Wendland, On three-dimensional singularities of elastic fields near vertices, Numer. Methods Partial Differential Equations, 9(1993), pp. 323-337.
[36] G. L. G. Sleijpen, G. L. Booten, D. R. Fokkema and H. A. van der Vorst, Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems, BIT, 36(1996), pp. 595-633.
[37] F. Tisseur, Backward error and condition of polynomial eigenvalue problems, Linear Algebra Appl., 309(2000), pp. 339-361.
[38] F. Tisseur and K. Meerbergen, The quadratic eigenvalue problem, SIAM Review, 43(2001), pp. 235-286.
[39] H. A. van der Vorst, BICGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 13(1992), pp. 631-644.
[40] Q. Ye, An iterated shift-and-invert Arnoldi algorithm for quadratic matrix eigenvalue problems, Appl. Math. Comput., 172(2006), pp. 818- 827.