Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Arnoldi and Jacobi-Davidson methods for generalized eigenvalue problems $ Ax=\lambda Bx$ with singular $ B$

Author: Joost Rommes
Journal: Math. Comp. 77 (2008), 995-1015
MSC (2000): Primary 65F15, 65F50
Published electronically: December 10, 2007
MathSciNet review: 2373189
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In many physical situations, a few specific eigenvalues of a large sparse generalized eigenvalue problem $ Ax=\lambda Bx$ are needed. If exact linear solves with $ A-\sigma B$ are available, implicitly restarted Arnoldi with purification is a common approach for problems where $ B$ is positive semidefinite. In this paper, a new approach based on implicitly restarted Arnoldi will be presented that avoids most of the problems due to the singularity of $ B$. Secondly, if exact solves are not available, Jacobi-Davidson QZ will be presented as a robust method to compute a few specific eigenvalues. Results are illustrated by numerical experiments.

References [Enhancements On Off] (What's this?)

  • 1. K. A. Cliffe, T. J. Garratt, and A. Spence, Eigenvalues of the discretized Navier-Stokes equation with application to the detection of Hopf bifurcations, Adv. Math. Comp. 1 (1993), 337-356. MR 1242379 (94k:65052)
  • 2. -, Eigenvalues of block matrices arising from problems in fluid mechanics, SIAM J. Matrix Anal. Appl. 15 (1994), no. 4, 1310-1318. MR 1293919 (95g:65053)
  • 3. K. A. Cliffe, A. Spence, and S. J. Tavener, The numerical analysis of bifurcation problems with application to fluid mechanics, Acta Numerica 9 (2000), 39-131. MR 1883627 (2003b:37125)
  • 4. H. Elman, D. Silvester, and A. Wathen, Finite Elements and Fast Iterative Solvers, First ed., Oxford University Press, 2005. MR 2155549 (2006f:65002)
  • 5. T. Ericsson, A generalised eigenvalue problem and the Lanczos algorithm, Large Scale Eigenvalue Problems (J. Cullum and R.A. Willoughby, eds.), Elsevier Science Publishers BV, 1986, pp. 95-119. MR 875436 (88c:65035)
  • 6. T. Ericsson and A. Ruhe, The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp. 35 (1980), 1251-1268. MR 583502 (83b:65034)
  • 7. D. R. Fokkema, G. L. G. Sleijpen, and H. A. van der Vorst, Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM J. Sc. Comp. 20 (1998), no. 1, 94-125. MR 1639102 (99e:65061)
  • 8. T. J. Garratt, The numerical detection of Hopf bifurcations in large systems arising in fluid mechanics, Ph.D. thesis, University of Bath, 1991.
  • 9. P. M. Gresho, D. K. Gartling, J. R. Torczynski, K. A. Cliffe, K. H. Winters, T. J. Garratt, A. Spence, and J. W. Goodrich, Is the steady viscous incompressible two-dimensional flow over a backward-facing step at Re=800 stable?, Int. J. Num. Meth.Fluids 17 (1993), 501-541. MR 1235004 (94h:76055)
  • 10. R. B. Lehoucq and J. A. Scott, Implicitly restarted Arnoldi methods and eigenvalues of the discretized Navier Stokes equations, Tech. Report SAND97-2712J, Sandia National Laboratory, 1997.
  • 11. R. B. Lehoucq and D. C. Sorensen, Deflation techniques within an implicitly restarted Arnoldi iteration, SIAM J. Matrix Anal. Appl. 17 (1996), 789-821. MR 1410702 (97k:65091)
  • 12. R. H. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK SOFTWARE, see:
  • 13. K. Meerbergen and D. Roose, The restarted Arnoldi method applied to iterative linear system solvers for the computation of rightmost eigenvalues, SIAM J. Matrix Anal. Appl. 18 (1997), no. 1, 1-20. MR 1428194 (98b:65042)
  • 14. K. Meerbergen and A. Spence, Implicitly restarted Arnoldi with purification for the shift-invert transformation, Math. Comp. 66 (1997), no. 218, 667-689. MR 1408376 (97h:65048)
  • 15. K. Meerbergen, A. Spence, and D. Roose, Shift-invert and Cayley transforms for detection of rightmost eigenvalues of nonsymmetric matrices, BIT 34 (1994), no. 3, 409-423. MR 1429941 (97i:65060)
  • 16. B. Nour-Omid, B. N. Parlett, T. Ericsson, and P. S. Jensen, How to implement the spectral transformation, Math. Comp. 48 (1987), no. 178, 663-673. MR 878698 (88f:65062)
  • 17. Y. Saad and M. H. Schultz, GMRES: A generalized minimial residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput. 7 (1986), no. 3, 856-869. MR 848568 (87g:65064)
  • 18. D. Silvester, H. Elman, and A. Ramage, Incompressible Flow and Iterative Solver Software, djs/ifiss/.
  • 19. G. L. G. Sleijpen, J. G. L. Booten, D. R. Fokkema, and H. A. van der Vorst, Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems, BIT 36 (1996), no. 3, 595-633. MR 1410100 (97k:65095)
  • 20. 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. MR 1384515 (96m:65042)
  • 21. G. L. G. Sleijpen, H. A. van der Vorst, and E. Meijerink, Efficient expansion of subspaces in the Jacobi-Davidson method, Electronic Transactions on Numerical Analysis 7 (1998), 75-89. MR 1667640 (99i:65040)
  • 22. D. C. Sorensen, Implicit application of polynomial filters in a $ k$-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13 (1992), 357-385. MR 1146670 (92i:65076)
  • 23. -, Deflation for implicitly restarted Arnoldi methods, Tech. Report TR98-12, Rice University, 1998.
  • 24. T. L. van Noorden and J. Rommes, Computing a partial real ordered generalized Schur form using the Jacobi-Davidson method, Num. Lin. Alg. Appl. 14 (2007), no. 3, 197-215. MR 2301912

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65F15, 65F50

Retrieve articles in all journals with MSC (2000): 65F15, 65F50

Additional Information

Joost Rommes
Affiliation: Mathematical Institute, Utrecht University, P.O. Box 80010, NL-3508 TA Utrecht, The Netherlands
Address at time of publication: NXP Semiconductors, Corporate I&T / DTF, High Tech Campus 37, PostBox WY4-01, NL-5656 AE, Eindhoven, The Netherlands

Keywords: Sparse generalized eigenvalue problems, purification, semi-inner product, implicitly restarted Arnoldi, Jacobi-Davidson, preconditioning
Received by editor(s): March 29, 2005
Received by editor(s) in revised form: January 25, 2007
Published electronically: December 10, 2007
Additional Notes: The author was supported by the BRICKS-MSV1 project.
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society