An Inverse Free Preconditioned Krylov Subspace Method For Computing Singular Value Of A Large Matrix

The calculation of matrix singular value decomposition(SVD)is an important problem in the field of numerical computation.It plays an imporant role in computing the best rank k approximation,forming the pseudo inverse of matrix and solving ill posed least squares problems.In the application field,the singular value of the matrix is widely applied in image compression,image denoising,face recognition,text retrieval,Data mining,latent index and user recommendation.Computing some small singular values and corresponding left-right singular vectors of large-scale sparse matrix A is an important research topic in the field of numerical computation.A common method is to transform them into augmented matrix H or cross product matrix C.When converted into the calculation of eigenvalue pairs of augmented matrix H,the existence of zero eigenvalues in H often fails to converge to the desired results.When converted into the calculation of eigenvalue pairs of cross product matrix C,the eigenvalue of C is the square of the singular value of A.When A has a small singular value,the accuracy of the calculated small singular value by the eigenvalue of C may be much lower than expected.Moreover,if the small singular value of A is very close to other singular values,after squaring,the small eigenvalue corresponding to C will be closer to other eigenvalues,and then the convergence of the iteration method will be very slow.In this thesis,we transform the problem of calculating singular triples of A into the problem of calculating corresponding eigenvalues of cross product matrices.First,we review a Krylov subspace method called eigifp,which is mainly used to calculate the generalized eigenvalues of symmetric matrices,and then extend the algorithm to calculating singular triples.Next we introduce a two-side Krylov subspace method called svdifp.In each step,svdifp constructs a Krylov subspace containing right singular vector information.On the basis of this subspace,we construct a two-side projection of the original matrix A,and then calculate the minimum singular triples of the projection matrix to obtain the approximation of A.The svdifp method also chooses a robust incomplete decomposition to get the preprocessing matrix to accelerate the convergence of the algorithm.Since the current svdifp is only suitable for calculating small singular values and corresponding right singular vectors,in this paper,we improve the existing svdifp algorithm so that it can also calculates left singular vectors and the accuracy of the left singular vectors is guaranteed to be the same as that of the right singular vectors.Then we discuss the stopping criteria of the svdifp algorithm further.Finally,numerical experiments were carried out to validate the dependence of svdifp method on the dimension of Krylov subspace,the accuracy of computed singular vector,and the optimization of stopping criteria.