×

A convergence analysis of the inexact simplified Jacobi-Davidson algorithm for polynomial eigenvalue problems. (English) Zbl 1415.65120

Summary: The simplified Jacobi-Davidson (JD) method is a variant of the JD method without subspace acceleration. If the correction equation is solved approximately, the inexact simplified JD method is obtained. In this paper, we present a new convergence analysis of the inexact simplified JD method. The analysis applies to polynomial eigenvalue problems with simple eigenpairs. We first establish a relationship between the solution of the correction equation and the residual of the approximate eigenpair. From this relationship, we find the difference of two adjacent approximate eigenvalues bounded in terms of the residual norm of the approximate eigenpair. Then we prove the convergence of the inexact simplified JD method in terms of the residual norm of the approximate eigenpair. Depending on how accurately we solve the correction equation, the convergence rate of the inexact simplified JD may take several different forms. Numerical experiments confirm the convergence analysis.

MSC:

65H17 Numerical solution of nonlinear eigenvalue and eigenvector problems
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A22 Matrix pencils
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Asakura, J; Sakurai, T; Tadano, H; Ikegami, T; Kimura, K, A numerical method for polynomial eigenvalue problems using contour integral, Jpn. J. Ind. Appl. Math., 27, 73-90, (2010) · Zbl 1204.65056 · doi:10.1007/s13160-010-0005-x
[2] Balay, S., Brown, J., Buschelman, K., Eijkhout, V., Gropp, W.D., Kaushik, D., Knepley, M.G., McInnes, L.C., Smith, B.F., Zhang, H.: PETSc Users Manual. Argonne National Laboratory, Lemont (2017)
[3] Betcke, T; Higham, NJ; Mehrmann, V; Schröder, C; Tisseur, F, NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Softw., 39, 7:1-7:28, (2013) · Zbl 1295.65140 · doi:10.1145/2427023.2427024
[4] Beyn, W-J, An integral method for solving nonlinear eigenvalue problems, Linear Algebra Appl., 436, 3839-3863, (2012) · Zbl 1237.65035 · doi:10.1016/j.laa.2011.03.030
[5] Boisvert, B., Pozo, R., Remington, K., Miller, B., Lipman, R.: Matrix market. http://math.nist.gov/MatrixMarket (2004) · Zbl 1284.47041
[6] Cai, X-C; Sarkis, M, A restricted additive Schwarz preconditioner for general sparse linear systems, SIAM J. Sci. Comput., 21, 792-797, (1999) · Zbl 0944.65031 · doi:10.1137/S106482759732678X
[7] Effenberger, C; Kressner, D, Chebyshev interpolation for nonlinear eigenvalue problems, BIT, 52, 933-951, (2012) · Zbl 1263.65048 · doi:10.1007/s10543-012-0381-5
[8] Freitag, M; Spence, A, Convergence theory for inexact inverse iteration applied to the generalised nonsymmetric eigenproblem, Electr. Trans. Numer. Anal., 28, 40-64, (2007) · Zbl 1171.65025
[9] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[10] Havé, P; Masson, R; Nataf, F; Szydlarski, M; Xiang, H; Zhao, T, Algebraic domain decomposition methods for highly heterogeneous problems, SIAM J. Sci. Comput., 35, c284-c302, (2013) · Zbl 1278.65189 · doi:10.1137/110842648
[11] Hochstenbach, ME; Sleijpen, GLG, Harmonic and refined Rayleigh-Ritz for the polynomial eigenvalue problem, Numer. Linear Algebra Appl., 15, 35-54, (2008) · Zbl 1212.65150 · doi:10.1002/nla.562
[12] Hochstenbach, ME; Notay, Y, Controlling inner iterations in the Jacobi-Davidson method, SIAM J. Matrix Anal. Appl., 31, 460-477, (2009) · Zbl 1191.65032 · doi:10.1137/080732110
[13] Hwang, F-N; Wei, Z-H; Huang, T-M; Wang, W, A parallel additive Schwarz preconditioned Jacobi-Davidson algorithm for polynomial eigenvalue problems in quantum dot simulation, J. Comput. Phys., 229, 2932-2947, (2010) · Zbl 1187.65034 · doi:10.1016/j.jcp.2009.12.024
[14] Jia, Z; Wang, Z, A convergence analysis of the inexact Rayleigh quotient iteration and simplified Jacobi-Davidson method for the large Hermitian eigenproblem, Sci. China Ser. A Math., 51, 2205-2216, (2008) · Zbl 1179.65039 · doi:10.1007/s11425-008-0050-y
[15] Jia, Z; Li, C, Inner iterations in the shift-invert residual Arnoldi method and the Jacobi-Davidson method, Sci. China Ser. A Math., 57, 1733-1752, (2014) · Zbl 1312.65054 · doi:10.1007/s11425-014-4791-5
[16] Jia, Z; Li, C, Harmonic and refined harmonic shift-invert residual Arnoldi and Jacobi-Davidson methods for interior eigenvalue problems, J. Comput. Appl. Math., 282, 83-97, (2015) · Zbl 1309.65041 · doi:10.1016/j.cam.2014.12.043
[17] Liao, B-S; Bai, Z; Lee, L-Q; Ko, K, Nonlinear Rayleigh-Ritz iterative method for solving large scale nonlinear eigenvalue problems, Taiwan. J. Math., 14, 869-883, (2010) · Zbl 1198.65072 · doi:10.11650/twjm/1500405872
[18] Meerbergen, K; Schröder, C; Voss, H, A Jacobi-Davidson method for two-real-parameter nonlinear eigenvalue problems arising from delay-differential equations, Numer. Linear Algebra Appl., 20, 852-868, (2013) · Zbl 1313.65083 · doi:10.1002/nla.1848
[19] Roman, J.E., Campos, C., Romero, E., Tomas, A.: SLEPc Users Manual v. 3.5.3. Universitat Politècnica de València (2015) · Zbl 1312.65054
[20] Ruhe, A, Rational Krylov sequence methods for eigenvalue computation, Linear Algebra Appl., 58, 391-405, (1984) · Zbl 0554.65025 · doi:10.1016/0024-3795(84)90221-0
[21] Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia (2003) · Zbl 1031.65046 · doi:10.1137/1.9780898718003
[22] Sleijpen, GLG; Booten, AGL; Fokkema, DR; Vorst, H, Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems, BIT, 36, 595-633, (1996) · Zbl 0861.65035 · doi:10.1007/BF01731936
[23] Sleijpen, GLG; Vorst, H, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17, 401-425, (1996) · Zbl 0860.65023 · doi:10.1137/S0895479894270427
[24] Szyld, DB; Xue, F, Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems, Numer. Math., 123, 333-362, (2013) · Zbl 1259.65077 · doi:10.1007/s00211-012-0489-1
[25] Szyld, DB; Xue, F, Local convergence of Newton-like methods for degenerate eigenvalues of nonlinear eigenproblems. I. classical algorithms, Numer. Math., 129, 353-381, (2015) · Zbl 1309.65059 · doi:10.1007/s00211-014-0639-8
[26] Szyld, DB; Xue, F, Local convergence of Newton-like methods for degenerate eigenvalues of nonlinear eigenproblems. II. accelerated algorithms, Numer. Math., 129, 382-403, (2015) · Zbl 1309.65060
[27] Tang, JM; Nabben, R; Vuik, C; Erlangga, YA, Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods, J. Sci. Comput., 39, 340-370, (2009) · Zbl 1203.65073 · doi:10.1007/s10915-009-9272-6
[28] Toselli, A., Widlund, O.: Domain Decomposition Methods: Algorithms and Theory. Springer, Berlin (2005) · Zbl 1069.65138 · doi:10.1007/b137868
[29] Beeumen, R; Meerbergen, K; Michiels, W, A rational Krylov method based on Hermite interpolation for nonlinear eigenvalue problems, SIAM J. Sci. Comput., 35, a327-a350, (2013) · Zbl 1284.47041 · doi:10.1137/120877556
[30] Beeumen, R; Meerbergen, K; Michiels, W, Compact rational Krylov methods for nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl., 36, 820-838, (2015) · Zbl 1319.65042 · doi:10.1137/140976698
[31] Voss, H, A new justification of the Jacobi-Davidson method for large eigenproblems, Linear Algebra Appl., 424, 448-455, (2007) · Zbl 1120.65048 · doi:10.1016/j.laa.2007.02.013
[32] Zhao, T, A spectral analysis of subspace enhanced preconditioners, J. Sci. Comput., 66, 435-457, (2016) · Zbl 1341.65012 · doi:10.1007/s10915-015-0029-0
[33] Zhao, T; Hwang, F-N; Cai, X-C, Parallel two-level domain decomposition based Jacobi-Davidson algorithms for pyramidal quantum dot simulation, Comput. Phys. Commun., 204, 74-81, (2016) · Zbl 1378.65110 · doi:10.1016/j.cpc.2016.03.009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.