Harmonic and Refined Extraction Methods for the Singular Value Problem,with Applications in Least Squares Problems

For the accurate approximation of the minimal singular triple (singular value and left and right singular vector) of a large sparse matrix, we may use two separate search spaces, one for the left, and one for the right singular vector. In Lanczos bidiagonalization, for example, such search spaces are constructed. In SIAM J. Sci. Comput., 23(2) (2002), pp. 606–628, the author proposes a Jacobi–Davidson type method for the singular value problem, where solutions to certain correction equations are used to expand the search spaces. As noted in the mentioned paper, the standard Galerkin subspace extraction works well for the computation of large singular triples, but may lead to unsatisfactory approximations to small and interior triples. To overcome this problem for the smallest triples, we propose three harmonic and a refined approach. All methods are derived in a number of different ways. Some of these methods can also be applied when we are interested in the largest or interior singular triples. Theoretical results as well as numerical experiments indicate that the results of the alternative extraction processes are often better than the standard approach. We show that when Lanczos bidiagonalization is used for the subspace expansion, the standard, harmonic, and refined extraction methods are all essentially equivalent. This gives more insight in the success of Lanczos bidiagonalization to find the smallest singular triples. Finally, we show that the extraction processes for the smallest singular values may give an approximation to a least squares problem at low additional costs. The truncated SVD is also discussed in this context. AMS subject classification (2000) 65F15, 65F50, (65F35, 93E24).Submitted December 2002. Accepted October 2004. Communicated by Haesun Park.M. E. Hochstenbach: The research of this author was supported in part by NSF grant DMS-0405387. Part of this work was done when the author was at Utrecht University.