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

 
 

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

Submitter:  Rik <rik5>
Submitted:  Wed 21 Sep 2011 05:51:10 AM UTC
   
 
Category:  Libraries Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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.


## -*- texinfo -*-
## @deftypefn {Function File} {} __isequal__ (@var{nans_compare_equal}, @var{x1}, @var{x2}, @dots{})
## Undocumented internal function.
## @end deftypefn


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>
Group 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>
Group Member
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>
Group 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>
Group Member
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>
Group Member
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

x = sprand (1000, 1000, 0.9);
density = nnz (x) / 1000^2

density =  0.59345


Rik <rik5>
Group administrator

 

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

Attach Files:
   
   
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
  • -email is unavailable- added by jordigh (Posted a comment)
  • -email is unavailable- added by rik5 (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 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2011-09-23 jordigh StatusNone Fixed
        Open/ClosedOpen Closed
    2011-09-22 jordigh Attached File- Added sprand.patch, #24005

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code