bugGNU Octave - Bugs: bug #49940, The svd function takes very long...


bug #49940: The svd function takes very long time for big matrices

Submitted by:  Saleh <sabmab>
Submitted on:  Tue 27 Dec 2016 10:55:26 AM UTC  
Category:  Performance Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  saleh 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.


( Jump to the original submission)

Thu 29 Dec 2016 12:13:35 AM UTC, comment #6:

I changed the default driver in Octave to gesdd which is 5X faster in this cset (http://hg.savannah.gnu.org/hgweb/octave/rev/750c8b4b7164). The original reporter can either build from the development sources, or just switch to "gesdd" using the svd_driver function with the current version of Octave (4.2.0).

Rik <rik5>
Project Administrator
Wed 28 Dec 2016 06:29:57 PM UTC, comment #5:

See also bug #29487.

John W. Eaton <jwe>
Project Administrator
Wed 28 Dec 2016 05:34:15 PM UTC, comment #4:

I'm going to ask on the Octave Maintainer's list about switching the core algorithm to gesdd.

Rik <rik5>
Project Administrator
Wed 28 Dec 2016 05:09:24 PM UTC, comment #3:

I don't think the large slowdown is attributable to Octave. Octave is an interpreter which relies on other solid linear algebra libraries like BLAS and LAPACK to do the real work. The svd function is rather special in that there are at least two different library functions in LAPACK that could be used. Octave allows you to switch which function is called with the svd_driver() function. Try 'help svd_driver' to get the documentation.

I coded up a test to see if svd driver makes a difference and it definitely does for the test case used here. The code is shown below and attached as tst_svd_driver.m

The results are

Using gesdd the slowdown is only 2X which is probably acceptable. This also seems to be roughly the slowdown that Matlab experiences for the 1e3 and 2e3 cases.

(file #39325)

Rik <rik5>
Project Administrator
Wed 28 Dec 2016 02:13:28 AM UTC, comment #2:

results of octave compared to matlab

I found in the svd.cc file at line 235 some relevant part (for real matrix)

I belive the culprit is one of two things
a- ovl :it is copying the matrix, instead of copying its address
b- the algorithms result.left_singular_matrix and right_singular_matrix are very expensive to evaluate in octave.

Saleh <sabmab>
Tue 27 Dec 2016 05:06:41 PM UTC, comment #1:

I benchmarked using the script tst_svd.m below

I tried 1e3, 2e3, and 3e3 for the size of the matrices. With the developent version of Octave I get

As you can see, requesting more than just the singular values is about 10X slower. Could you try running the same script in Matlab to get an idea of the size of the performance hit there.

Rik <rik5>
Project Administrator
Tue 27 Dec 2016 10:55:26 AM UTC, original submission:

When running the svd function without returning parameter it perform well (like Matlab).

When adding output parameters, the performance drops significantly(40x, in this case), which is not the case in Matlab.

I didn't see this behavior for other functions such as the "inv" function.

Saleh <sabmab>


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

Attach Files:

Attached Files
file #39325:  tst_svd_driver.m added by rik5 (337B - d2l/unknowntype)


Depends on the following items: None found

Items that depend on this one: None found


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

    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
    2016-12-29 rik5 StatusConfirmed => Fixed
        Open/ClosedOpen => Closed
    2016-12-28 rik5 Attached File- => Added tst_svd_driver.m, #39325
    2016-12-27 rik5 StatusNone => Confirmed

    Back to the top

    Powered by Savane 3.3