Hochstenbach, Michiel E. A Jacobi-Davidson type method for the product eigenvalue problem. (English) Zbl 1139.65028 J. Comput. Appl. Math. 212, No. 1, 46-62 (2008). Summary: We propose a Jacobi-Davidson type method to compute selected eigenpairs of the product eigenvalue problem \(A_m\cdots A_{1}x=\lambda x\), where the matrices may be large and sparse. To avoid difficulties caused by a high condition number of the product matrix, we split up the action of the product matrix and work with several search spaces. We generalize the Jacobi-Davidson correction equation and the harmonic and refined extraction for the product eigenvalue problem. Numerical experiments indicate that the method can be used to compute eigenvalues of product matrices with extremely high condition numbers. Cited in 2 Documents MSC: 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 65F50 Computational methods for sparse matrices Keywords:product eigenvalue problem; subspace method; Jacobi-Davidson correction; cyclic matrix; cyclic eigenvalue problem; harmonic extraction; refined extraction; large sparse matrices; numerical experiments Software:mctoolbox; benchmodred PDFBibTeX XMLCite \textit{M. E. Hochstenbach}, J. Comput. Appl. Math. 212, No. 1, 46--62 (2008; Zbl 1139.65028) Full Text: DOI References: [1] Amodio, P.; Cash, J. R.; Roussos, G.; Wright, R. W.; Fairweather, G.; Gladwell, I.; Kraut, G. L.; Paprzycki, M., Almost block diagonal linear systems: sequential and parallel solution techniques, and applications, Numer. Linear Algebra Appl., 7, 275-317 (2000) · Zbl 1051.65018 [2] Bojanczyk, A.; Golub, G. H.; Van Dooren, P., The periodic Schur decomposition; algorithm and applications, (Proc. SPIE Conference, vol. 1770 (1992)), 31-42 [3] Y. Chahlaoui, P. Van Dooren, Benchmark examples for model reduction of linear time-invariant dynamical systems, in: P. Benner, V. Mehrmann, D.C. Sorensen (Eds.), Dimension Reduction of Large-Scale Systems, Lecture Notes in Computational Science and Engineering, vol. 45, Springer, Heidelberg, 2005, pp. 379-392.; Y. Chahlaoui, P. Van Dooren, Benchmark examples for model reduction of linear time-invariant dynamical systems, in: P. Benner, V. Mehrmann, D.C. Sorensen (Eds.), Dimension Reduction of Large-Scale Systems, Lecture Notes in Computational Science and Engineering, vol. 45, Springer, Heidelberg, 2005, pp. 379-392. · Zbl 1100.93006 [4] Drmač, Z., Accurate computation of the product-induced singular value decomposition with applications, SIAM J. Numer. Anal., 35, 1969-1994 (1998) · Zbl 0914.65034 [5] Golub, G.; Sølna, K.; Van Dooren, P., Computing the SVD of a general matrix product/quotient, SIAM J. Matrix Anal. Appl., 22, 1-19 (2000) · Zbl 0969.65032 [6] Heath, M. T.; Laub, A. J.; Paige, C. C.; Ward, R. C., Computing the singular value decomposition of a product of two matrices, SIAM J. Sci. Statist. Comput., 7, 1147-1159 (1986) · Zbl 0607.65013 [7] Hench, J. J.; Laub, A. J., Numerical solution of the discrete-time periodic Riccati equation, IEEE Trans. Automat. Control, 39, 1197-1210 (1994) · Zbl 0804.93037 [8] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1011.65010 [9] Hochstenbach, M. E., A Jacobi-Davidson type SVD method, SIAM J. Sci. Comput., 23, 606-628 (2001) · Zbl 1002.65048 [10] Hochstenbach, M. E., Harmonic and refined extraction methods for the singular value problem, with applications in least squares problems, BIT, 44, 721-754 (2004) · Zbl 1079.65047 [11] Jia, Z., Refined iterative algorithms based on Arnoldi’s process for large unsymmetric eigenproblems, Linear Algebra Appl., 259, 1-23 (1997) · Zbl 0877.65018 [12] D. Kressner, An efficient and reliable implementation of the periodic QZ algorithm, in: IFAC Workshop on Periodic Control Systems, 2001.; D. Kressner, An efficient and reliable implementation of the periodic QZ algorithm, in: IFAC Workshop on Periodic Control Systems, 2001. [13] D. Kressner, Numerical methods and software for general and structured eigenvalue problems, Ph.D. Thesis, Technische Universität Berlin, 2004.; D. Kressner, Numerical methods and software for general and structured eigenvalue problems, Ph.D. Thesis, Technische Universität Berlin, 2004. · Zbl 1213.65062 [14] Kressner, D., A periodic Krylov-Schur algorithm for large matrix products, Numer. Math., 103, 461-483 (2006) · Zbl 1094.65027 [15] Oliveira, S.; Stewart, D. E., Exponential splittings of products of matrices and accurately computing singular values of long products, Linear Algebra Appl., 309, 175-190 (2000) · Zbl 0955.65028 [16] Parlett, B. N., The Symmetric Eigenvalue Problem (1998), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA, Corrected reprint of the 1980 original · Zbl 0885.65039 [17] Saad, Y., Numerical Methods for Large Eigenvalue Problems (1992), Manchester University Press: Manchester University Press Manchester, UK · Zbl 0991.65039 [18] Sleijpen, G. L.G.; van der Vorst, H. A., A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17, 401-425 (1996) · Zbl 0860.65023 [19] G.L.G. Sleijpen, H.A. van der Vorst, The Jacobi-Davidson method for eigenvalue problems and its relation with accelerated inexact Newton schemes, in: S.D. Margenov, P.S. Vassilevski (Eds.), Iterative Methods in Linear Algebra, II, IMACS Series in Computational and Applied Mathematics, vol. 3, New Brunswick, NJ, USA, 1996, IMACS, pp. 377-389.; G.L.G. Sleijpen, H.A. van der Vorst, The Jacobi-Davidson method for eigenvalue problems and its relation with accelerated inexact Newton schemes, in: S.D. Margenov, P.S. Vassilevski (Eds.), Iterative Methods in Linear Algebra, II, IMACS Series in Computational and Applied Mathematics, vol. 3, New Brunswick, NJ, USA, 1996, IMACS, pp. 377-389. [20] Stathopoulos, A.; Saad, Y., Restarting techniques for the (Jacobi-) Davidson symmetric eigenvalue methods, Electron. Trans. Numer. Anal., 7, 163-181 (1998) · Zbl 0912.65027 [21] Stewart, D. E., A new algorithm for the SVD of a long product of matrices and the stability of products, Electron. Trans. Numer. Anal., 5, 29-47 (1997) · Zbl 0895.65012 [22] G.W. Stewart, Matrix Algorithms, Vol. II, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001.; G.W. Stewart, Matrix Algorithms, Vol. II, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. [23] Van Loan, C. F., A general matrix eigenvalue algorithm, SIAM J. Numer. Anal., 12, 819-834 (1975) · Zbl 0321.65023 [24] Watkins, D., Product eigenvalue problems, SIAM Rev., 47, 3-40 (2005) · Zbl 1075.65055 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.