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-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
