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

 
 

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

Submitted by:  None
Submitted on:  Thu 14 Apr 2011 03:13:40 PM UTC  
 
Category: LibrariesSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Performance
Status: FixedAssigned to: Jordi GutiĆ©rrez Hermoso <jordigh>
Originator Name: Andrew JanowczykOriginator Email: -unavailable-
Open/Closed: ClosedRelease: 3.4.0
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.

 

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>
Project 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>
Project AdministratorIn charge of this item.
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 File(s):
   
   
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
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by jordigh (Posted a comment)
  • -unavailable- added by None (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 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 06 May 2011 12:07:21 AM UTCrik5StatusPatch Submitted=>Fixed
      Open/ClosedOpen=>Closed
    Thu 14 Apr 2011 03:54:35 PM UTCjordighStatusNone=>Patch Submitted
      Assigned toNone=>jordigh
    Thu 14 Apr 2011 03:13:40 PM UTCNoneAttached File-=>Added eigs-patch, #23243
      Attached File-=>Added svds-patch, #23244

    Back to the top


    Powered by Savane 3.1-cleanup1