Hochstenbach, M. E. Harmonic and refined extraction methods for the singular value problem, with applications in least squares problems. (English) Zbl 1079.65047 BIT 44, No. 4, 721-754 (2004). The author presents the accurate approximation of the minimal singular triple (the smallest singular value and corresponding left and right singular vector) of a large and/or sparse matrix. He suggests three harmonic and refined approaches for the above problem with some specific variants as the finding the largest or interior singular triples and the applications of the determined smallest singular values in the approximations of the least squares solutions and in truncated singular value decomposition.As the conclusion of this paper (34 pages) with many comparative numerical experiments, the author proposes to use for the smallest and interior singular triples the refined extraction approach (the minimal left and right singular vector of matrix \(A\) minimize \(\| A^{*}x\| \) and \(\| Ay\| \), respectively) with the double-harmonic extraction method (harmonic Rayleigh-Ritz extraction introduced by C. C. Paige, B. N. Parlett and H. A. Van der Vorst [Numer. Linear Algebra Appl. 2(2), 115–133 (1995; Zbl 0831.65036)] as an alternative. For the largest singular triples is recommended standard extraction (Galerkin subspace method) because it is the cheapest. Reviewer: Jan Kozanek (Praha) Cited in 28 Documents MSC: 65F20 Numerical solutions to overdetermined systems, pseudoinverses 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 65F50 Computational methods for sparse matrices 65F35 Numerical computation of matrix norms, conditioning, scaling Keywords:large sparse matrix; subspace method; least squares problem; truncated SVD; singular value decomposition; numerical experiments; double-harmonic extraction method; harmonic Rayleigh-Ritz extraction Citations:Zbl 0831.65036 Software:CRAIG; LSQR; JDQZ; MatrixMarket; JDQR; PROPACK PDFBibTeX XMLCite \textit{M. E. Hochstenbach}, BIT 44, No. 4, 721--754 (2004; Zbl 1079.65047) Full Text: DOI Link References: [1] J. Baglama, D. Calvetti, and L. Reichel, IRBL: An implicitly restarted Block?Lanczos method for large-scale Hermitian eigenproblems, SIAM J. Sci. Comput., 24(5) (2003), pp. 1650-1677. · Zbl 1044.65027 [2] J. Baglama and L. Reichel, Augmented implicitly restarted Lanczos bidiagonalization methods, Preprint, 2004. · Zbl 1087.65039 [3] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst (eds.), Templates for the Solution of Algebraic Eigenvalue Problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. A practical guide. · Zbl 0965.65058 [4] Å. Björck, Numerical Methods for Least Squares Problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. · Zbl 0847.65023 [5] G. H. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), pp. 205-224. · Zbl 0194.18201 [6] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd edn, The John Hopkins University Press, Baltimore, 1996. · Zbl 0865.65009 [7] M. E. Hochstenbach, A Jacobi?Davidson type SVD method, SIAM J. Sci. Comput., 23(2) (2001), pp. 606-628. · Zbl 1002.65048 [8] JDQR code, available via http://www.math.uu.nl/people/sleijpen. [9] Z. Jia, Refined iterative algorithms based on Arnoldi?s process for large unsymmetric eigenproblems, Linear Algebra Appl., 259 (1997), pp. 1-23. · Zbl 0877.65018 [10] Z. Jia and D. Niu, An implicitly restarted refined bidiagonalization Lanczos method for computing a partial singular value decomposition, SIAM J. Matrix Anal. Appl., 25(1) (2003), pp. 246-265. · Zbl 1063.65030 [11] A. V. Knyazev, New estimates for Ritz vectors, Math. Comp., 66(219) (1997), pp. 985-995. · Zbl 0870.65045 [12] E. Kokiopoulou, C. Bekas and E. Gallopoulos, Computing smallest singular triplets with implicitly restarted Lanczos bidiagonalization, Appl. Numer. Math., 49(1) (2004), pp. 39-61. · Zbl 1049.65027 [13] R. M. Larsen, Lanczos bidiagonalization with partial reorthogonalization, Technical report DAIMI PB-357, Department of Computer Science, University of Aarhus, September 1998. See also http://sun.stanford.edu/\(\sim\)rmunk/PROPACK. [14] The Matrix Market, http://math.nist.gov/MatrixMarket, a repository for test matrices. [15] R. B. Morgan, Computing interior eigenvalues of large matrices, Linear Algebra Appl., 154/156 (1991), pp. 289-309. · Zbl 0734.65029 [16] C. C. Paige, B. N. Parlett, and H. A. van der Vorst, Approximate solutions and eigenvalue bounds from Krylov subspaces, Num. Lin. Alg. Appl., 2(2) (1995), pp. 115-133. · Zbl 0831.65036 [17] C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8(1) (1982), pp. 43-71. · Zbl 0478.65016 [18] B. N. Parlett, The Symmetric Eigenvalue Problem, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Corrected reprint of the 1980 original. · Zbl 0885.65039 [19] Y. Saad, Numerical Methods for Large Eigenvalue Problems, Manchester University Press, Manchester, UK, 1992. · Zbl 0991.65039 [20] H. D. Simon and H. Zha, Low-rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM J. Sci. Comput., 21(6) (2000), pp. 2257-2274. · Zbl 0962.65038 [21] G. L. G. Sleijpen, H. A. van der Vorst, and E. Meijerink, Efficient expansion of subspaces in the Jacobi?Davidson method for standard and generalized eigenproblems, Electron. Trans. Numer. Anal., 7 (1998), pp. 75-89. · Zbl 0912.65026 [22] G. W. Stewart, Matrix Algorithms, Vol. II, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. [23] G. W. Stewart and J. G. Sun, Matrix Perturbation Theory, Academic Press Inc., Boston, MA, 1990. · Zbl 0706.65013 [24] L. N. Trefethen, Computation of pseudospectra, in Acta Numerica, Cambridge Univ. Press, Cambridge, 1999, pp. 247-295. · Zbl 0945.65039 [25] S. Van Huffel and J. Vandewalle, The Total Least Squares Problem, Frontiers in Applied Mathematics, Vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1991. · Zbl 0789.62054 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.