Arnoldi and Jacobi-Davidson methods for generalized eigenvalue problems \(Ax=\lambda Bx\) with singular \(B\). (English) Zbl 1133.65020
Summary: In many physical situations, a few specific eigenvalues of a large sparse generalized eigenvalue problem \( Ax=\lambda Bx\) are needed. If exact linear solvers 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 is presented that avoids most of the problems due to the singularity of \( B\). Secondly, if exact solvers are not available, Jacobi-Davidson QZ will be presented as a robust method to compute a few specific eigenvalues. The results are illustrated by numerical experiments.
In this paper, a new approach based on implicitly restarted Arnoldi is presented that avoids most of the problems due to the singularity of \( B\). Secondly, if exact solvers are not available, Jacobi-Davidson QZ will be presented as a robust method to compute a few specific eigenvalues. The results are illustrated by numerical experiments.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F50 | Computational methods for sparse matrices |
Keywords:
sparse generalized eigenvalue problems; purification; semi-inner product; implicitly restarted Arnoldi method; Jacobi-Davidson method; preconditioning; numerical experimentsReferences:
| [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. Comput. Math. 1 (1993), no. 3-4, 337 – 356. · Zbl 0830.76048 · doi:10.1007/BF02072015 |
| [2] | 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. · Zbl 0807.65030 · doi:10.1137/S0895479892233230 |
| [3] | 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. · Zbl 1005.65138 · doi:10.1017/S0962492900000398 |
| [4] | 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. · Zbl 1083.76001 |
| [5] | 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. · Zbl 0605.65026 · doi:10.1016/S0304-0208(08)72642-2 |
| [6] | 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. · Zbl 0468.65021 |
| [7] | 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. · Zbl 0924.65027 · doi:10.1137/S1064827596300073 |
| [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] | 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 \?\?=800 stable?, Internat. J. Numer. Methods Fluids 17 (1993), no. 6, 501 – 541. · Zbl 0784.76050 · doi:10.1002/fld.1650170605 |
| [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 for an implicitly restarted Arnoldi iteration, SIAM J. Matrix Anal. Appl. 17 (1996), no. 4, 789 – 821. · Zbl 0863.65016 · doi:10.1137/S0895479895281484 |
| [12] | R. H. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK SOFTWARE, see: http://www.caam.rice.edu/software/ARPACK/. |
| [13] | 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. · Zbl 0872.65038 · doi:10.1137/S0895479894274255 |
| [14] | Karl Meerbergen and Alastair Spence, Implicitly restarted Arnoldi with purification for the shift-invert transformation, Math. Comp. 66 (1997), no. 218, 667 – 689. · Zbl 0864.65020 |
| [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. · Zbl 0814.65037 · doi:10.1007/BF01935650 |
| [16] | 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. · Zbl 0638.65026 |
| [17] | 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. · Zbl 0599.65018 · doi:10.1137/0907058 |
| [18] | D. Silvester, H. Elman, and A. Ramage, Incompressible Flow and Iterative Solver Software, http://www.maths.manchester.ac.uk/ djs/ifiss/. · Zbl 1365.65326 |
| [19] | 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). · Zbl 0861.65035 · doi:10.1007/BF01731936 |
| [20] | 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. · Zbl 0860.65023 · doi:10.1137/S0895479894270427 |
| [21] | 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). · Zbl 0912.65026 |
| [22] | D. C. Sorensen, Implicit application of polynomial filters in a \?-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13 (1992), no. 1, 357 – 385. · Zbl 0763.65025 · doi:10.1137/0613025 |
| [23] | -, Deflation for implicitly restarted Arnoldi methods, Tech. Report TR98-12, Rice University, 1998. |
| [24] | 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. · Zbl 1199.65126 · doi:10.1002/nla.523 |
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.
