The increasing number of applications requiring the solution of large scale singular value problems have rekindled interest in iterative methods for the SVD. Some promising recent ad- vances in large scale iterative methods are still plagued by slow convergence and accuracy limitations for computing smallest singular triplets. Furthermore, their current implementations in MATLAB cannot address the required large problems. Recently, we presented a preconditioned, two-stage method to effectively and accurately compute a small number of extreme singular triplets. In this research, we present a high-performance software, PRIMME SVDS, that implements our hybrid method based on the state-of-the-art eigensolver package PRIMME for both largest and smallest singular values. PRIMME SVDS fills a gap in production level software for computing the partial SVD, especially with preconditioning. The numerical experiments demonstrate its superior performance compared to other state-of-the-art software and its good parallel performance under strong and weak scaling.
The first approach computes eigenpairs of the normal equations matrix @math (or @math if @math ). The eigenpairs of @math correspond to the squares of the singular values and the right singular vectors of @math , @math . If @math , the corresponding left singular vectors are obtained as @math . Although extreme Hermitian eigenvalue problems can be solved very efficiently, @math can be ill-conditioned. Assume @math is a computed singular triplet corresponding to the exact triplet @math with residual satisfying @math . Then the relative errors satisfy the relations @cite_51 , where @math is the closest singular value to @math , @math is a constant that depends on the dimensions of @math , and @math is the machine precision. Since all singular values (except the largest @math ) will lose accuracy, this approach is typically followed by a second stage of iterative refinement. The singular triplets can be refined one by one @cite_18 @cite_20 @cite_28 or collectively as an initial subspace for an iterative eigensolver @cite_12 . This is especially needed when seeking smallest singular values.
@cite_18 @cite_28 @cite_20 @cite_51 @cite_12
2167193748 1918870341 2052926498 1747539222
The harmonic Lanczos bidiagonalization method can be used to compute the smallest singular triplets of a large matrix @math . We prove that for good enough projection subspaces harmonic Ritz values converge if the columns of @math are strongly linearly independent. On the other hand, harmonic Ritz values may miss some desired singular values when the columns of @math are almost linearly dependent. Furthermore, harmonic Ritz vectors may converge irregularly and may even fail to converge. Based on the refined projection principle for large matrix eigenproblems due to the first author, we propose a refined harmonic Lanczos bidiagonalization method that takes the Rayleigh quotients of the harmonic Ritz vectors as approximate singular values and extracts the best approximate singular vectors, called the refined harmonic Ritz approximations, from the given subspaces in the sense of residual minimizations. The refined approximations are shown to converge to the desired singular vectors once the subspaces are sufficiently good and the Rayleigh quotients converge. An implicitly restarted refined harmonic Lanczos bidiagonalization algorithm (IRRHLB) is developed. We study how to select the best possible shifts, and suggest refined harmonic shifts that are theoretically better than the harmonic shifts used within the implicitly restarted harmonic Lanczos bidiagonalization algorithm (IRHLB). We propose a novel procedure that can numerically compute the refined harmonic shifts efficiently and accurately. Numerical experiments are reported that compare IRRHLB with five other algorithms based on the Lanczos bidiagonalization process. It appears that IRRHLB is at least competitive with them and can be considerably more efficient when computing the smallest singular triplets. We consider the behavior of the GMRES method for solving a linear system @math when @math is singular or nearly so, i.e., ill conditioned. The (near) singularity of @math may or may not affect the performance of GMRES, depending on the nature of the system and the initial approximate solution. For singular @math , we give conditions under which the GMRES iterates converge safely to a least-squares solution or to the pseudoinverse solution. These results also apply to any residual minimizing Krylov subspace method that is mathematically equivalent to GMRES. A practical procedure is outlined for efficiently and reliably detecting singularity or ill conditioning when it becomes a threat to the performance of GMRES. We describe a parallel iterative least squares solver named LSRN that is based on random normal projection. LSRN computes the min-length solution to @math , where @math with @math or @math , and where @math may be rank-deficient. Tikhonov regularization may also be included. Since @math is only involved in matrix-matrix and matrix-vector multiplications, it can be a dense or sparse matrix or a linear operator, and LSRN automatically speeds up when @math is sparse or a fast linear operator. The preconditioning phase consists of a random normal projection, which is embarrassingly parallel, and a singular value decomposition of size @math , where @math is moderately larger than 1, e.g., @math . We prove that the preconditioned system is well-conditioned, with a strong concentration result on the extreme singular values, and hence that the number of iterations is fully predictable when we apply LSQR or the Chebyshev semi-iterative method. As we demonstrate, the Chebyshev method is particularly efficient for solving large problems on clusters with high communication cost. Numerical results demonstrate that on a shared-memory machine, LSRN outperforms LAPACK's DGELSD on large dense problems, and MATLAB's backslash (SuiteSparseQR) on sparse problems. Further experiments demonstrate that LSRN scales well on an Amazon Elastic Compute Cloud cluster. Let A be a real m×n matrix with m≧n. It is well known (cf. [4]) that @math (1) where @math The matrix U consists of n orthonormalized eigenvectors associated with the n largest eigenvalues of AA T , and the matrix V consists of the orthonormalized eigenvectors of A T A. The diagonal elements of ∑ are the non-negative square roots of the eigenvalues of A T A; they are called singular values. We shall assume that @math Thus if rank(A)=r, σ r+1 = σ r+2=⋯=σ n = 0. The decomposition (1) is called the singular value decomposition (SVD).