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

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.

Authors:

• Liping Zhou
• Liang Bao
• Yiqin Lin
• Yimin Wei
• Qinghua Wu

Keywords:

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

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.