Re: [eigen] Status of givens QR decomposition |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] Status of givens QR decomposition*From*: Adolfo Rodríguez Tsouroukdissian <dofo79@xxxxxxxxx>*Date*: Tue, 27 Apr 2010 11:45:37 +0200*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:content-type; bh=QC76fMJ9ItvQtPzRhUYYzBXxXoRivZCskwuKj3n93hs=; b=FTHf+oKhX5byOPQzFKm6OUo/+ZsKVxRLJgfN1MPRHWIOnP+JwusgE0eGFpFZXyQQNC qvF1lCdLB8qy+m3yLvlliP5AVGA6nAE+swXjfUw/I3IizYl1U3pFLI8/edEjXhgUAZl1 6KHqz7s7bIVz7zZxfy4EM6bMc/HbvYc00BsUg=*Domainkey-signature*: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; b=iew3VItl7BfCwNEg8hIKkE160T6hrDcvNwdDTYFrbJpjKYoettQiSfgJJG9qfBkDWj qaa9bVOLpHVZpAXXnVYe98aiTNkktm5QF6+yX7Xj3fonh1P1JGsyVDBOxGOzIGhuXKO1 QKypaHC2OZYcdrqJMv3eDicbqSbFiY3Z4eAXg=

On Tue, Jan 26, 2010 at 1:52 PM, Benoit Jacob <jacob.benoit.1@xxxxxxxxx> wrote:

Let's revive this thread a little bit :)

I'm curious to have a general idea of the solution method you want to implement here (SVD based on Givens rotations, storing only N rotations/sweep). Is there a paper that you could refer me to?. One sweet thing of using Givens rotations (as opposed to say Householder reflections) is that their computation can be easily parallelized across multiple cores.

On a separate note, I'd like to ask if there would be interest in having a SVD implementation tailored for the case of using one decomposition instance to solve multiple "similar" problems. By similar I'm referring to solve initially for matrix A, and then for a perturbed matrix A + deltaA, and so on. In such cases, results from previous computations can greatly increase performance. The KDL developers [1] brought to my attention a paper that details this solution strategy (also based on Givens rotations), which can be found here [2]. They have also a working implementation [3] that uses eigen matrices, but its internals are not "eigenized".

Finally, I wanted to ask the more general question of what SVD implementations will likely make it to 3.0.

TIA,

Adolfo

[1] http://orocos.org/kdl

[2] http://www.engr.colostate.edu/~aam/pdf/journals/5.pdf

[3] http://svn.mech.kuleuven.be/websvn/orocos/trunk/kdl/src/utilities/svd_eigen_Macie.hpp

2010/1/26 Thomas Capricelli <orzel@xxxxxxxxxxxxxxx>:

>Interesting!!

> As a following to:

> http://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2009/09/msg00009.html

>

> I'd like to say that i have a very important use case for givens-QR with big matrices in the NonlinearOptimization module. This is useful in the variant of the Levenberg Marquardt algorithm for very big matrices, so-called 'storage efficient': the qr decomposition is done with givens rotation, presumably because this is the only decomposition that can be done incrementally : the matrix to decompose is not known as a whole, but is constructed line by line, 'updating' the qr decomposition and deleting the line.

I haven't touched it in a long time. The original use case was small

>

> Andrea, Benoit, what is the status of this fork ? As I have write permission, I've merged with mainline once or twice, but the fork seems abandoned... was there a use case ? not anymore ?

matrices, where it is faster than householder. Now you mention large

matrices that are not fully known in advance: interesting.

Finally, about the old debate about whether to store the list of

givens permutations, let me mention that in the different setting of

SVD, I have now decide to try this approach too. It's different as I'm

only storing N Givens rotations per sweep, as opposed to N^2/2 in

GivensQR, but perhaps still worth mentioning.

Let's revive this thread a little bit :)

I'm curious to have a general idea of the solution method you want to implement here (SVD based on Givens rotations, storing only N rotations/sweep). Is there a paper that you could refer me to?. One sweet thing of using Givens rotations (as opposed to say Householder reflections) is that their computation can be easily parallelized across multiple cores.

On a separate note, I'd like to ask if there would be interest in having a SVD implementation tailored for the case of using one decomposition instance to solve multiple "similar" problems. By similar I'm referring to solve initially for matrix A, and then for a perturbed matrix A + deltaA, and so on. In such cases, results from previous computations can greatly increase performance. The KDL developers [1] brought to my attention a paper that details this solution strategy (also based on Givens rotations), which can be found here [2]. They have also a working implementation [3] that uses eigen matrices, but its internals are not "eigenized".

Finally, I wanted to ask the more general question of what SVD implementations will likely make it to 3.0.

TIA,

Adolfo

[1] http://orocos.org/kdl

[2] http://www.engr.colostate.edu/~aam/pdf/journals/5.pdf

[3] http://svn.mech.kuleuven.be/websvn/orocos/trunk/kdl/src/utilities/svd_eigen_Macie.hpp

It is for sure needed at least by everyone needing QR decomposition of

> btw, Am I the only one needing givens QR decompozition on the list ? anyone ?

very small matrices.

If you need to make intrusive changes in Andrea's fork, perhaps it's

easiest for you to fork it, you can then re-merge with Andrea if he

expresses agreement with your changes. I personally don't have time

right now to think about that... :(

Benoit

--

Adolfo Rodríguez Tsouroukdissian, Ph. D.

Robotics engineer

PAL ROBOTICS S.L

http://www.pal-robotics.com

Tel. +34.93.414.53.47

Fax.+34.93.209.11.09

AVISO DE CONFIDENCIALIDAD: Este mensaje y sus documentos adjuntos, pueden contener información privilegiada y/o confidencial que está dirigida exclusivamente a su destinatario. Si usted recibe este mensaje y no es el destinatario indicado, o el empleado encargado de su entrega a dicha persona, por favor, notifíquelo inmediatamente y remita el mensaje original a la dirección de correo electrónico indicada. Cualquier copia, uso o distribución no autorizados de esta comunicación queda estrictamente prohibida.

CONFIDENTIALITY NOTICE: This e-mail and the accompanying document(s) may contain confidential information which is privileged and intended only for the individual or entity to whom they are addressed. If you are not the intended recipient, you are hereby notified that any disclosure, copying, distribution or use of this e-mail and/or accompanying document(s) is strictly prohibited. If you have received this e-mail in error, please immediately notify the sender at the above e-mail address.

**Follow-Ups**:**Re: [eigen] Status of givens QR decomposition***From:*Benoit Jacob

**Messages sorted by:**[ date | thread ]- Prev by Date:
**RE: [eigen] SelfAjointView::ldlt()** - Next by Date:
**Re: [eigen] Status of givens QR decomposition** - Previous by thread:
**RE: [eigen] SelfAjointView::ldlt()** - Next by thread:
**Re: [eigen] Status of givens QR decomposition**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |