Tue 25 Mar 2014 01:04:00 AM UTC, comment #7:
I think your benchmarking shows that Octave is not unduly slow compared to Matlab, and that we can leave it as is.
|
Tue 25 Mar 2014 12:01:23 AM UTC, comment #6:
Rik that definitly looks better. I have tried at college your test case plus one with n and m being 2e3 in both Matlab and Octave (same pc).
As you can see there is not such a difference in execution times between Matlab's version and ours, so I am not unhappy. But yes it is not the fastest algorithm for large matrices. Maybe a C++ implementation would speed up things for the critical part of the code.
|
Mon 24 Mar 2014 03:40:50 AM UTC, comment #5:
I reviewed your patch and checked it in here (http://hg.savannah.gnu.org/hgweb/octave/rev/35a5e7740a6d).
sprand/sprandn had not been reviewed in a long time so I followed it up by overhauling the functions in this changeset (http://hg.savannah.gnu.org/hgweb/octave/rev/54a1e95365e1).
I did some tricks, like replacing the do/until loop with randperm and pre-calculating the speye() portion of the U/V matrices outside the loop, to speed things up. Although the algorithm works, it seems pretty slow for large matrices.
|
Sat 22 Mar 2014 12:35:17 PM UTC, comment #4:
I have added a replacement for the first patch. [https://savannah.gnu.org/bugs/download.php?file_id=31002 (#file 31002)
1) Test are fixed now.
2) Changed they way the situation is handled when the length of the vector rc is greater than min(m,n). It is related to point (2) Kai commented (see comment #2).
3) The singular values now are randomly generated always between 1 and rc when rc is scalar. That is to be compliant with Matlab.
|
Fri 21 Mar 2014 11:24:04 AM UTC, comment #3:
Thanks Kai for reviewing,
1) Yes, I copied the tests and forgot to change sprand with sprandn. I will change that.
2) According with Matlab's 2014a documentation : "If rc is a vector of length lr, where lr <= min(m,n), then R has rc as its first lr singular values, all others are zero". It is logical because if that condition is not fulfilled the number of elements in rc is greater than the number of elements in the main diagonal of a rectangular MxN matrix. That is not admissible unless some single values are dropped. Therefore I think that this is not needed to be changed.
|
Fri 21 Mar 2014 12:56:51 AM UTC, comment #2:
Your patch is working for me without problems, but I have some remarks to your patch:
1) In sprandn you simply copied the test cases from sprand, therefore you check the "wrong" functions there.
2) MATLAB 2013b accepts the following test cases:
Same for sprandn.
|
Wed 12 Mar 2014 09:31:12 AM UTC, comment #1:
This is the patch proposed.
(#file 30862)
|
Tue 11 Mar 2014 09:19:09 PM UTC, original submission:
I have modified sprand/sprandn functions to include a fourth parameter (rc, reciprocal condition number) compliant with Matlab. The approach I followed was:
From the singular value descomposition A =USV'.
1) If rc is a scalar then it would be the reciprocal condition number and I will set the minimum singular value and maximun singular value to fit to it. Then random values between vmin and vmax will be generated and sorted. With that S is build.
2)If rc is a vector, the values inside are the first singular values of the matrix. The rest will be 0. S is build from them as diagonal elements.
3)Once we have S we can see U and V as rotation matrices(they are ortogonal and , so they will be Jacobi rotation matrices formed by n rotations U = U1U2...Un , V=V1V2...Vn
In each iteration the matrix will be populated until density required is achieved (from testing with a 0.01% of error).
Feedback would be welcome.
|