How to accelerate the SVD algorithm?

Click For Summary

Discussion Overview

The discussion revolves around the performance of the Singular Value Decomposition (SVD) algorithm implemented in C compared to MATLAB's SVD. Participants explore the algorithms used by MATLAB, specifically DGESVD from LAPACK, and discuss potential optimizations for improving the performance of SVD implementations.

Discussion Character

  • Debate/contested
  • Technical explanation
  • Exploratory

Main Points Raised

  • One participant expresses disappointment in their C implementation of the GR SVD algorithm, noting it performs worse than MATLAB's SVD.
  • Another participant points out that MATLAB uses the DGESVD routine from LAPACK for real-valued matrices and suggests checking the documentation for more information.
  • A participant indicates they have found the source code for DGESVD but seeks to understand the reasons behind its speed.
  • Some participants criticize others for not utilizing MATLAB's documentation effectively and for asking questions that have already been answered in the documentation.
  • There are suggestions for optimizing SVD implementations through processor-specific techniques, such as vectorization, blocking, and loop unrolling.
  • Participants mention the existence of optimized libraries like Intel's hand-tuned BLAS, ATLAS BLAS, and GOTO BLAS, which can significantly outperform naive implementations.
  • One participant recommends exploring C++ template metaprogramming with Eigen2 as a potential solution for efficient SVD implementations.

Areas of Agreement / Disagreement

Participants exhibit disagreement regarding the effectiveness of documentation usage and the necessity of asking questions that may already have answers. There is no consensus on the best approach to optimize SVD implementations, as various strategies and libraries are suggested.

Contextual Notes

Participants express varying levels of familiarity with MATLAB and its documentation, leading to misunderstandings about the information available. The discussion also highlights the complexity of optimizing algorithms beyond just the mathematical implementation.

Who May Find This Useful

Individuals interested in algorithm optimization, particularly in the context of SVD and numerical computing, as well as those looking to implement efficient algorithms in C or C++.

irongreat
Messages
8
Reaction score
0
I've written a program in c language in terms of the GR SVD algorithm. To my dispointment,its performance is worse than the svd of matlab. I wish to get to know which algorithm the MATLAB used. Who may tell me? Thanks.
 
Technology news on Phys.org
Sigh.

irongreat said:
I've written a program in c language in terms of the GR SVD algorithm. To my dispointment,its performance is worse than the svd of matlab. I wish to get to know which algorithm the MATLAB used. Who may tell me?

Matlab will.

Code: 
doc svd
 
Oh, you said nothing.
 
irongreat said:
Oh, you said nothing.

No, I told you that if you had had the startlingly obvious idea to check the documentation for svd in Matlab, you'd find which algorithms it uses to compute singular value decompositions.

If you want to be snippy towards someone who's given you the answer to your question, that's your business.
 
You are not friendly,Shoehorn. I have read the MATLAB document. I know it use DGESVD. But I cannot find the details of the algorithm. So I asked the question.
Do take any thing for granted. Ok? GUY
 
As a matter of fact ,I have found the source code of the algorithm. But I wonder the cause of its fast speed.So I hope to find the primitive document about the algorithm.
Who may tell me?
 
irongreat said:
Oh, you said nothing.
Actually, shoehorn said everything. It was enough for you to figure out that, for real-valued matrices, MATLAB uses the DGESVD routine from LAPACK. That should have been enough of a clue for you to find the http://www.netlib.org/lapack/lug/" , which is probably what you were looking for.
 
Last edited by a moderator:
irongreat said:
You are not friendly,Shoehorn. I have read the MATLAB document. I know it use DGESVD... So I asked the question.

So you know which algorithm Matlab uses for singular value decompositions, and yet you still decided to waste everyone's time by asking which algorithm Matlab uses for singular value decompositions?

Matlab has the best documentation of any software I've ever seen. Ever. Learn how to use it. 90% of the questions about Matlab on this forum are from people who are too lazy to read the documentation and instead want to waste other people's time by getting them to do work that they are too lazy/stupid to perform.
 
Last edited:
So you know which algorithm Matlab uses for singular value decompositions, and yet you still decided to waste everyone's time by asking which algorithm Matlab uses for singular value decompositions?

Matlab has the best documentation of any software I've ever seen. Ever. Learn how to use it. 90% of the questions about Matlab on this forum are from people who are too lazy to read the documentation and instead want to waste other people's time by getting them to do work that they are too lazy/stupid to perform.

Don't insult me,ok? I only implement sth not by matlab.
If I used matlab, I not ask the question.

Matlab is a good software, but it is too large , I cannot put it into a hardware. So I have to implement svd by myself.
 
  • #10
I have to research linpack source code. It is more complicated than read the primitive document.

Sigh.
 
  • #11
I dislike those who take themselves as industrious men.
Is it a a great thing to develop sth on matlab?
 
  • #12
I dislike them also.

By taking advantage of the specific processor-memory architecture you can accelerate
computations in way not directly related to the mathematical algorithm:

using processor specific vectorization (SSE2,3,...)
blocking,
loop unrolling, ...

You would want to

optimize main memory to L2-cache traffic,
avoid TLB misses

and possibly many other things.

When you go up against MATLAB you are going up against Intel hand tuned BLAS
(10 times faster than naive code depending on the operation).

Large systems that try to optimize on different architectures are
ATLAS BLAS, GOTO BLAS.

Look for paper by Jack Donguerra for the issues involved.

Naive C-code is hopeless.

For a reasonably small system that accomlishes quite a lot using C++ template metaprogramming see Eigen2:
http://eigen.tuxfamily.org/index.php?title=Main_Page

This is your best chance to do something yourself and is also very elegant code.
 

Similar threads

Learning data structures and algorithms in different programming languages
  • · Replies 86 ·
3
Replies
86
Views
3K
Non youtube courses and paid textbooks to learn algorithms?
  • · Replies 8 ·
Replies
8
Views
4K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
Fast reciprocal square root algorithm
  • · Replies 30 ·
2
Replies
30
Views
7K
What is the fastest algorithm for finding large prime numbers?
  • · Replies 14 ·
Replies
14
Views
3K
Algorithm for the min. distance over a set of points randomly distributed
  • · Replies 3 ·
Replies
3
Views
2K
When should a beginner programmer learn vims/emacs?
  • · Replies 25 ·
Replies
25
Views
1K
How do you handle algorithms (memorize vs. reference)?
  • · Replies 13 ·
Replies
13
Views
3K
Can someone recommend an algorithm to optimize this data
  • · Replies 25 ·
Replies
25
Views
3K
Algorithm running time discrepencies
  • · Replies 7 ·
Replies
7
Views
3K