×

Convergence and preconditioning of inexact inverse subspace iteration for generalized eigenvalue problems. (English) Zbl 1437.65028

Let \(A-\lambda B\) be regular matrix pencil (\(\det (A-\lambda B)\neq 0\)), where \(A\) and \(B\) are large and sparse \(n \times n\) matrices, and let \(X\in C^{n \times p}\), \(p\ll n\). The subspace range\((X)\) is a deflating subspace for \(A-\lambda B\) if there exists \(L\in C^{p \times p}\) such that \(AX-BXL=0\).
This paper focuses on the inner iteration that arises in the inexact inverse subspace iteration for computing a small deflating subspace of a large matrix pencil. First, it is shown that the method achieves linear rate of convergence if the inner iteration is performed with increasing accuracy (see, Theorem 1 and Algorithm 1). In Section 3 the authors discussed the use of block-GMRES as inner iteration of Algorithm 1.
The investigations of this paper generalize well-known results by M. Robbé et al. [SIAM J. Matrix Anal. Appl. 31, No. 1, 92–113 (2009; Zbl 1269.65036)]. In particular, it is shown that the preconditioners help to maintain the number of iterations needed by block-GMRES to approximately small constant. Some numerical tests are presented in Section 4.

MSC:

65F50 Computational methods for sparse matrices
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F10 Iterative numerical methods for linear systems
65F08 Preconditioners for iterative methods
15A22 Matrix pencils

Citations:

Zbl 1269.65036

Software:

JDQZ
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems, Software Environ. Tools 11, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 2000.
[2] J. Berns-Müller, I. G. Graham and A. Spence, Inexact inverse iteration for symmetric matrices, Linear Algebra Appl. 416 (2006), no. 2-3, 389-413. · Zbl 1101.65037
[3] J. Berns-Müller and A. Spence, Inexact inverse iteration with variable shift for nonsymmetric generalized eigenvalue problems, SIAM J. Matrix Anal. Appl. 28 (2006), no. 4, 1069-1082. · Zbl 1134.65025
[4] J. Brandts, The Riccati algorithm for eigenvalues and invariant subspaces of matrices with inexpensive action, Linear Algebra Appl. 358 (2003), 335-365. · Zbl 1030.65022
[5] M. A. Freitag and P. Kürschner, Tuned preconditioners for inexact two-sided inverse and Rayleigh quotient iteration, Numer. Linear Algebra Appl. 22 (2015), no. 1, 175-196. · Zbl 1363.65061
[6] M. A. Freitag, P. Kürschner and J. Pestana, GMRES convergence bounds for eigenvalue problems, Comput. Methods Appl. Math. 18 (2018), no. 2, 203-222. · Zbl 1391.65065
[7] M. A. Freitag and A. Spence, Convergence of inexact inverse iteration with application to preconditioned iterative solves, BIT 47 (2007), no. 1, 27-44. · Zbl 1121.65038
[8] M. A. Freitag and A. Spence, Convergence theory for inexact inverse iteration applied to the generalised nonsymmetric eigenproblem, Electron. Trans. Numer. Anal. 28 (2007/08), 40-64. · Zbl 1171.65025
[9] M. A. Freitag and A. Spence, A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems, IMA J. Numer. Anal. 28 (2008), no. 3, 522-551. · Zbl 1151.65030
[10] M. A. Freitag and A. Spence, Rayleigh quotient iteration and simplified Jacobi-Davidson method with preconditioned iterative solves, Linear Algebra Appl. 428 (2008), no. 8-9, 2049-2060. · Zbl 1142.65034
[11] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins University, Baltimore, 1996. · Zbl 0865.65009
[12] G. H. Golub and Q. Ye, Inexact inverse iteration for generalized eigenvalue problems, BIT 40 (2000), no. 4, 671-684. · Zbl 0984.65032
[13] M. Hochbruck and C. Lubich, On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal. 34 (1997), no. 5, 1911-1925. · Zbl 0888.65032
[14] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University, Cambridge, 1985. · Zbl 0576.15001
[15] Y.-L. Lai, K.-Y. Lin and W.-W. Lin, An inexact inverse iteration for large sparse eigenvalue problems, Numer. Linear Algebra Appl. 4 (1997), no. 5, 425-437. · Zbl 0889.65038
[16] R. B. Lehoucq and K. Meerbergen, Using generalized Cayley transformations within an inexact rational Krylov sequence method, SIAM J. Matrix Anal. Appl. 20 (1999), no. 1, 131-148. · Zbl 0931.65035
[17] Y. Notay, Convergence analysis of inexact Rayleigh quotient iteration, SIAM J. Matrix Anal. Appl. 24 (2003), no. 3, 627-644. · Zbl 1045.65032
[18] M. Robbé and M. Sadkane, Riccati-based preconditioner for computing invariant subspaces of large matrices, Numer. Math. 92 (2002), no. 1, 129-159. · Zbl 1004.65057
[19] M. Robbé and M. Sadkane, Exact and inexact breakdowns in the block GMRES method, Linear Algebra Appl. 419 (2006), no. 1, 265-285. · Zbl 1112.65028
[20] M. Robbé, M. Sadkane and A. Spence, Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems, SIAM J. Matrix Anal. Appl. 31 (2009), no. 1, 92-113. · Zbl 1269.65036
[21] Y. Saad, Iterative Methods for Sparse Linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, 2003. · Zbl 1002.65042
[22] V. Simoncini and L. Eldén, Inexact Rayleigh quotient-type methods for eigenvalue computations, BIT 42 (2002), no. 1, 159-182. · Zbl 1003.65033
[23] G. L. G. Sleijpen and H. A. Van der Vorst, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 2, 401-425. · Zbl 0860.65023
[24] G. W. Stewart and J. G. Sun, Matrix Perturbation Theory, Academic Press, Boston, 1990.
[25] F. Xue and H. C. Elman, Convergence analysis of iterative solvers in inexact Rayleigh quotient iteration, SIAM J. Matrix Anal. Appl. 31 (2009), no. 3, 877-899. · Zbl 1201.65060
[26] F. Xue and H. C. Elman, Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation, Linear Algebra Appl. 435 (2011), no. 3, 601-622. · Zbl 1253.65059
[27] Q. Ye and P. Zhang, Inexact inverse subspace iteration for generalized eigenvalue problems, Linear Algebra Appl. 434 (2011), no. 7, 1697-1715. · Zbl 1215.65069
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.