bugGNU Octave - Bugs: bug #41839, sprand/sprandn functions missing...

 
 

bug #41839: sprand/sprandn functions missing 4th input parameter

Submitter:  Eduardo Ramos Fernández <edu159>
Submitted:  Tue 11 Mar 2014 09:19:09 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Matlab Compatibility
Status:  Fixed Assigned to:  None
Originator Name:  Eduardo Ramos (edu159) Open/Closed:  * Closed
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

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.

Rik <rik5>
Group administrator
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).


Matlab:
>> tic; x = sprand (1e3, 1e3, 0.3, 0.7); toc
Elapsed time is 4.792556 seconds.

>> tic; x = sprand (2e3, 2e3, 0.3, 0.7); toc
Elapsed time is 48.590979 seconds.

Octave:
octave:42> tic; x = sprand (1e3, 1e3, 0.3, 0.7); toc
Elapsed time is 7 seconds.

octave:43> tic; x = sprand (2e3, 2e3, 0.3, 0.7); toc
Elapsed time is 56 seconds.


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.

Eduardo Ramos Fernández <edu159>
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.


tic; x = sprand (1e3, 1e3, 0.3, 0.7); toc
Elapsed time is 11.2219 seconds.




Rik <rik5>
Group administrator
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.


Eduardo Ramos Fernández <edu159>
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.


Eduardo Ramos Fernández <edu159>
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:


>> sprand (6, 4, 0.2, [1 2 3 4 5])

ans =

   (1,1)       2.0000
   (5,2)       3.0000
   (2,3)       0.7071
   (6,3)       0.7071
   (3,4)       4.0000

>> sprand (4, 6, 0.2, [1 2 3 4 5])

ans =

   (3,1)       0.7071
   (4,2)       3.0000
   (1,3)       4.0000
   (3,4)       0.7071
   (2,5)       2.0000


Same for sprandn.

Kai Torben Ohlhus <siko1056>
Group Member
Wed 12 Mar 2014 09:31:12 AM UTC, comment #1: 

This is the patch proposed.

(#file 30862)

Eduardo Ramos Fernández <edu159>
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 =U*S*V'.

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 = U1*U2*...Un , V=V1*V2...*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.

Eduardo Ramos Fernández <edu159>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #31002:  sprand_4rth_parameter_2.diff added by edu159 (10KiB - text/x-diff - Fix some issues of #30862 patch.)
file #30862:  sprand_4rth_parameter.diff added by edu159 (10KiB - text/x-diff)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Updated the item)
  • -email is unavailable- added by siko1056 (Posted a comment)
  • -email is unavailable- added by edu159 (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2014-03-24 rik5 StatusNone Fixed
        Open/ClosedOpen Closed
    2014-03-22 edu159 Attached File- Added sprand_4rth_parameter_2.diff, #31002
    2014-03-22 rik5 Summary sprand/sprandn functions with 4rth parameter missing in Octave sprand/sprandn functions missing 4th input parameter
    2014-03-11 edu159 Attached File- Added sprand_4rth_parameter.diff, #30862

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code