bugGNU Octave - Bugs: bug #44491, svd is slow and uses too much...

 
 

bug #44491: svd is slow and uses too much memory

Submitted by:  Max Görner <maxg>
Submitted on:  Mon 09 Mar 2015 07:12:06 AM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Performance
Status: Need InfoAssigned to: None
Originator Name: Open/Closed: Closed
Release: 3.8.2Operating System: GNU/Linux

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Mon 18 May 2015 09:28:56 PM UTC, comment #8:

I think we can close it, unless someone else still finds problems

Nir Krakauer <nir_krakauer>
Mon 18 May 2015 08:52:40 PM UTC, comment #7:

@Nir: Is there any change to core Octave that needs to be done, or is this something exclusive to the statistics package?

Can we close this bug report?

Rik <rik5>
Project Administrator
Tue 10 Mar 2015 07:05:02 AM UTC, comment #6:

The patch works for me.

Max Görner <maxg>
Mon 09 Mar 2015 09:54:15 PM UTC, comment #5:

I changed the script in the repository to use the economy SVD when n > p. This seems to solve the problem:

d = 0.01;
x = [-100:d:100]';
X = [x,x];
tic; s = princomp(X, "econ"); toc #took 9 s before fix, 0.002 s after

Nir Krakauer <nir_krakauer>
Mon 09 Mar 2015 03:35:30 PM UTC, comment #4:

Max, to answer your question about copyright, since you've apparently read Matlab's source code, we cannot accept any code from you for this problem.

However, your suggestion to use an economy svd decomposition and/or implement Matlab's "0" argument for svd can be a good place to start.

Jordi Gutiérrez Hermoso <jordigh>
Project Administrator
Mon 09 Mar 2015 02:57:43 PM UTC, comment #3:

From a previous IRC discussion, the problem is actually on svd being very very slow

Carnë Draug <carandraug>
Project Member
Mon 09 Mar 2015 01:13:13 PM UTC, comment #2:

Thanks for your bug report. Reassigning this bug report to the statistics package and adding maintainer in CC.

Mike Miller <mtmiller>
Project Administrator
Mon 09 Mar 2015 07:24:21 AM UTC, comment #1:

I forgot to add, that in the described kind the error occours in 32bit only. Under 64bit Octave tries to eat up all memory and was killed by STRG+C or reboot before the call to princomp returned.

Max Görner <maxg>
Mon 09 Mar 2015 07:12:06 AM UTC, original submission:

I'm developing some code under Matlab and Octave. However, princomp in Octave miserably.

My minimum working example is:

'X' is not even 1MiB in size, but I get this error. Matlab performs this code.

Furthermore, Matlab is way faster. If we change 'd' to 'd = 0.05' and perform the same code again, Octave takes 0.2 seconds and Matlab 0.001 seconds. On other matrices the ratio of ~100 reproduces.

I think I traced that down to the fact that Matlab ...
a) uses a special case with [coeff,~] = eig(X'*X)
b) calls 'svd(X,0)' whereas Octave calls 'svd(X)'.

If I enter the '0' in Octave's princomp function, it works. It is still a lot slower though.

Are there any reasons that the '0' is omittet? Are there any reasons that the special case using the eig function is not used? I'd create a patch if these questions are answered. Especially I'd like to know whether doing that call to eig would violate any copyrights.

sincerely,
Max Görner

Max Görner <maxg>

 

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

Attach File(s):
   
   
Comment:
   

No files currently attached

 

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 nir_krakauer (Posted a comment)
  • -unavailable- added by jordigh (Updated the item)
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by mtmiller
  • -unavailable- added by maxg (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 10 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Mon 18 May 2015 11:53:17 PM UTCrik5Open/ClosedOpen=>Closed
    Mon 18 May 2015 08:52:40 PM UTCrik5StatusNone=>Need Info
    Mon 09 Mar 2015 02:57:43 PM UTCcarandraugCategoryOctave Forge Package=>Octave Function
      Releaseother=>3.8.2
      Summarystatistics package: princomp is slow and uses too much memory=>svd is slow and uses too much memory
    Mon 09 Mar 2015 02:43:58 PM UTCjordighSummarystatistics package: princomp is inferior to Matlab\'s=>statistics package: princomp is slow and uses too much memory
    Mon 09 Mar 2015 01:13:13 PM UTCmtmillerCategoryOctave Function=>Octave Forge Package
      Release3.8.2=>other
      SummaryOctave\'s princomp is inferior to Matlab\'s=>statistics package: princomp is inferior to Matlab's
      Carbon-Copy-=>Added asnelt

    Back to the top


    Powered by Savane 3.1-cleanup1