[Octave-bug-tracker] [bug #33073] EIGS is inefficient when run from SVD [patch included]

[anonymous]

URL:
  <http://savannah.gnu.org/bugs/?33073>

                 Summary: EIGS is inefficient when run from SVD [patch
included]
                 Project: GNU Octave
            Submitted by: None
            Submitted on: Thu 14 Apr 2011 03:13:40 PM UTC
                Category: Libraries
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Improvement/Optimization
                  Status: None
             Assigned to: None
         Originator Name: Andrew Janowczyk
        Originator Email: address@hidden
             Open/Closed: Open
         Discussion Lock: Any
                 Release: 3.4.0
        Operating System: GNU/Linux

    _______________________________________________________

Details:

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




    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Thu 14 Apr 2011 03:13:40 PM UTC  Name: eigs-patch  Size: 2kB   By: None

<http://savannah.gnu.org/bugs/download.php?file_id=23243>
-------------------------------------------------------
Date: Thu 14 Apr 2011 03:13:40 PM UTC  Name: svds-patch  Size: 508B   By: None

<http://savannah.gnu.org/bugs/download.php?file_id=23244>

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?33073>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/