SVD Error

General CULA Dense (LAPACK & BLAS) support and troubleshooting. Use this forum if you are having a general problem or have encountered a bug.

SVD Error

Postby sainath » Tue Apr 27, 2010 3:15 pm

Hi,

I am new to CULA Tools and have been getting good speedups using this.

I was trying to implement a basic program that computes SVD for a matrix of size 540x3. I also perform the same SVD in Octave and it seems that the results are not matching.

Is there something in CULA that I should be aware of when I calculate SVD for these kind of matrices i.e No. of Rows >>>> No. of Columns.

The S matrix computed is correct and matches with Octave one. The U and VT matrices are not. Any help is appreciated.Thanks.

Code: Select all
nzcount = 540;

float *A = (float*) malloc (nzcount*3*sizeof(float));
float* W = (float*) malloc( imin(nzcount,3) * sizeof(float));
float* U = (float*) malloc( nzcount * nzcount * sizeof(float));
float* VT = (float*) malloc( 3 * 3 * sizeof(float));

//Take SVD
s = culaSgesvd('A', 'A', nzcount, 3, A, nzcount, W, U, nzcount, VT, 3);
checkStatus(s);
sainath
 
Posts: 5
Joined: Sun Apr 18, 2010 11:17 am

Re:SVD Error

Postby kyle » Tue Apr 27, 2010 8:04 pm

How are the results of the reconstruction: A = U*S*VT

SVD is a fairly complicated algorithm with many strategies based on input size and therefor might return a different, but correct results.
kyle
Administrator
 
Posts: 301
Joined: Fri Jun 12, 2009 7:47 pm

Re:SVD Error

Postby sainath » Tue Apr 27, 2010 8:15 pm

The reconstruction matches with the original input. Sorry if my title mislead by saying SVD is wrong.

The differences between reconstructed image and the original one is fairly low for single precision calculations.

sum(A-U*S*VT) = -0.0096

But as MATLAB/Octave both use LAPACK internally, I am wondering if CULA uses different strategies while using LAPACK or is it basically a from scratch implementation for SVD.

The algorithm after svd follows like this:
[U,W,V] = svd(A)
b = V*(W\(U'*Y));
yco = A*b;

I am getting different values for b and obviously yco. Is there any way I can make sure that culaSgesvd matches with svd from Octave/MATLAB.

Additional Links:
Octave Code
C Code
sainath
 
Posts: 5
Joined: Sun Apr 18, 2010 11:17 am

Re:SVD Error

Postby kyle » Tue Apr 27, 2010 8:25 pm

We use the same strategies in the LAPACK SVD function but our algorithm cross over points have been tuned for optimal GPU performance. I'll take a look at your code samples sometime this week and let you know if I see anything strange.
kyle
Administrator
 
Posts: 301
Joined: Fri Jun 12, 2009 7:47 pm

Re:SVD Error

Postby kyle » Wed Apr 28, 2010 7:31 am

Hi sainath,

I ran your script to generate a test matrix and I analyzed the code within our testing platforms. The results seemed within the appropriate error bounds:

|| U * U' || / || I || = 5.7e-006
|| VT' * VT || / || I || = 3.0e-007
|| U * S * VT || / || A || = 1.9e-007

Where the one norms are analyzed.

Additionally, the code paths between CULA and Octave's LAPACK implementations should be the same. There is machine specific tuning parameter for algorithmic cross over point, but the I'd imagine all implementation will take the recommended M >> N path.
kyle
Administrator
 
Posts: 301
Joined: Fri Jun 12, 2009 7:47 pm

Re:SVD Error

Postby sainath » Wed Apr 28, 2010 8:07 am

Thanks for all the effort you put in. Due to the small difference (I would say not even differences - not having unique solutions) in the results from svd.. the final prediction of the price in case of C is fluctuating a little whereas in Octave for the given test case it stays 9.5-10.5 (in C it is 4.5-9.5). I need to look into the actual algorithm once more to see if the Octave implementation missed anything.

I am trying to look into the code of Octave's svd implementation to see if they have done anything special like conditioning the matrices for faster convergence or something like that. I will let you know if I find anything interesting. Thanks.
sainath
 
Posts: 5
Joined: Sun Apr 18, 2010 11:17 am

Re:SVD Error

Postby kyle » Wed Apr 28, 2010 8:29 am

I believe the native types in Octave are double precision so this might account for the difference.
kyle
Administrator
 
Posts: 301
Joined: Fri Jun 12, 2009 7:47 pm

Re:SVD Error

Postby sainath » Wed Apr 28, 2010 9:30 am

Might be the case. Although I cant test it as I am only using CULA Basic version.

In the algorithm I have to perform Least squares regression for an overdetermined matrix. Section 5.5 in this document is interesting, and this matrix fits that particular case. I believe Octave guys might also have implemented this in a similar way.

http://www.mathworks.com/moler/leastsquares.pdf

So, instead of SVD way of solving for least squares, they seem to be using QR for m>>n. I will try the same and will let you know if I succeed.

EDIT: Sorry, I was wrong. The code explicitly uses SVD way to solve Least Squares and the results are not matching. I guess it has to do something with the stability and perturbations of SVD\LS.

http://www.ces.clemson.edu/~petersj/Agents/MatLabNA/MatLabNA004.html
sainath
 
Posts: 5
Joined: Sun Apr 18, 2010 11:17 am

Re:SVD Error

Postby kyle » Wed Apr 28, 2010 9:46 am

You could try forcing Octave to use single precession to test the stability of your algorithm. In MATLAB this is just:

[...] = svd( single(A) )

I'd imagine Octave is similar.
kyle
Administrator
 
Posts: 301
Joined: Fri Jun 12, 2009 7:47 pm

Re:SVD Error

Postby sainath » Wed Apr 28, 2010 10:26 am

Wow.. never mind.. all along I'm the stupid one. I don't know which matrices I have been comparing but right now.. I see that the result matrix i.e b matches with the one from Octave. I writed out the A matrix to a file and calculated svd and b from Octave, the result matches with the one that I write out from C. I guess I found myself a quite little bug. Sorry if I have wasted your time.

I tried forcing single precision.. still U and V differ from the the ones that are generated by Octave, but seems to me that as LS uses U and V again.. the result should be the same from both cases. Thanks.

EDIT: Also I had this confusion regarding Column major data ordering:

for a matrix A with M rows and N columns, if it is ordered in column major data, then the for the element at row i and column j is A[i+j*M]??

CULA Programming guide says that it is A[i*LDA+j] (LDA - no. of rows for column major data i.e M), am I missing something here?
sainath
 
Posts: 5
Joined: Sun Apr 18, 2010 11:17 am

Re:SVD Error

Postby kyle » Wed Apr 28, 2010 10:57 am

... for a matrix A with M rows and N columns, if it is ordered in column major data, then the for the element at row i and column j is A[i+j*M]??

This is correct. LDA is important because sometimes M != LDA.
kyle
Administrator
 
Posts: 301
Joined: Fri Jun 12, 2009 7:47 pm

Re: SVD Error

Postby aurelius » Wed Aug 25, 2010 6:10 am

Hi,

I have kind of a similar problem. I have a matrix and I want to run SVD on it. However, the results that I get are all NaN and I can't find where is the error. The code seems the same as posted here, but I get an error code 6, which I couldn't find what represents. Anyways, my code is:

Code: Select all
float* Dlin = (float*) malloc(2 * 4 * 9 * sizeof(float)) ;
float* S = (float*) malloc(2 * 4 * sizeof(float)) ;
float* U = (float*) malloc(2 * 4 * 2 * s * sizeof(float)) ;
float* VT = (float*) malloc(9 * 9 * sizeof(float)) ;

culaStatus status ;
    culaInitialize() ;
    status = culaSgesvd('A', 'A', 2 * 4, 9, Dlin, 2 * 4, S, U, 2 * 4, VT, 9);
//     checkStatus(status) ;
    if( status != culaNoError )
    {
        if( status == culaDataError )
            printf("Data error with code %d, please see LAPACK documentation\n",
                   culaGetErrorInfo());
    }


Do you see any noticeable errors. When I run it, all three matrices are nan's.

Thanks :)
aurelius
 
Posts: 1
Joined: Tue Aug 17, 2010 12:19 am

Re: SVD Error

Postby kyle » Wed Aug 25, 2010 6:36 am

A positive error code means the SVD algorithm didn't converge on the singular values. The 6 means that 6 superdiagonals of the intermediate bidiagonal form B did not converge to zero.

Are you sure you are passing good data into the routine? In your posted example you allocate the data and pass it straight into the function. Is there something that puts data in there first?
kyle
Administrator
 
Posts: 301
Joined: Fri Jun 12, 2009 7:47 pm


Return to CULA Dense Support

Who is online

Users browsing this forum: No registered users and 1 guest

cron