Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

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

Author(s): Joost Rommes.
Journal: Math. Comp. 77 (2008), 995-1015.
MSC (2000): Primary 65F15, 65F50
Posted: December 10, 2007
Retrieve article in: PDF DVI PostScript

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:

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: http://www.caam.rice.edu/software/ARPACK/.

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, http://www.maths.manchester.ac.uk/ 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
Email: joost.rommes@nxp.com

DOI: 10.1090/S0025-5718-07-02040-6
PII: S 0025-5718(07)02040-6
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
Posted: December 10, 2007
Additional Notes: The author was supported by the BRICKS-MSV1 project.
Copyright of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google