Acceleration of inexact inverse iteration for eigenvalue problems

Abstract

Many methods have been used to improve the efficiency of iterative numerical algorithms. Combining different methods is not always possible because the performance of acceleration methods usually depends critically on the precise form of the error in successive iterates, and this form often changes when other acceleration methods are used. Inexact implementation methods have proved particularly effective in increasing the efficiency of iterations involving sparse matrices. This article investigates the extent to which the efficiency of inexact inverse iteration and the inexact Rayleigh quotient algorithm, for the numerical computation of eigenvalues and eigenvectors of sparse matrices, may be further increased by the use of the scalar epsilon algorithm, a classical extrapolation technique. Some encouraging numerical results are presented and some pointers are given for future research. References

• A. L. Andrew. The accuracy of Numerov's method for eigenvalues. BIT, 26:251--253 1986. doi:10.1007/BF01933751
• A. L. Andrew and R. C. E. Tan. Iterative computation of derivatives of repeated eigenvalues and the corresponding eigenvectors. Numer. Linear Algebra Appl., 7:151--167, 2000. MR2001g:65036 doi:10.1002/1099-1506(200005)7:4<151::AID-NLA191>3.0.CO;2-M
• O. Axelsson. A survey of preconditioned iterative methods for linear systems of algebraic equations. BIT, 25:166--187, 1985. doi:10.1007/BF01934996
• Z.-J. Bai, R. H. Chan and B. Morini. An inexact Cayley transform method for inverse eigenvalue problems. Inverse Problems, 20:1675--1689, 2004. doi:10.1088/0266-5611/20/5/022
• J. Berns-Mueller, I. G. Graham and A. Spence. Inexact inverse iteration for symmetric matrices. Linear Algebra Appl., 416:389--413, 2006. doi:10.1016/j.laa.2005.11.019
• A. Bouras and V. Fraysse. Inexact matrix-vector products in Krylov methods for solving linear systems: a relaxation strategy. SIAM J. Matrix Anal. Appl., 26:660--678 2005. doi:10.1137/S0895479801384743
• C. Brezinski. Computation of the eigenelements of a matrix by the $\varepsilon $-algorithm. Linear Algebra Appl., 11:7--20, 1975. doi:10.1016/0024-3795(75)90113-5
• C. Brezinski and M. Redivo Zaglia. Extrapolation Methods: Theory and Practice. North Holland: Amsterdam, 1991.
• P. Deuflhard. Newton Methods for Nonlinear Problems. Affine invariance and adaptive algorithms. Springer-Verlag: Berlin, 2004.
• A. M. Erisman, R. G. Grimes, J. G. Lewis, W. G. Poole, Jr. and H. D. Simon. Evaluation of orderings for unsymmetric sparse matrices, SIAM J. Sci. Comput., 8:600-624, 1987. doi:10.1137/0908054
• M. A. Freitag and A. Spence. Convergence theory for inexact inverse iteration applied to the generalised nonsymmetric eigenproblem, ETNA 28:40--64, 2007. http://etna.mcs.kent.edu/
• M. A. Freitag and A. Spence. Rayleigh quotient iteration and simplified Jacobi--Davidson method with preconditioned iterative solves, Linear Algebra Appl., 428:2049--2060, 2008. doi:10.1016/j.laa.2007.11.013
• M. A. Freitag and A. Spence. A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems, IMA J. Numer. Anal., 28:522--551, 2008. doi:10.1093/imanum/drm036
• G. H. Golub and Q. Ye. Inexact inverse iteration for generalized eigenvalue problems, BIT, 40:671--684, 2000. doi:10.1023/A:1022388317839
• I. C. F. Ipsen. Computing an eigenvector with inverse iteration, SIAM Review, 39:254--291, 1997. doi:10.1137/S0036144596300773
• Y. L. Lai, K. Y. Lin and W. W. Lin. An inexact inverse iteration for large sparse eigenvalue problems, Numer. Linear Algebra Appl., 4:425-437, 1997. MR98f:65042 doi:10.1002/(SICI)1099-1506(199709/10)4:5<425::AID-NLA117>3.0.CO;2-G
• Matrix Market. [Online] http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/cirphys/jpwh_991.html
• S. G. Nash. A survey of truncated-Newton methods. J. Comput. Appl. Math. 124:45--59 2000. doi:10.1016/S0377-0427(00)00426-X
• Y. Notay. Convergence analysis of inexact Rayleigh quotient iteration. SIAM J. Matrix Anal. Appl. 24:627--644, 2003. doi:10.1137/S0895479801399596
• V. Simoncini. Variable accuracy of matrix-vector products in projection methods for eigencomputation. SIAM J. Numer. Anal., 43:1155--1174, 2005. doi:10.1137/040605333
• V. Simoncini and L. Elden. Inexact Rayleigh quotient-type methods for eigenvalue computations. BIT, 42:159--182, 2002. doi:10.1023/A:1021930421106
• P. Smit and M. H. C. Paardekooper. The effects of inexact solvers in algorithms for symmetric eigenvalue problems, Linear Algebra Appl. 287:337--357, 1999. doi:10.1016/S0024-3795(98)10201-X
• H. A. Van der Vorst. {Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems.} SIAM J. Sci. Comput. 13:631-644, 1992. doi:10.1137/0913035
• M. Waechter. Survey on inexact inverse iteration for eigenvalue problems Technical Report: Centre for Industrial Mathematics, National University of Singapore, 2005.
• J. H. Wilkinson. The Algebraic Eigenvalue Problem. Clarendon Press: Oxford, 1965.
• P. Wynn. On a device for computing the $e_m(S_n)$ transfromation. Math. Tables Aids Comput., 10:91--96, 1956. MR18,801e