Re: [eigen] BDCSVD update

[ Thread Index | Date Index | More Archives ]

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.


Mail converted by MHonArc 2.6.19+