×

The Jacobi-Davidson method. (English) Zbl 1177.65055

Summary: The Jacobi–Davidson method is a popular technique to compute a few eigenpairs of large sparse matrices. Its introduction, about a decade ago, was motivated by the fact that standard eigensolvers often require an expensive factorization of the matrix to compute interior eigenvalues. Such a factorization may be infeasible for large matrices as arise in today’s large-scale simulations.
In the Jacobi–Davidson method, one still needs to solve “inner” linear systems, but a factorization is avoided because the method is designed so as to favor the efficient use of modern iterative solution techniques, based on preconditioning and Krylov subspace acceleration. Here we review the Jacobi–Davidson method, with the emphasis on recent developments that are important in practical use.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices

Software:

JDQR; JDQZ; JDCG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] ARBENZ, A comparison of solvers for large eigenvalue problems occurring in the design of resonant cavities, Numer. Linear Algebra Appl. 6 (1) pp 3– (1999) · Zbl 0982.65039
[2] ARBENZ, A Jacobi-Davidson method for solving complex symmetric eigenvalue problems, SIAM J. Sci. Comput. 25 (5) pp 1655– (2004) · Zbl 1061.65027
[3] ARNOLDI, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math. 9 pp 17– (1951)
[4] BAI , Z. DEMMEL , J. DONGARRA , J. RUHE , A. VAN DER VORST , H.A. Eds. Templates for the Solution ofAlgebraic Eigenvalue Problems. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. A practical guide.
[5] BARRETT , R. BERRY , M. CHAN , T. DEMMEL , J. DONATO , J. DONGARRA , J. EIJKHOUT , V. POZO , R. ROMINE , C. AND VAN DER VORST , H.A Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. · Zbl 0814.65030
[6] BENZI , M. 2002 418 477
[7] BERGAMASCHI, Computational experience with sequential and parallel, preconditioned Jacobi-Davidson for large, sparse symmetric matrices., J. Comput. Phys. 188 (1) pp 318– (2003) · Zbl 1022.65037
[8] BETCKE, A Jacobi-Davidson-type projection method for nonlinear eigenvalue problems, Future Generation Computer Systems 20 (3) pp 363– (2004)
[9] BOOTEN, Jacobi-Davidson methods for generalized MHD-eigenvalue problems, Z. Angew. Math. Mech. 76 (1) pp 131– (1996)
[10] BRANDTS, The Riccati algorithm for eigenvalues and invariant subspaces of matrices with inexpensive action, Linear Algebra Appl. 358 pp 335– (2003) · Zbl 1030.65022
[11] BRANDTS , J. H. Solving eigenproblems: from Arnoldi via Jacobi-Davidson to the Riccati method. In Numerical methods and applications, vol. 2542 of Lecture Notes in Comput. Sci. Springer, Berlin, 2003, pp. 167-173. · Zbl 1033.65016
[12] DAVIDSON, The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices, J. Comput. Phys. 17 pp 87– (1975) · Zbl 0293.65022
[13] DE STURLER , E. Improving the convergence of the Jacobi-Davidson algorithm. Preprint, Department of Computer Science, University of Illinois at Urbana-Champaign, 2002.
[14] DUPONT, An approximate factorization procedure for solving self-adjoint elliptic difference equations, SIAM J. Numer. Anal. 5 pp 559– (1968) · Zbl 0174.47603
[15] FENG, An integrated Davidson and multigrid solution approach for very large scale symmetric eigenvalue problems, Comput. Methods Appl. Mech. Engrg. 190 (28) pp 3543– (2001) · Zbl 1006.74085
[16] FOKKEMA, Accelerated inexact Newton schemes for large systems of nonlinear equations, SIAM J. Sci. Comput. 19 (2) pp 657– (1998) · Zbl 0916.65050
[17] FOKKEMA, Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM J. Sci. Comput. 20 (1) pp 94– (1998) · Zbl 0924.65027
[18] GENSEBERGER , M. SLEIJPEN , G. L. G. VAN DER VORST , H. A. Using domain decomposition in the Jacobi-Davidson method. Preprint 1164, Department of Mathematics, Utrecht University, October 2000.
[19] GENSEBERGER , M. SLEIJPEN , G. L. G. VAN DER VORST , H. A. An optimized Schwarz method in the Jacobi-Davidson method for eigenvalue problems. In Domain decomposition methods in science and engineering. Natl. Auton. Univ. Mex., México, 2003, pp. 289-296.
[20] GEUS , R. The Jacobi-Davidson algorithm for solving large sparse symmetric eigen- value problems. Phd thesis no. 14734, ETH Zurich, 2002. (Available at URL http://e-collection.ethbib.ethz.ch/show?type=diss&nr=14734).
[21] GOLUB , G. H. VAN LOAN , C. F. Matrix Computations. The John Hopkins University Press, Baltimore, Maryland, 1996. Third ed.
[22] HEEG, Spatial instabilities of the incompressible attachment-line flow using sparse matrix Jacobi-Davidson techniques, Appl. Sci. Res. 59 (4) pp 315– (1998) · Zbl 0915.76025
[23] HEUVELINE, On multigrid methods for the eigenvalue computation of nonselfadjoint elliptic operators, East-West J. Numer. Math. 8 (4) pp 275– (2000)
[24] HOCHSTENBACH, A Jacobi-Davidson type SVD method, SIAM J. Sci. Comput. 23 (2) pp 606– (2001) · Zbl 1002.65048
[25] HOCHSTENBACH, Harmonic and refined extraction methods for the singular value problem, with applications in least squares problems, BIT 44 (4) pp 721– (2004) · Zbl 1079.65047
[26] HOCHSTENBACH , M. E. Generalizations of harmonic and refined Rayleigh-Ritz. Preprint, Dept. Math., Case Western Reserve University, August 2005. Revised version. Submitted. · Zbl 1121.65316
[27] HOCHSTENBACH , M. E. A Jacobi-Davidson type method for the generalized singular value problem. Preprint, Department of Mathematics, Case Western Reserve University, August 2005. Revised version. Submitted.
[28] HOCHSTENBACH, A Jacobi-Davidson type method for the nonsingular two-parameter eigenvalue problem, SIAM J. Matrix Anal. Appl. 26 (2) pp 477– (2005) · Zbl 1077.65036
[29] HOCHSTENBACH, A Jacobi-Davidson type method for a right definite two-parameter eigenvalue problem, SIAM J. Matrix Anal. Appl. 24 (2) pp 392– (2002) · Zbl 1025.65023
[30] HOCHSTENBACH, Two-sided and alternating Jacobi-Davidson, Linear Algebra Appl. 358 (1-3) pp 145– (2003) · Zbl 1087.65035
[31] HOCHSTENBACH , M. E. SLEIJPEN , G. L.G. Harmonic and refined extraction methods for the polynomial eigenvalue problem. Preprint, Department of Mathematics, Case Western Reserve University, August 2005. Revised version. Submitted. · Zbl 1212.65150
[32] HWANG, Numerical solution of quadratic eigenvalue problems with structure-preserving methods, SIAM J. Sci. Comput. 24 (4) pp 1283– (2003) · Zbl 1048.65035
[33] HWANG, Numerical simulation of three dimensional pyramid quantum dot, J. Comput. Phys. 196 (1) pp 208– (2004) · Zbl 1053.81018
[34] JACOBI , C. G. J. Über eine neue Auflösungsart der bei der Methode der kleinsten Quadrate vorkommende linearen Gleichungen. Astronom. Nachr. (1845), 297-306.
[35] JACOBI, Über ein leichtes Verfahren, die in der Theorie der Säcularstörungen vorkommenden Gleichungen numerisch aufzulösen, J. Reine und Angew. Math. pp 51– (1846) · ERAM 030.0852cj
[36] JDCG code, available via http://homepages.ulb.ac.be/ ynotay/.
[37] JDQR and JDQZ codes, available via http://www.math.uu.nl/people/sleijpen.
[38] JIA, Refined iterative algorithms based on Arnoldi’s process for large unsymmetric eigenproblems, Linear Algebra Appl. 259 pp 1– (1997) · Zbl 0877.65018
[39] KNYAZEV, A geometric theory for preconditioned inverse iteration. III: A short and sharp convergence estimate for generalized eigenvalue problems, Linear Algebra Appl. 358 pp 95– (2003) · Zbl 1037.65039
[40] LANCZOS, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Stand. 45 (4) pp 255– (1950)
[41] LEHOUCQ, Using generalized Cayley transformations within an inexact rational Krylov sequence method, SIAM J. Matrix Anal. Appl. 20 (1) pp 131– (1999) · Zbl 0931.65035
[42] LIU, Jacobi-Davidson algorithm and its application to modeling RF/microwave detection circuits, Comput. Methods Appl. Mech. Engrg. 169 (3-4) pp 359– (1999) · Zbl 0941.78012
[43] MEERBERGEN, Locking and restarting quadratic eigenvalue solvers, SIAM J. Sci. Comput. 22 (5) pp 1814– (2000) · Zbl 0985.65027
[44] MEIJERINK, An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix, Math. Comp. 31 pp 148– (1977)
[45] MORGAN, Preconditioning eigenvalues and some comparison of solvers, J. Comput. Appl. Math. 123 (1-2) pp 101– (2000) · Zbl 0979.65028
[46] NOOL , M. VAN DER PLOEG , A. Parallel Jacobi-Davidson for solving generalized eigenvalue problems. In Vector and parallel processing-VECPAR ’98 (Porto), vol. 1573 of Lecture Notes in Comput. Sci. Springer, Berlin, 1999, pp. 58-70. · Zbl 0964.65037
[47] NOOL, A parallel Jacobi-Davidson-type method for solving large generalized eigenvalue problems in magnetohydrodynamics, SIAM J. Sci. Comput. 22 (1) pp 95– (2000) · Zbl 0964.65037
[48] NOTAY, Optimal order preconditioning of finite difference matrices, SIAM J. Sci. Comput. 21 pp 1991– (2000) · Zbl 0959.65064
[49] NOTAY, Combination of Jacobi-Davidson and conjugate gradients for the partial symmetric eigenproblem, Numer. Lin. Alg. Appl. pp 21– (2002) · Zbl 1071.65516
[50] NOTAY, Convergence analysis of inexact Rayleigh quotient iteration, SIAM J. Matrix Anal. Appl. 24 pp 627– (2003) · Zbl 1045.65032
[51] NOTAY, Is Jacobi-Davidson faster than Davidson, SIAM J. Matrix Anal. Appl. 26 (2) pp 522– (2004/05) · Zbl 1078.65032
[52] OVTCHINNIKOV, Convergence estimates for the generalized Davidson method for symmetric eigenvalue problems. I. The preconditioning aspect, SIAM J. Numer. Anal. 41 (1) pp 258– (2003) · Zbl 1078.65537
[53] OVTCHINNIKOV, Convergence estimates for the generalized Davidson method for symmetric eigenvalue problems. II. The subspace acceleration, SIAM J. Numer. Anal. 41 (1) pp 272– (2003) · Zbl 1078.65538
[54] PARLETT , B. N. The Symmetric Eigenvalue Problem. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Corrected reprint of the 1980 original. · Zbl 0885.65039
[55] ROMMES , J. VAN DER VORST , H. A. TER MATEN , E. J. W. Jacobi-Davidson methods and preconditioning with applications in pole-zero analysis. In Progress in industrial mathematics at ECMI 2002, vol. 5 of Math. Ind. Springer, Berlin, 2004, pp. 191-196. · Zbl 1087.65546
[56] SAAD , Y. Iterative Methods for Sparse Linear Systems. SIAM, Philadelphia, 2003. Second ed. · Zbl 1031.65046
[57] SIMONCINI, Inexact Rayleigh quotient-type methods for eigenvalue computations, BIT 42 pp 159– (2002) · Zbl 1003.65033
[58] SLEIJPEN,, Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems, BIT 36 (3) pp 595– (1996) · Zbl 0861.65035
[59] SLEIJPEN,, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl. 17 (2) pp 401– (1996) · Zbl 0860.65023
[60] SLEIJPEN, G. L. G. VAN DER VORST , H. A. The Jacobi-Davidson method for eigenvalue problems and its relation with accelerated inexact Newton schemes. In Iterative Methods in Linear Algebra, II. (New Brunswick, NJ, U.S.A., 1996), S. D. Margenov and P. S. Vassilevski, Eds., vol. 3 of IMACS Series in Computational and Applied Mathematics, IMACS, pp. 377-389.
[61] SLEIJPEN,, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM Review 42 (2) pp 267– (2000) · Zbl 0949.65028
[62] SLEIJPEN,, Efficient expansion of subspaces in the Jacobi-Davidson method for standard and generalized eigenproblems, Electron. Trans. Numer. Anal. 7 pp 75– (1998) · Zbl 0912.65026
[63] SLEIJPEN,, Exploiting multilevel preconditioning techniques in eigenvalue computations, SIAM J. Sci. Comput. 25 (4) pp 1249– (2003/04) · Zbl 1061.65030
[64] SORENSEN, Numerical methods for large eigenvalue problems, Acta Numer. 11 (2002) · Zbl 1105.65325
[65] SORENSEN, A truncated RQ iteration for large scale eigenvalue calculations, SIAM J. Matrix Anal. Appl. 19 (4) pp 1045– (1998) · Zbl 0918.65023
[66] STATHOPOULOS, A case for a biorthogonal Jacobi-Davidson method: restarting and correction equation, SIAM J. Matrix Anal. Appl. 24 (1) pp 238– (2002) · Zbl 1016.65016
[67] STATHOPOULOS, Restarting techniques for the (Jacobi-)Davidson symmetric eigenvalue methods, Electron. Trans. Numer. Anal. 7 pp 163– (1998) · Zbl 0912.65027
[68] STEWART , G. W. Matrix algorithms. Vol. II. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001.
[69] STREIFF, Computing optical modes for VCSEL device simulation, IEE Proc.-Optoelectron. 149 (4) pp 166– (2002)
[70] SZYLD , D. B. Criteria for combining inverse and Rayleigh quotient iteration. SIAM J. Numer. Anal. (1988), 1369-1375. · Zbl 0665.65031
[71] TISSEUR, The quadratic eigenvalue problem, SIAM Rev. 43 (2) pp 235– (2001) · Zbl 0985.65028
[72] TROTTENBERG , U. OOSTERLEE , C. W. SCH ÜLLER , A. Multigrid. Academic Press, London, 2001.
[73] VAN DEN ESHOF, The convergence of Jacobi-Davidson iterations for Hermitian eigenproblems. Numer, Linear Algebra Appl. 9 (2) pp 163– (2002) · Zbl 1071.65518
[74] VAN DER VORST, Subspace iteration for eigenproblems, CWI Quarterly 9 (1-2) pp 151– (1996) · Zbl 0871.65028
[75] VAN DER VORST , H. A. Computational methods for large eigenvalue problems. In Handbook of numerical analysis, Vol. VIII. North-Holland, Amsterdam, 2002, pp. 3-179. · Zbl 1028.65028
[76] VAN DER VORST , H. A. Iterative Krylov Methods for Large Linear systems. Cambridge University Press, Cambridge, 2003. · Zbl 1023.65027
[77] VAN DER VORST, Modern methods for the iterative computation of eigenpairs of matrices of high dimension, ZAMM Z. Angew. Math. Mech. 84 (7) pp 444– (2004) · Zbl 1055.65051
[78] VAN DER VORST , H. A. GOLUB , G. H. 150 years old and still alive: eigenproblems. In The state of the art in numerical analysis (York, 1996), vol. 63 of Inst. Math. Appl. Conf. Ser. New Ser. Oxford Univ. Press, New York, 1997, pp. 93-119. · Zbl 0881.65026
[79] VAN DORSSELAER, Computing eigenvalues occurring in continuation methods with the Jacobi-Davidson QZ method, J. Comput. Phys. 138 (2) pp 714– (1997) · Zbl 0899.65033
[80] VAN NOORDEN , T. L. Computing a partial real ordered generalized Schur form using the Jacobi- Davidson method. Preprint 1307, Department of Mathematics, Utrecht University, September 2004.
[81] VOSS , H. A Jacobi-Davidson method for nonlinear and nonsymmetric eigenproblems. Tech. rep., Institute of Mathematics, Hamburg University of Technology, 2004. Submitted. · Zbl 1080.65535
[82] WANG, Numerical methods for semiconductor heterostructures with band nonparabolicity, J. Comput. Phys. 190 (1) pp 141– (2003) · Zbl 1027.82040
[83] YANG, Large-scale normal coordinate analysis for molecular structures, SIAM J. Sci. Comput. 23 (2) pp 563– (2001) · Zbl 0992.65031
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.