Re: [eigen] BDCSVD update

[Jitse Niesen <jitse@xxxxxxxxxxxxxxxxx>]

On Tue, 20 Aug 2013, Gael Guennebaud wrote:

> Lapack is using rational approximations to help solving the non-linear
> equation. There is also this paper [1] that suggest using the
> fast-multipole-method, but before moving to other algorithms we should make
> some performance analysis to see how far we can get with that one.

I just committed a rather ad-hoc implementation of rational interpolation. 
It does bring down the number of iterations substantially, and thus speed 
up the SVD especially for smallish matrices (size around 100). On the 
negative side, I am not convinced that my implementation will terminate in 
all cases.

The paper "Solving secular equations stably and efficiently" by Li appears 
to be a good description on how to do this properly, but it will take a 
while to implement. This will be the next step.

I expect that fast multipole will be tricky to implement (the non-linear 
equation has to be solved accurately, so you have to be very careful with 
grouping the poles together). A quick search suggests that not many people 
have gone this route. So I'm hesitant to go there.

I think a general clean-up of the code will allow some more optimizations, 
especially when the singular vectors are also required.

Gael, thanks for your work on bidiagonalization. Hopefully we are getting 
close to lapack now.


Jitse