Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
computational complexity of SVD

Subject: computational complexity of SVD

From: Frank

Date: 12 Jul, 2011 09:09:09

Message: 1 of 2

If A is a MxN matrix, what is the number of multiplications and additions when performing its SVD?

Any books for references?

Thanks a lot.

Subject: computational complexity of SVD

From: John D'Errico

Date: 12 Jul, 2011 11:37:09

Message: 2 of 2

"Frank " <allinone_2003@yahoo.com.hk> wrote in message <ivh2vl$nbi$1@newscl01ah.mathworks.com>...
> If A is a MxN matrix, what is the number of multiplications and additions when performing its SVD?
>
> Any books for references?

My one answer for the day...

Assuming the scheme used in matlab's SVD is the same as
that I used long ago when I wrote one using the Linpack
manual as a guide, it uses Householder rotations to
bi-diagonalize the matrix, then Givens rotations to kill off
the super-diagonal. Worse, each Givens rotation creates
another non-zero, that you must then kill off, chasing
elements off the edge of the matrix.

The first set of Householder rotations is easily counted for
flops, but the Givens rotations are simply done until that
super diagonal is killed off, so it becomes a purely iterative
process. And this second step will depend on the singular
values themselves, so a matrix with all nearly equal singular
values may have a very different run time in flops than a
matrix with widely separated singular values.

Finally, there is the standard issue with any large matrix
problem on a modern processor. There are caching issues
at several levels of cache, tricks employed by the blas,
multi-rthreading, etc. All of these things combine to make
it virtually IMPOSSIBLE to give an intelligent flop count
that would reflect reality anyway.

For a reference, you could check out the linpack guide,
if you could find one. Amazingly I still find one for sale
on Amazon.

http://www.amazon.com/LINPACK-Users-Guide-J-Dongarra/dp/089871172X/ref=sr_1_2?ie=UTF8&qid=1310470328&sr=8-2

John

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us