Arnoldi and Jacobi-Davidson methods for generalized eigenvalue problems 𝐴𝑥=𝜆𝐵𝑥 with singular 𝐵

Rommes, Joost

doi:10.1090/S0025-5718-07-02040-6

Arnoldi and Jacobi-Davidson methods for generalized eigenvalue problems $Ax=\lambda Bx$ with singular $B$
HTML articles powered by AMS MathViewer

by Joost Rommes PDF

Math. Comp. 77 (2008), 995-1015 Request permission

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

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. Comput. Math. 1 (1993), no. 3-4, 337–356. MR 1242379, DOI 10.1007/BF02072015
K. A. Cliffe, T. J. Garratt, and A. Spence, Eigenvalues of block matrices arising from problems in fluid mechanics, SIAM J. Matrix Anal. Appl. 15 (1994), no. 4, 1310–1318. MR 1293919, DOI 10.1137/S0895479892233230
K. A. Cliffe, A. Spence, and S. J. Tavener, The numerical analysis of bifurcation problems with application to fluid mechanics, Acta numerica, 2000, Acta Numer., vol. 9, Cambridge Univ. Press, Cambridge, 2000, pp. 39–131. MR 1883627, DOI 10.1017/S0962492900000398
Howard C. Elman, David J. Silvester, and Andrew J. Wathen, Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2005. MR 2155549
Thomas Ericsson, A generalised eigenvalue problem and the Lánczos algorithm, Large scale eigenvalue problems (Oberlech, 1985) North-Holland Math. Stud., vol. 127, North-Holland, Amsterdam, 1986, pp. 95–119. MR 875436, DOI 10.1016/S0304-0208(08)72642-2
Thomas Ericsson and Axel Ruhe, The spectral transformation Lánczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp. 35 (1980), no. 152, 1251–1268. MR 583502, DOI 10.1090/S0025-5718-1980-0583502-2
Diederik R. Fokkema, Gerard L. G. Sleijpen, and Henk A. Van der Vorst, Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM J. Sci. Comput. 20 (1998), no. 1, 94–125. MR 1639102, DOI 10.1137/S1064827596300073
T. J. Garratt, The numerical detection of Hopf bifurcations in large systems arising in fluid mechanics, Ph.D. thesis, University of Bath, 1991.
Philip M. Gresho, David K. Gartling, J. R. Torczynski et al., Is the steady viscous incompressible two-dimensional flow over a backward-facing step at $\textrm {Re}=800$ stable?, Internat. J. Numer. Methods Fluids 17 (1993), no. 6, 501–541. MR 1235004, DOI 10.1002/fld.1650170605
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.
R. B. Lehoucq and D. C. Sorensen, Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM J. Matrix Anal. Appl. 17 (1996), no. 4, 789–821. MR 1410702, DOI 10.1137/S0895479895281484
R. H. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK SOFTWARE, see: http://www.caam.rice.edu/software/ARPACK/.
Karl Meerbergen and Dirk 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, DOI 10.1137/S0895479894274255
Karl Meerbergen and Alastair Spence, Implicitly restarted Arnoldi with purification for the shift-invert transformation, Math. Comp. 66 (1997), no. 218, 667–689. MR 1408376, DOI 10.1090/S0025-5718-97-00844-2
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, DOI 10.1007/BF01935650
Bahram Nour-Omid, Beresford N. Parlett, Thomas Ericsson, and Paul S. Jensen, How to implement the spectral transformation, Math. Comp. 48 (1987), no. 178, 663–673. MR 878698, DOI 10.1090/S0025-5718-1987-0878698-5
Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
D. Silvester, H. Elman, and A. Ramage, Incompressible Flow and Iterative Solver Software, http://www.maths.manchester.ac.uk/ djs/ifiss/.
Gerard L. G. Sleijpen, Albert G. L. Booten, Diederik R. Fokkema, and Henk A. Van der Vorst, Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems, BIT 36 (1996), no. 3, 595–633. International Linear Algebra Year (Toulouse, 1995). MR 1410100, DOI 10.1007/BF01731936
Gerard L. G. Sleijpen and Henk 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, DOI 10.1137/S0895479894270427
Gerard L. G. Sleijpen, Henk A. van der Vorst, and Ellen Meijerink, Efficient expansion of subspaces in the Jacobi-Davidson method for standard and generalized eigenproblems, Electron. Trans. Numer. Anal. 7 (1998), 75–89. Large scale eigenvalue problems (Argonne, IL, 1997). MR 1667640
D. C. Sorensen, Implicit application of polynomial filters in a $k$-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 357–385. MR 1146670, DOI 10.1137/0613025
—, Deflation for implicitly restarted Arnoldi methods, Tech. Report TR98-12, Rice University, 1998.
Tycho van Noorden and Joost Rommes, Computing a partial generalized real Schur form using the Jacobi-Davidson method, Numer. Linear Algebra Appl. 14 (2007), no. 3, 197–215. MR 2301912, DOI 10.1002/nla.523