commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <Luc.Maison...@free.fr>
Subject Re: [nabla] Applications
Date Sun, 09 Oct 2011 19:07:43 GMT
Le 09/10/2011 19:24, Phil Steitz a écrit :
> On 10/9/11 9:53 AM, Luc Maisonobe wrote:
>> Le 09/10/2011 16:51, Phil Steitz a écrit :
>>> For the acon US talk I am giving, I would like to provide some
>>> potential practical examples of how [nabla] might be used in
>>> applications.  So far, I have come up with some direct uses of
>>> analytic derivatives in things like splines and projections.  I
>>> suspect there are quite a few numerical or optimization use cases
>>> where having an exact derivative could improve speed or accuracy.  I
>>> would like to refer to some of those.  Its OK if the needed
>>> machinery does not exist yet in [nabla] - these are motivational
>>> examples.
>>
>> Here are the original example that lead me to start everything.
>>
>> One of the classical process used in operational space flight
>> dynamics is orbit determination. Spacecraft orbits are not
>> perfectly known due to launcher errors, maneuvers errors and
>> measurements errors. Error grows from these initial errors due to
>> the dynamics of the trajectory, so after some time it becomes
>> necessary to perform some measurements (distances, angles, Doppler
>> from some refence points like known ground stations). Then we try
>> to compute the orbit that fits the best these measurements, taking
>> into account many perturbing effects. This is basically least
>> squares or Kalman filtering, where we adjust some state vector
>> that evolves in time, using observation points and evolution
>> models. We need Jacobians matrices in this process, the Jacobians
>> associated with measurement at time ti with respect to initial
>> orbit state at time t0 or with respect to some model parameters
>> like atmospheric drag coefficients or thrusters efficiency. These
>> models are very complex. They are split in many classes, many
>> methods, many iterations so even if from a very high level we have
>> for measurement m a function like m(ti) = f(o(t0), t0, ti), the f
>> function is in fact several thousands lines of code from three
>> different libraries.
>>
>> Up to now, we had to compute the Jacobians by manual coding of the
>> exact formulas. This is a maintenance nigthmare. As we try to use
>> more and more complex force models for spacecraft dynamics, we
>> have to compute their differentials too. It would be nice if we
>> could just focus on the perturbation forces only and have some
>> automatic engine that would perform the heavy duty differentiation
>> for us. There is really no added value in the derivatives from a
>> science or engineering point of view, so it is a perfect target
>> for automation, so we concentrate the human efforts on something
>> else: the perturbation forces by themselves.
>
> Thanks, this is a great example.  Why exactly is numeric
> differentiation not viable here?  I assume it must have something to
> do with either the setup being almost as hard as just coding the
> analytic differentials or error.

There are several reasons.

The first reason is it is costly: in order to have accurate derivatives, 
you have to compute f(xi+hi) and f(xi-hi) in addition to f(xi) for each 
column i of the Jacobian, so with a 6 parameters orbit you have 1 + 2 * 
6 = 13 times more calls. It is even worse when you want the derivatives 
about other non-state parameters (like force models and so on). 
Analytical derivatives and algorithmic differentiation increase cost by 
a factor 2 or 3, regardless of the number of columns (in algorithmic 
differentiation, this is sometimes called the "cheap gradient" 
principle, it is true only using reverse mode which is not yet 
implemented in Nabla).

The second reason is it is difficult to select appropriate steps, as 
state vectors sensitivity is quite different from component to component 
and also depends on the time (with elliptical orbits, sensitivity near 
perigee is different from sensitivity near apogee, so the step size 
should change).

The third reason is that some parameters are bounded and useful values 
are sometimes close to the boundaries, so you may hit some problems if 
you shift one parameters too far. As a (simplified) example, 
eccentricity is between 0 and 1 and circular orbits have almost 0 
eccentricity, so you must be careful not setting eccentricity to a 
negative value.

>>
>> This example (optimization and least squares) can also be reduced
>> to one dimension only, so derivatives would also be useful in root
>> solvers (but in fact, I know think solvers like the extended Nth
>> order Brent I implemented are in fact more efficient than Newton
>> despite they don't use derivatives).
>
> Right.  I considered exactly the same example and came to exactly
> the same conclusion :)
>>
>> Another example is sensitivity and error analysis. Having the
>> derivatives almost for free (in engineering costs, not in
>> computation costs) is a major advantage. Jacobians link an initial
>> error to a final error and hene can be used to convert covariance
>> matrices. They can also be used to set up convergence criterions
>> in iterative processes or margins for robustness analysis.
>
> Here again, the key I guess is the reduced engineering cost over
> numerical differentiation or direct analytics.  The simple example I
> was thinking about was computing the slope of an interpolating
> function, e.g. a cubic spline.  Our own SplineInterpolator will
> provide the Polynomials, which give you the analytical derivatives;
> but to roll your own derivative for the whole function,  you have to
> write code to locate the right knot points, pick out the
> interpolating polynomial, etc.  Having [nabla] do what will amount
> to *the same thing* automatically saves engineering time.  An
> interesting question for us in [math] is how we would feel about
> eventually using [nabla] internally for exactly this kind of thing.

Well, Nabla has two drawbacks that in my opinion are destructive with 
respect to an inclusion in [math]: it is a really huge codebase for one 
specific purpose that not anyone needs, and it brings a dependency to asm.

However, what could be really interesting is moving the "core" package 
into [math], along with the simple finite differences based 
implementation for package "numerical". There was a discussion on the 
list some months ago about setting up a differentiation framework. Then, 
the algorithmic implementation from Nabla would be an external add-on 
that provides another implementation of the differentiation engine, for 
users who really need it and accept the burden of the large code base 
and the dependencies.

> Providing a derivative for the function returned by the
> SplineInterpolator (or even more basically, replacing what we have
> now in Polynomial) is an example.

Yes, but Nabla is perhaps to heavyweight for that.

Luc

>
> Phil
>>
>>
>> Hope this helps
>> Luc
>>
>>>
>>> Thanks!
>>>
>>> Phil
>>>
>>> ---------------------------------------------------------------------
>>>
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message