This project has moved. For the latest updates, please go here.

SVD error NonconvergenceException

Nov 15, 2013 at 3:22 PM
Hi,

while comparing some linear AX=B solution with SVD and traditional LU, I got (in one case) on the metanumeric SVD side only an error: NonconvergenceException; trying
    Dim A As RectangularMatrix    
    Dim ASVD As SingularValueDecomposition
......
    ASVD = A.SingularValueDecomposition 'here goes in error
....

I've dumped the A matrix
A=U D V                 
1.900019E+01    0.000000E+00    0.000000E+00    -1.385471E+02   1.027977E+05    1.520100E+04
0.000000E+00    1.900019E+01    0.000000E+00    -1.026921E+05   -1.499209E+02   1.410499E+05
0.000000E+00    0.000000E+00    1.900019E+01    -1.499527E+04   -1.410719E+05   0.000000E+00
-1.385471E+02   -1.026921E+05   -1.499527E+04   5.669219E+08    1.101144E+08    -7.618976E+08
1.027977E+05    -1.499209E+02   -1.410719E+05   1.101144E+08    1.670648E+09    8.113594E+07
1.520100E+04    1.410499E+05    0.000000E+00    -7.618976E+08   8.113594E+07    1.126334E+09
which can be decomposed by SVD (I used an excel library) in A=UDV, so should be a problem in the algorithm, is it?:
U
-6.174824E-05 1.351675E-06 -2.356797E-06 8.050991E-01 -5.929203E-01 1.615193E-02
-1.447477E-05 -1.041964E-04 1.439067E-04 -8.676587E-02 -1.446663E-01 -9.856690E-01
8.258497E-05 -1.726247E-05 2.451368E-05 5.867598E-01 7.921598E-01 -1.679159E-01
1.420417E-02 5.764131E-01 -8.170350E-01 3.960384E-14 -1.825392E-06 -1.801604E-04
-9.864629E-01 1.415825E-01 8.273592E-02 -4.827701E-14 1.026323E-04 -3.464403E-06
-1.633680E-01 -8.047996E-01 -5.706212E-01 -9.559026E-15 1.749057E-05 1.598354E-06

D
1.682500E+09 0.000000E+00 0.000000E+00 0.000000E+00 0.000000E+00 0.000000E+00
0.000000E+00 1.657746E+09 0.000000E+00 0.000000E+00 0.000000E+00 0.000000E+00
0.000000E+00 0.000000E+00 2.365830E+07 0.000000E+00 0.000000E+00 0.000000E+00
0.000000E+00 0.000000E+00 0.000000E+00 1.900019E+01 0.000000E+00 0.000000E+00
0.000000E+00 0.000000E+00 0.000000E+00 0.000000E+00 7.574556E-01 0.000000E+00
0.000000E+00 0.000000E+00 0.000000E+00 0.000000E+00 0.000000E+00 8.984791E-04

V
-6.1748E-05 1.3517E-06 -2.3568E-06 8.0510E-01 -5.9292E-01 1.6152E-02
-1.4475E-05 -1.0420E-04 1.4391E-04 -8.6766E-02 -1.4467E-01 -9.8567E-01
8.2585E-05 -1.7262E-05 2.4514E-05 5.8676E-01 7.9216E-01 -1.6792E-01
1.4204E-02 5.7641E-01 -8.1704E-01 -5.0733E-14 -1.8254E-06 -1.8016E-04
-9.8646E-01 1.4158E-01 8.2736E-02 3.9226E-15 1.0263E-04 -3.4644E-06
-1.6337E-01 -8.0480E-01 -5.7062E-01 2.2232E-15 1.7491E-05 1.5984E-06
Coordinator
Nov 25, 2013 at 6:43 PM
Thanks for this report. I have had one other report of SVD non-convergence, but didn't get a repro case from it, so this is very helpful. I have filed a bug (https://metanumerics.codeplex.com/workitem/7685) and will be looking at this as soon as possible.
Nov 26, 2013 at 9:55 AM
For your information I discovered that the problem arises when I try the SVD of a type A[m,n] RectangularMatrix which in true is m=n therefore is square, I changed the code as follows and the problem is disapperead:
    Dim TmpMat(,), TmpVec() As Double
.......
  .......
  'Matrix proper type definition for meta.numerics
    'SquareMatrix or RectangularMatrix
    If UBound(TmpMat, 1) = UBound(TmpMat, 2) Then
      ASVD = CType(New RectangularMatrix(TmpMat),  _
                   SquareMatrix).SingularValueDecomposition
    Else
      ASVD = New RectangularMatrix(TmpMat).SingularValueDecomposition
    End If
Coordinator
Jan 4, 2014 at 8:19 AM
This bug has been fixed in the latest check-in. Thanks for the report!
Apr 1, 2015 at 10:30 AM
Hi,

I am using Meta.Numerics to perform matrix calculations for a NLP project that I am busy with. After running for several hours a NonconvergenceException was thrown in Meta.Numerics.Matrices.MatrixAlgorithms.ExtractSingularValues while calculating the SVD. The original matrix being used is a 39169 x 392 rectangular matrix holding doubles. Do you have any idea how I canfix/prevent this from happening?

Regards,
Merrick
Coordinator
Apr 3, 2015 at 9:51 AM
Hi Merrick,

That's a very big matrix! It takes about 117 MB of memory just to hold the contents of a 39169 X 392 matrix of doubles. The theoretical scaling of the SVD algorithm for an M X N matrix (with M >> N) is M^2 N, and scaling up from smaller test cases on my own machine, I would expect your SVD to take about 6 hours. Perhaps less with a more performant machine, perhaps more if moving that much data in and out of active memory starts to take more time than actual computations, but that's at least the order-of-magnitude time I would expect.

It's hard for me to know whether the nonconvergence you observe is a general phenomenon that appears once input matrices get big enough, or is triggered by some very specific property of your matrix. Since getting your email, I have experimented with random matrices up to about 4000 X 400 without seeing any nonconvergence exception. Is there any particular aspect of your problem I should try to replicate? (Very sparse matrix? Entries vary in magnitude by many orders? Entries all positive, all negative, or mixed? Some notable pattern in the entries?) Would it be possible to actually get from you the matrix that triggers the exception? I will continue to experiment and analyze the algorithm, but your help would be appreciated.

If you are experienced with debugging, one helpful exercise would be to look at the values in the a and b arrays of the ExtractSingularValues method when the NonConvergenceException is triggered. The algorithm is trying to drive the values in the b array to zero (at which point the values in the a array are the singular values). It would be helpful to know how close it is getting. Are the values in b all very small and getting smaller, meaning the algorithm is working but we are not giving it long enough? Or have some NaN values appeared in either array, in which case they are likely to propagate in such a way that the algorithm will never converge?

Thanks again for the bug report!

Yours,
David