bugGNU Octave - Bugs: bug #33073, EIGS is inefficient when run from...

 
 

bug #33073: EIGS is inefficient when run from SVD [patch included]

Submitter:  None
Submitted:  Thu 14 Apr 2011 03:13:40 PM UTC
   
 
Category:  Libraries Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  jordigh
Originator Name:  Andrew Janowczyk Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * 3.4.0
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Fri 06 May 2011 12:07:21 AM UTC, comment #2: 

I rewrote the eigs.cc patch to work correctly when eigs is called standalone, rather than through svds.  Testing on my machine shows a 62% decrease in runtime (roughly 2X increase in performance) when run on large random matrices.  The changeset was applied to the development branch (http://hg.savannah.gnu.org/hgweb/octave/rev/8579e7a6e6e0)

Rik <rik5>
Group administrator
Thu 14 Apr 2011 03:54:35 PM UTC, comment #1: 

Thanks for the patches. I'll take a look at them over the weekend, if someone else doesn't beat me to them.

Jordi GutiƩrrez Hermoso <jordigh>
Group Member
Thu 14 Apr 2011 03:13:40 PM UTC, original submission:  

hey all,

i have a 12 core machine with 64bit ACML libraries linked into a 64bit octave.

when running:

A=rand(1000,10000);
[u,s,v]=svds(A,2);

a single core is used for the first stage of the computation. i tracked it down using gdb and came to the following:

on line 410 of eigs.cc:

symmetric = asmm.is_symmetric();

is computed by brute force (i.e. checking every single value to its transpose value), and when the matrix is large, this takes a very long time.

In actuality, if we look at the SVDS code (which is a nice wrapper around the eigs code), the computation which is performed is:


[V, s, flag] = eigs ([sparse(m,m), b; b', sparse(n,n)], ....


but:

[sparse(m,m), b; b', sparse(n,n)]

is always a symmetric matrix, making the asmm.is_symmetric() check redundant (and extremely time consuming).

this should have been taken care of by a flag which can be passed from svd to eigs in the opts.issym (which is even mentioned in the documentation), but alas it was not. even if it was, eigs.cc always performed the check.

i rewrote it to take these things to account. find two attached patches, one for eigs.cc and one for svds.m

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #23243:  eigs-patch added by None (2KiB - application/octet-stream)
file #23244:  svds-patch added by None (508B - application/octet-stream)

 

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 jordigh (Posted a comment)
  • -email is unavailable- added by None (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 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2011-05-06 rik5 StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2011-04-14 jordigh StatusNone Patch Submitted
        Assigned toNone jordigh
    2011-04-14 None Attached File- Added eigs-patch, #23243
        Attached File- Added svds-patch, #23244

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code