KrylovKit svd solver not running properly

New to Julia
1

I am encountering a problem with the svd solver of the KylovKit.jl package. I am trying to compute the SVD of a 90000X90000 sparse matrix, with a fraction of 2.4E-4 elements non-zero. However, the following execution

using KrylovKit;
K=deserialize(open( "K.dat" ));
Lambda,Phi,Gamma,info = KrylovKit.svdsolve(K, 1, krylovdim=3, tol=1E-3, maxiter=100);

does not terminate (it has been more than 48 hours). I am looking only for the top SVD, and my tolerance is also very high. The matrix K is close to the identity and its top singular value is 1.

Could suggest any reason why this relatively simple svd application is not working. Is there any known bug ?

Another curious thing is that my computer has 4 processors, but only one of them is being used during the operation.

The sparse matrix K is created from a complicated process involving the computation of a Gaussian kernel over a data-set. So i have not provided those details.

2

The svd solver is probably the least tested. That being said, I notice you have krylovdim=3. Is there any reason for choosing it so so small? You can get more info about the convergence by using the verbosity keyword

1 Like
3

I was under the impression that it is sufficient for the krylov dimension needs to be 2L+1, where L is the number of singular values/vectors required.
I will try out with the verbosity command.
Can you suggest any other tried and tested package. I had earlier reported a problem / bug with the svds() routine here, to which you had suggested KrylovKit.jl

4

2L+1 is theoretically sufficient, but I would suggest larger to get faster convergence. krylovdim around 20 to 30 seems to be an often made choice.

1 Like
5

I now ran the command without specifying the krylov dimension, as follows

@time Lambda,Phi,Gamma,info = KrylovKit.svdsolve( K, L, verbosity=3, tol=1E-3, maxiter=100 );

The process has been stuck at the 30th iteration for several hours. Only 1 out 4 processors is still being utilized.

[ Info: GKL iteration step 1: normres = NaN
[ Info: GKL iteration step 2: normres = NaN
...
[ Info: GKL iteration step 30: normres = NaN

Do you know what this could mean ? Also, can you suggest any other svd solver ? svd solving is very crucial for many numeric applications.

6

You can try svdl in IterativeSolvers.

https://juliamath.github.io/IterativeSolvers.jl/dev/svd/svdl/

The fact that normres is NaN is concerning. What does it return when you set maxiter=1?

1 Like
7

Setting maxiter=1 still has the same problem :

julia> @time Lambda,Phi,Gamma,info = KrylovKit.svdsolve( K, 1, verbosity=3, tol=1E-3, maxiter=1 );
[ Info: GKL iteration step 1: normres = NaN
...
[ Info: GKL iteration step 30: normres = NaN

The process stops indefinitely after iteration step 30.

8

Thank you for the suggestion. I looked up the documentation here. I am having travel in deciphering the output. I tried the routine on a simple identity amtrix of size 4.

A = Diagonal(ones(4));
X,L = IterativeSolvers.svdl(A,nsv=3,vecs="both");

The problem is that I do not know how the SVD results are stored in X,L. Upon checking, I find

julia> X
SVD{Float64,Float64,Array{Float64,2}}(Array{Float64}(4,0), [7.76331, 5.56498, 3.40801], Array{Float64}(0,4))

julia> L
IterativeSolvers.PartialFactorization{Float64,Float64}([0.148432 -0.00588581 … 0.993988 -0.993989; 0.016312 -0.000646821 … 0.109257 -0.109253; 0.000746992 -2.96202e-5 … 0.00503284 -0.0050266; 0.000748214 -2.9669e-5 … 0.00502097 -0.00501883], [1.15233 -0.0327544 … -0.99399 0.99399; 0.126635 -0.00359955 … -0.109242 0.109243; 0.00579912 -0.000164836 … -0.00501194 0.00501381; 0.00580861 -0.000165107 … -0.00501379 0.00501443], [7.76331 0.0 … 0.0 0.0; 0.0 5.56498 … 0.0 0.0; … ; 0.0 0.0 … 2.34803 2.34803; 0.0 0.0 … 0.0 3.34803], 3.348034540367908)

I do not see 3 singular values equal to one. Where can I recover the left and right singular vectors from ? The documentation does not indicate that.

In other programs such as Matlab, the documentation clearly provides this basic information. Usually people are interested in both the singular vectors and values.

9

Your X here is an SVD object, which is well documented here.

10

Could you share K.dat ? It should indeed not happen that you get NaN for normres (and I should probably check for that and error out).

11

It is a 3GB file, so I shared it on Google drive with you
https://drive.google.com/open?id=1d_v-qyLhaZcfrZ6X0wW3tKgf_2GRtjvr

12

Thank you. I am having some problems with this package, which I have posted on a separate thread

13

Your matrix contains Inf values, so any vector you multiply it with will also come to have infinite norm.

1 Like
14

Thank you for the painstaking effort, that was indeed the problem. It had never occurred to me.