Abstract:
The memory-efficient Two-level Orthogonal Arnoldi method can maintain the similar numerical stability and convergence to the standard Arnoldi method, therefore it becomes an important method to solve quadratic eigenvalue problems. It is inevitable to restart the algorithm in practical applications since the computation and storage continue to increase during the process. The special structure of decomposition puts forward new requirements for the restarted algorithm. In this paper, we analyse the properties of the restarted subspace and propose a restarted method which maintains the special structure. On the basis of that, we use Schur decomposition, exact shifts and refined shifts within the restarted method to obtain three restarted algorithms. Theoretical analysis and numerical results illustrate the efficiency of the restarted algorithms under fixed maximum storage.
. IMPLICITLY RESTARTED TWO-LEVEL ORTHOGONAL ARNOLDI ALGORITHMS[J]. Journal of Numerical Methods and Computer Applicat, 2017, 38(4): 256-270.
[1]
Bai Z, Su Y. SOAR:A Second-order Arnoldi Method for the Solution of the Quadratic Eigenvalue Problem[J]. SIAM J Matrix Anal Appl, 2005, 26(3):640-659.
[2]
Zhu J. Structured Eigenvalue Problems and Quadratic Eigenvalue Problems[D]. PhD thesis, Department of Mathematics, University of California, Berkeley, CA, 2005.
[3]
Su Y, Zhang J, Bai Z. A compact Arnoldi algorithm for Polynomial Eigenvalue Problems[R]. RANMEP2008, 2008.
[4]
Lu D, Su Y, Bai Z. Stability Analysis of the Two-level Orthogonal Arnoldi Procedure[J]. SIAM J Matrix Anal Appl, 2016, 37(1):195-214.
[5]
Zhang Y, Su Y. A memory-efficient model order reduction for time-delay systems[J]. BIT, 2013, 53(4):1047-1073.
[6]
Kressner D, Roman J E. Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis[J]. Numer Linear Algebr, 2014, 21(4):569-588.
[7]
Beeumen R V. Compact rational Krylov methods for nonlinear eigenvalue problems[J]. SIAM J Matrix Anal Appl, 2015, 36(2):820-838.
[8]
Campos C, Roman J E. Parallel Krylov solvers for the polynomial eigenvalue problem in SLEPc[J/OL]. 2015, http://users.dsic.upv.es/jroman/preprints/pepslepc.pdf
[9]
Jia Z, Sun Y. Implicitly Restarted Generalized Second-order Arnoldi Type Algorithms for the Quadratic Eigenvalue Problem[J]. Taiwan J Math, 2015, 19(1):1-30.
[10]
Gong F, Sun Y. A new shift strategy for the implicitly restarted generalized second-order Arnoldi method (in Chinese)[J]. Sci Sin Math, 2017, 47(5):635-650.
[11]
Sorensen D C. Implicit application of polynomial filters in a k-step Arnoldi method[J]. SIAM J Matrix Anal Appl, 1990, 13(1):357-385.
[12]
Jia Z. Polynomial characterizations of the approximate eigenvectors by the refined Arnoldi method and an implicitly restarted refined Arnoldi algorithm[J]. Linear Algebra Appl, 1999, 287(1-3):191-214.
[13]
Jia Z. The refined harmonic Arnoldi method and an implicitly restarted refined algorithm for computing interior eigenpairs of large matrices[J]. Appl Numer Math, 2002, 42(4):489-512.
[14]
Betcke T, Higham N J, Mehrmann V, et al. NLEVP:A Collection of Nonlinear Eigenvalue Problems[J]. ACM TOMS, 2013, 39(2):254-261.
[15]
Tisseur F, Meerbergen K. The Quadratic Eigenvalue Problem[J]. SIAM Rev, 2001, 43(2):235-286.