bugGNU Octave - Bugs: bug #41426, OOM for issymmetric on sparse...

 
 

bug #41426: OOM for issymmetric on sparse matrices

Submitted by:  David Spies <dspyz>
Submitted on:  Sun 02 Feb 2014 04:24:41 AM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  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.

 

Mon 03 Feb 2014 05:12:17 PM UTC, comment #5: 

Thanks,

I'm a little confused though
How is that possible?  issparse(x) should just check a single bit or boolean or type or something, whereas the possibility of early termination as provided by 'any' can avoid examining nearly all the elements (if the matrix isn't symmetric).

Is the implicit copy operation associated with passing an argument to a function not being elided for issparse?
For that matter, does octave do copy ellision for functions which don't modify their inputs?  Is it something I should worry about?

Or is it just the case that in practice this method is generally only used inside an assert statement (in which case it's expected to always hold, so using 'any' doesn't provide any benefit)?

David Spies <dspyz>
Mon 03 Feb 2014 04:27:38 AM UTC, comment #4: 

I did some benchmarking and introducing the "issparse (x)" test actually slows things down more significantly than just using the proposed patch.  I also benchmarked the proposed patch against the existing code for full matrices and I find very little difference (< 2% and within the range of fluctuations that exist from run to run).  With that in mind I applied the patch here (http://hg.savannah.gnu.org/hgweb/octave/rev/7c0db9c4e454).

Rik <rik5>
Project Administrator
Sun 02 Feb 2014 04:41:26 PM UTC, comment #3: 

Ok, thanks

How do you test the efficiency?

David Spies <dspyz>
Sun 02 Feb 2014 04:31:22 PM UTC, comment #2: 

retval = any ((x != x.')(:));

seems slightly faster for full matrices and about the same speed as the original code, but the "(:)" creates an out of memory error for large sparse matrices as well. The difference in speed for the two versions for full matrices only seems to be about 5% so maybe we should just take your patch as is otherwise something like

if (issparse (x))
  retval = nnz (x != x.') == 0;
else
  retval = all ((x == x.')(:));
endif

might be appropriate

D.

David Bateman <dbateman>
Project Member
Sun 02 Feb 2014 04:13:52 PM UTC, comment #1: 

I fixed it (yay, my first bugfix).  Can someone commit my patch?

(file #30439)

David Spies <dspyz>
Sun 02 Feb 2014 04:24:41 AM UTC, original submission:  

octave:1> issymmetric(speye(100000))
error: out of memory or dimension too large for Octave's index type
error: called from:
error:   /usr/local/share/octave/4.1.0+/m/linear-algebra/issymmetric.m at line 43, column 14

David Spies <dspyz>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #30439:  sparse_symmetric.diff added by dspyz (683B - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by dbateman (Posted a comment)
  • -email is unavailable- added by dspyz (Submitted the item)
  • -email is unavailable- added by dspyz
  •  

    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 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2014-02-03 rik5 StatusNone => Fixed
        Open/ClosedOpen => Closed
    2014-02-02 dspyz Attached File- => Added sparse_symmetric.diff, #30439
    2014-02-02 dspyz Carbon-Copy- => Added davidnspies@gmail.com

    Back to the top


    Powered by Savane 3.5