Re: [eigen] Levenberg-marquardt and dogleg minimizer |

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

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] Levenberg-marquardt and dogleg minimizer*From*: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>*Date*: Fri, 27 Feb 2009 17:32:22 +0100*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type; bh=nbf6LjJUa1rxI3Ep9Ac3AlchkEh1lxaYxBBLOnG/nkY=; b=GVnGWO45mHkyP+H1iAtKOzYlr23dsG+l5OMyAgWx2/f41z+Xh6CZO66UMMgK7KJhsa 0atbrjjiCFJD/7kx3UZO43Q402aUXDGNDa0kbw1/dKiYeErSWfgJkxbzkdt2zRhWBeM1 wjysC0a/Y32Is5a+qnJ23H2ljJX7PdexwQPI8=*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=ZE1XqYowdAKTf8AhW87ANMqhf0hRYz/qas0f7kr6/L+a+aV+ETKuZ075VeBx4cQ7DR Qlg9YSromrfslCrnJDUi8Kdoeg4jpprWsaM7fxWZWok9foAnu4/U4ww6b86xjYz/sLRB G1yA11NrxxfbDlEhGU5bTFZejckCavzFopRrs=

FYI, I just added a proof of concept helper class to compute the Jacobian using adolc:

http://websvn.kde.org/trunk/kdesupport/eigen2/unsupported/Eigen/AdolcForward?view=markup

and the test/example:

http://websvn.kde.org/trunk/kdesupport/eigen2/unsupported/test/forward_adolc.cpp?revision=932957&view=markup

from this very simple piece of code all variants can be imagined.

However there are severe limitations:

1 - the max number of "directions" must be set at compile time using a #define (this is an adolc limitation)

2 - all the functions which are called from your function must either be templated on the scalar type or have an explicit overload for the adolc's adouble type (this is already the case for most mathematical functions)

Note that the current support is for adolc's tapeless forward mode. Adolc also has a tape-based mode which offers many more features (e.g., sparsity analysis) and does not suffer from the 1st stupid limitation (on the other hand, perf and memory accesses are usually much worse)

cheers,

gael.

On Thu, Feb 26, 2009 at 1:36 PM, Gael Guennebaud <gael.guennebaud@xxxxxxxxx> wrote:

On Thu, Feb 26, 2009 at 1:13 PM, Jos van den Oever <jvdoever@xxxxxxxxx> wrote:2009/2/26 Gael Guennebaud <gael.guennebaud@xxxxxxxxx>:

> adolc internally uses dense vector to store each derivatives, so itReduced storage in the Jacobian is not the main benefit I'm aiming for.

> cannot deal with large - sparse problem. What would be nice is to

> implement our own autodiff tool based on eigen's dense and sparse

> objects but that happens only if someone interested in doing that

> shows up...

The solver uses a dense Jacobian storage wise, but can do faster

iteration steps if it knows which parts of the Jacobian are zero or

linear.

You are right that using a sparse matrix would probably improve

performance more.

yes, in mind the goal is to be able to instantiate Lev-Marq with sparse-matrices, then the conversion from adolc derivatives to the jacobian will generate a real sparse Jacobian... Note that I think the memory overhead needed by adolc might prevent its use for relatevly large problems.

If I understand the autodiff Jacobian correctly, the derivative

functions are calculated at compile time. So would it be possible to

find out which part of it are zero or linear?

yes, in forward mode the derivative are more or less computed at compile time using operator overloading, but this is not enough to be able to determine the zeros at compile-time. Likewise, you cannot determine linear parts at compile time, but, at runtime, I think this would be easy to flag the coefficients which are not linear (adolc does not provide that, but this is theoratically possible to add that).

Cheers,

Jos

**References**:**[eigen] Levenberg-marquardt and dogleg minimizer***From:*Keir Mierle

**Re: [eigen] Levenberg-marquardt and dogleg minimizer***From:*Keir Mierle

**Re: [eigen] Levenberg-marquardt and dogleg minimizer***From:*Gael Guennebaud

**Re: [eigen] Levenberg-marquardt and dogleg minimizer***From:*tjhunter

**Re: [eigen] Levenberg-marquardt and dogleg minimizer***From:*Gael Guennebaud

**Re: [eigen] Levenberg-marquardt and dogleg minimizer***From:*Jos van den Oever

**Re: [eigen] Levenberg-marquardt and dogleg minimizer***From:*Gael Guennebaud

**Re: [eigen] Levenberg-marquardt and dogleg minimizer***From:*Jos van den Oever

**Re: [eigen] Levenberg-marquardt and dogleg minimizer***From:*Gael Guennebaud

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] Eigen rocks** - Next by Date:
**Re: [eigen] Eigen rocks** - Previous by thread:
**Re: [eigen] Levenberg-marquardt and dogleg minimizer** - Next by thread:
**[eigen] Reshape function**

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