Re: [eigen] Divide & conquer SVD algorithm

[Jitse Niesen <jitseniesen@xxxxxxxxx>]

On Tue, 27 May 2014, Tristan Sahel wrote:

> First, we would need to get used to the code and the specific array 
> functionalities, so we thought we would try and develop the "shift" or 
> "rotate" functions of the Array Module. We saw that the todo list was not 
> up-to-date though, so we would require your confirmation that the job is 
> still needed before getting down to it. We are hoping that the implementation 
> of these functions will not be too hard or long.

These functions have not been implemented yet. You should however read 
yesterdag's message by Wenzel Jakob on this mailing list. My reply might 
also be useful.

> Then, we are planning to continue the work of our fellow students of the 
> Ensimag from last year, who were trying to improve the SVD by developping a 
> divide & conquer algorithm. Their work was very promising and their algorithm 
> was slightly faster than the Jocobi SVD algorithm. However, they did not have 
> time to finish the implementation of their divide & conquer: they were 
> missing one step, the last one, which they explained step by step in their 
> todoBDcsvd.txt document. If we manage to finish the job, the calculation time 
> should become o(n^2).

I hate to scupper your plan, but this is already done. At the moment we 
have a complete but basic implementation of the divide and conquer 
algorithm in the experimental section. It does need some improvements 
(there seems to be at least one bug and several inefficiencies).

I do not know exactly what is required for your project, but here are some 
ideas along similar lines. What I would consider the standard algorithm 
for the SVD based on Golub and Kahan using bi-diagonalization is not 
implemented in Eigen (we did have an implementation in the past but we 
removed it as we were not happy with it), so you could do that. You could 
also try implementing a divide-and-conquer algorithm for computing 
eigenvalues. Another idea is to implement an method for the polar 
decomposition.

All the best,
Jitse