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


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

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

Add a New Comment (Rich Markup)

You are not logged in

Please log in, so followups can be emailed to you.


( 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>
Project 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).

>> 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: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>
Project 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>
Project 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:

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)

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project 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.5