|Re: [eigen] BDCSVD update|
[ Thread Index |
| More lists.tuxfamily.org/eigen 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  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
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.