bugGNU Octave - Bugs: bug #34352, sprand/sprandn density argument is...

 
 

bug #34352: sprand/sprandn density argument is not very accurate

Submitted by:  Rik <rik5>
Submitted on:  Wed 21 Sep 2011 05:51:10 AM UTC  
 
Category: LibrariesSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Inaccurate Result
Status: FixedAssigned to: None
Originator Name: Open/Closed: Closed
Release: devOperating System: GNU/Linux

Add a New Comment(Rich Markup)
   

You are not logged in

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

 

Fri 23 Sep 2011 04:25:24 PM UTC, comment #5:

Do you want to update the Copyright notice in _sprand_impl_ to add your name and reflect your own work? Right now the file is attributed to Paul Kienzle from 2004-2011 but this seems to be a substantial enough change to warrant a new copyright holder going forward. Perhaps one should ask jwe about these things. In the rewrite of the statistics functions I added my Copyright beginning in this year (2011) to the existing Copyright which covered the years XXXX-2011.

It seems like you could do away with the texinfo documentation in _sprand_impl_ as well since it seems to cover a different function.

Alas, I don't think I have many good ideas about specifying the singular values. Maybe, you could do something like the inverse of the singular value decomposition? Start with a diagonal matrix of specified singular values (easy) and then multiply from the left by a random MxM unitary matrix and from the right by a random NxN unitary matrix. However, one is left with the problem of creating a random unitary matrix.

Rik <rik5>
Project Administrator
Fri 23 Sep 2011 07:01:56 AM UTC, comment #4:

Okay, I pushed it:

http://hg.savannah.gnu.org/hgweb/octave/rev/5976ba269538

I note that this implementation would make it quite easy to let d be larger than 1 and thus be interpreted as the exact desired number of nonzero entries instead of the density percentage. I was tempted to make that change, but wasn't sure about it.

However, a more pressing issues seems to be to implement the algorithm that allows specifyiing the condition number or singular values of the resulting sparse matrix. I don't even know what this algorithm might be. Matlab hints at "rank 1 updates", but I don't immediately see how to do this.

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Thu 22 Sep 2011 03:47:17 AM UTC, comment #3:

My opinion is that this does qualify as a bug. I consider it a bug because the user requests a given behavior and Octave neither honors the request nor warns that it has failed. In the same vein, we don't strive to match undocumented Matlab behavior so I would push to commit the patch for sprand. It seems perverse to rely on a function to not do what it is documented to do. If sprand actually performs according to its documentation then user's can reclaim the old behavior by adjusting the density value down.

Rik <rik5>
Project Administrator
Thu 22 Sep 2011 02:44:13 AM UTC, comment #2:

I pushed a change to randperm to implement k-subsets:

http://hg.savannah.gnu.org/hgweb/octave/rev/2896c083576a

With this change, the attached cset implements the precise sprand density you speak of. It also speeds up most calls of sprand. I'm not pushing it, though, because it breaks apparent (but not documented) Matlab compatibility.

(file #24005)

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Wed 21 Sep 2011 11:42:06 PM UTC, comment #1:

Is this a bug?

The matrix you're testing isn't really sparse. If you want a 90% full sparse matrix, you end up using more memory to store it than if you use dense storage.

Asking around, it seems sprand's current behaviour matches Matlab's (in my opinion, undocumented) behaviour.

That being said, this seems like really bizarre behaviour. I'm working on perhaps a more sensible behaviour that uses randperm, and I saw that our implementation of randperm is incompatible with Matlab's documented version.

I notice that there are two Matlab features of sprand that we haven't implemented yet, which allow you to specify the condition number or the singular values. That seems like a more pressing issue for sprand.

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Wed 21 Sep 2011 05:51:10 AM UTC, original submission:

The sprand routine creates a random sparse matrix filled to a density D. In practice, the resulting matrix density is usually 1-36% different from the requested value.

Sample code

Rik <rik5>
Project Administrator

 

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

Attach File(s):
   
   
Comment:
   

Attached Files
file #24005:  sprand.patch added by jordigh (1KiB - text/x-diff)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by jordigh (Posted a comment)
  • -unavailable- added by rik5 (Submitted the item)
  •  

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

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 23 Sep 2011 07:01:56 AM UTCjordighStatusNone=>Fixed
      Open/ClosedOpen=>Closed
    Thu 22 Sep 2011 02:44:13 AM UTCjordighAttached File-=>Added sprand.patch, #24005

    Back to the top


    Powered by Savane 3.1-cleanup1