×

zbMATH — the first resource for mathematics

An implicit filter for rational Krylov using core transformations. (English) Zbl 1403.65016
Summary: The rational Krylov method is a powerful tool for computing a selected subset of eigenvalues in large-scale eigenvalue problems. In this paper we study a method to implicitly apply a filter in a rational Krylov iteration by directly acting on a QR factorized representation of the Hessenberg pair from the rational Krylov method. This filter is used to restart the iteration, which is generally required to limit the orthogonalization and storage costs. The contribution in this paper is threefold. We reformulate existing procedures in terms of operations on core transformations. This has the advantage of improved convergence monitoring. Secondly, we demonstrate that the extended QZ method is a special case of this more general method. Finally, numerical experiments show the validity and the increased accuracy of the new approach compared with existing methods.

MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
Software:
ARPACK; eigs; IFISS; IRAM
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnoldi, W. E., The principle of minimized iteration in the solution of the matrix eigenvalue problem, Quart. Appl. Math., 9, 17-29, (1951) · Zbl 0042.12801
[2] Saad, Y., Variations on Arnoldi’s method for computing eigenelements of large unsymmetric matrices, Linear Algebra Appl., 34, 269-295, (1980) · Zbl 0456.65017
[3] Saad, Y., Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. Comp., 42, 166, 567-588, (1984) · Zbl 0539.65013
[4] Saad, Y., Numerical solution of large nonsymmetric eigenvalue problems, Comput. Phys. Commun., 53, 1-3, 71-90, (1989) · Zbl 0798.65053
[5] Y. Saad, Numerical Methods for Large Eigenvalue Problems, Manchester University Press. · Zbl 0991.65039
[6] Kuijlaars, A., Which eigenvalues are found by the Lanczos method?, SIAM J. Matrix Anal. Appl., 22, 1, 306-321, (2000) · Zbl 0969.65028
[7] Kuijlaars, A., Convergence analysis of Krylov subspace iterations with methods from potential theory, SIAM Rev., 48, 1, 3-40, (2006) · Zbl 1092.65031
[8] Ericsson, T.; Ruhe, A., The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp., 35, 152, 1251-1268, (1980) · Zbl 0468.65021
[9] Parlett, B. N.; Saad, Y., Complex shift and invert strategies for real matrices, Linear Algebra Appl., 88-89, 575-595, (1987) · Zbl 0623.65045
[10] Meerbergen, K.; Spence, A., Implicitly restarted Arnoldi with purification for the shift-invert transformation, Math. Comp., 66, 218, 667-689, (1997) · Zbl 0864.65020
[11] Ruhe, A., Rational Krylov sequence methods for eigenvalue computation, Linear Algebra Appl., 58, 391-405, (1984) · Zbl 0554.65025
[12] Ruhe, A., Rational Krylov algorithms for nonsymmetric eigenvalue problems, (Golub, G.; Greenbaum, A.; Luskin, M., Recent Advances in Iterative Methods, IMA Volumes in Mathematics and its Applications, vol. 60, (1994), Springer-Verlag New York), 149-164 · Zbl 0803.65045
[13] Ruhe, A., Rational Krylov algorithms for nonsymmetric eigenvalue problems, II: matrix pairs, Linear Algebra Appl., 197-198, 283-296, (1994) · Zbl 0810.65031
[14] Ruhe, A., The rational Krylov algorithm for nonsymmetric eigenvalue problems. III: complex shifts for real matrices, BIT, 34, 165-176, (1994) · Zbl 0810.65032
[15] Ruhe, A., Rational Krylov: a practical algorithm for large sparse nonsymmetric matrix pencils, SIAM J. Sci. Comput., 19, 5, 1535-1551, (1998) · Zbl 0914.65036
[16] Druskin, V.; Knizhnerman, L., Extended Krylov subspaces: approximation of the matrix square root and related functions, SIAM J. Matrix Anal. Appl., 19, 3, 755-771, (1998) · Zbl 0912.65022
[17] Sorensen, D. C., Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13, 1, 357-385, (1992) · Zbl 0763.65025
[18] Morgan, R. B., On restarting the Arnoldi method for large nonsymmetric eigenvalue problems, Math. Comp., 65, 215, 1213-1231, (1996) · Zbl 0857.65041
[19] Lehoucq, R. B.; Sorensen, D. C., Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM J. Matrix Anal. Appl., 17, 4, 789-821, (1996) · Zbl 0863.65016
[20] Stewart, G., A Krylov-Schur algorithm for large eigenproblems, SIAM J. Matrix Anal. Appl., 23, 3, 601-614, (2001) · Zbl 1003.65045
[21] De Samblanx, G.; Meerbergen, K.; Bultheel, A., The implicit application of a rational filter in the RKS method, BIT, 37, 4, 925-947, (1997) · Zbl 0890.65035
[22] Berljafa, M.; Güttel, S., Generalized rational Krylov decompositions with an application to rational approximation, SIAM J. Matrix Anal. Appl., 36, 2, 894-916, (2015) · Zbl 1319.65028
[23] Vandebril, R., Chasing bulges or rotations? A metamorphosis of the QR-algorithm, SIAM J. Matrix Anal. Appl., 32, 1, 217-247, (2011) · Zbl 1218.65035
[24] Vandebril, R.; Watkins, D. S., A generalization of the multishift QR algorithm, SIAM J. Matrix Anal. Appl., 33, 3, 759-779, (2012) · Zbl 1261.65039
[25] Vandebril, R.; Watkins, D. S., An extension of the QZ algorithm beyond the Hessenberg-upper triangular pencil, Electron. Trans. Numer. Anal., 40, 17-35, (2013) · Zbl 1288.65053
[26] Camps, D.; Meerbergen, K.; Vandebril, R., A rational QZ method
[27] Mach, T.; Vandebril, R., On deflations in extended QR algorithms, SIAM J. Matrix Anal. Appl., 35, 2, 559-579, (2014) · Zbl 1301.65025
[28] Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Natl. Bur. Stand., 45, 4, 255, (1950)
[29] Berljafa, M., Rational Krylov decompositions: theory and applications, (2017), The University of Manchester, Ph.D. thesis
[30] Vandebril, R.; Van Barel, M.; Mastronardi, N., A parallel QR-factorization/solver of quasiseparable matrices, Electron. Trans. Numer. Anal., 30, 144-167, (2008) · Zbl 1171.65017
[31] Fasino, D., Rational Krylov matrices and QR steps on Hermitian diagonal-plus-semiseparable matrices, Numer. Linear Algebra Appl., 12, 8, 743-754, (2005) · Zbl 1164.15339
[32] Van Barel, M.; Fasino, D.; Gemignani, L.; Mastronardi, N., Orthogonal rational functions and structured matrices, SIAM J. Matrix Anal. Appl., 26, 3, 810-829, (2005) · Zbl 1071.42015
[33] Mach, T.; Barel, M. V.; Vandebril, R., Inverse eigenvalue problems for extended Hessenberg and extended tridiagonal matrices, J. Comput. Appl. Math., 272, 377-398, (2014) · Zbl 1294.65041
[34] Kågström, B.; Poromaa, P., Computing eigenspaces with specified eigenvalues of a regular matrix pair (A, B) and condition estimation: theory, algorithms and software, Numer. Algorithms, 12, 369-407, (1996) · Zbl 0859.65036
[35] Van Dooren, P., A generalized eigenvalue approach for solving Riccati equations, SIAM J. Sci. Statist. Comput., 2, 2, 121-135, (1981) · Zbl 0463.65024
[36] Aurentz, J.; Mach, T.; Robol, L.; Vandebril, R.; Watkins, D., Core-chasing algorithms for the eigenvalue problem, fundamentals of algorithms, (2018), Society for Industrial and Applied Mathematics · Zbl 1434.65003
[37] Van Beeumen, R.; Meerbergen, K.; Michiels, W., Connections between contour integration and rational Krylov methods for eigenvalue problems, (2016), Department of Computer Science, KU Leuven, Technical report TW673
[38] Baglama, J.; Calvetti, D.; Reichel, L., IRBL: an implicitly restarted block-Lanczos method for large-scale Hermitian eigenproblems, SIAM J. Sci. Comput., 24, 5, 1650-1677, (2003) · Zbl 1044.65027
[39] Baglama, J.; Reichel, L., An implicitly restarted block Lanczos bidiagonalization method using Leja shifts, BIT, 53, 2, 285-310, (2013) · Zbl 1269.65038
[40] Turner, J. S., Buoyancy effects in fluids, (1973), Cambridge University Press · Zbl 0262.76067
[41] Cliffe, K. A.; Garratt, T. J.; Spence, A., Eigenvalues of the discretized Navier-Stokes equation with application to the detection of Hopf bifurcations, Adv. Comput. Math., 1, 3, 337-356, (1993) · Zbl 0830.76048
[42] Elman, H.; Meerbergen, K.; Spence, A.; Wu, M., Lyapunov inverse iteration for identifying Hopf bifurcations in models of incompressible flow, SIAM J. Sci. Comput., 34, 3, 1584-1606, (2012)
[43] Elman, H. C.; Ramage, A.; Silvester, D. J., IFISS: a computational laboratory for investigating incompressible flow problems, SIAM Rev., 56, 2, 261-273, (2014) · Zbl 1426.76645
[44] Elman, H. C.; Wu, M., Lyapunov inverse iteration for computing rightmost eigenvalues of large generalized eigenvalue problems, SIAM J. Matrix Anal. Appl., 34, 4, 1685-1707, (2013) · Zbl 1425.65053
[45] Lehoucq, R. B.; Sorensen, D. C.; Yang, C., ARPACK users’ guide: solution of large scale eigenvalue problems with implicitly restarted Arnoldi methods, (1997) · Zbl 0901.65021
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.