Hi all,
A few months ago, Gilles proposed to add an implementation of the
Ridder's algorithm for differentiation (see
<https://issues.apache.org/jira/browse/MATH-726>). After some discussion
the issue was postponed, waiting for an API for this family of algorithms.
Last week, at work, someone asked me again about differentiation and I
directed him to this issue and also to the Nabla project. He told me he
was interested in having some support in [math] for this (I'm not sure
he reads this list, but if he does, I hope he will join the discussion).
The basic needs are to get derivatives of either real-valued or vector
valued variables, either univariate or multivariate. Depending on the
dimensions we have derivatives, gradients, or Jacobians. In some cases,
the derivatives can be computed by exact methods (either because user
developed the code or using an automated tool like Nabla). In other
cases we have to rely on approximate algorithms (like Ridder's algorithm
with iterations or n-points finite differences).
Most of the times, when a derivative is evaluated, either the user needs
to evaluate the function too or the function is evaluated as a side
effect of the derivative computation. Numerous tools therefore packe the
value and the derivative in one object (sometimes called Rall numbers)
and transfor something like:
double f(double x) { ... }
into this:
RallNumber f(RallNumber x) { ... }
This is a very classical approach, very simple for languages that
implement operator overloading (see the book "Evaluating Derivatives" by
Andreas Griewank and Andrea Waltherpaper, SIAM 2008 or the paper "On the
Implementation of Automatic Differentiation Tools" by Christian H.
Bischof, Paul D. Hovland and Boyana Norris, unfortunately I was not able
to find a public version of this paper, or simply look at the wikipedia
entry <http://en.wikipedia.org/wiki/Algorithmic_differentiation> and the
presentation on automatic differentiation which seems to have been
written by one of the people who contributed to the wikipedia article
<http://www.docstoc.com/docs/29133537/Automatic-differentiation>).
Using this approach is simple to understand and compatible with all
differnetiation methods: direct user code for functions that are easily
differentiated, generated exact code produced by tools, finite
differences methods without any iteration and iterative methods like the
Ridder's method.
So I suggest we use this as our basic block. We already have an
implementation of RallNumbers in Nabla, where it is called
differentialPair
(<http://commons.apache.org/sandbox/nabla/apidocs/org/apache/commons/nabla/core/DifferentialPair.html>).
We can move this class into [math] and rename it RallNumbers.
For real valued univariate functions, we have the interface
UnivariateFunction
<http://commons.apache.org/math/apidocs/org/apache/commons/math3/analysis/UnivariateFunction.html>
that defines the single method
double value(double x)
This interface is used in many places, it is simple and it is well
defined, so it should be kept as is.
We also have a DifferentiableUnivariateFunction, which returns a
separate UnivariateFunction for the derivative:
UnivariateFunction derivative();
This interface is used only in the interface
AbstractDifferentiableUnivariateSolver and in its single implementation
NewtonSolver. This interface seems awkward to me and costly as it forces
to evaluate separately the function even when evaluating the derivative
implies computing the function a few times. For very computing intensive
functions, this is a major problem.
I suggest we deprecate this interface and add a new one defining method:
RallNumber value(RallNumber x)
This interface could extend UnivariateFunction in which case when we
want to compute only the value we use the same object, or it could also
define a getPrimitive method the would return a separate primitive
object (this is how it is done in Nabla, with the interface
UnivariateDerivative
(<http://commons.apache.org/sandbox/nabla/apidocs/org/apache/commons/nabla/core/UnivariateDerivative.html>),
or it can even be completely separate from UnivariateFunction.
Multivariate differentiable functions or vector valued functions would
be done exactly the same way: replacing the parameter or return value
types from double arrays to RallNumber arrays. This would be much more
consistent than what we currently have (we have methods called
partialDerivatives, gradients, jacobians and even several methods called
derivative which do not have the same signatures).
For functions that can be differentiated directly at development time,
this layer would be sufficient. We can typically us it for all the
function objects we provide (Sin Exp ...) as well as the operators
(Multiply, subtract ...).
For more complex functions, we need to add another layer that would take
a simple function (say a UnivariateFunction for the real value
univariate case) and would create the differentiated version. For this,
I suggest to create a Differentiator interface (similar in spirit to
Nable UnivariateDiffernetiator
<http://commons.apache.org/sandbox/nabla/apidocs/org/apache/commons/nabla/core/UnivariateDifferentiator.html>).
We should probably build a set of interfaces in the same spirit as the
solvers interfaces. This interface would be implemented by engines that
can compute derivatives. In most cases, these engines would simply
return a wrapper around the function they get as parameters. The wrapper
would implement the appropriate derivative interface. When the wrapper
"value" method would be called, the underlying raw univariate "value"
method would be called a number of time to compute the derivative.
We could provide several implementations of these interfaces. For
univariate real functions, we should at least provide the finite
differences methods in 2, 4, 6 and 8 points (we already have them in
Nabla), and we should also provide the Ridder's algorithm. Users or
upper level libraries and applications could provide other
implementations as well. In fact, Nabla would be such a case and would
provide an algorithmic implementaion and would depend on [math].
We could also provide implementations for the upper dimensions
(multivariate or vector valued) using simply the univariate
implementations underneath (typically computing a gradient involves
computing n derivatives for the n parameters of the same function,
considering each time a different parameter as the free variable). Here
again, more efficient implementations could be added for specific cases
by users.
The separation between the low level layer (derivatives definition) and
the upper layer (transforming a function that do not compute derivatives
into a function taht compute derivatives) is a major point. The guy who
talked to me last week insisted about this, as he wanted to avoid
approximate (and computation-intensive) algorithms when he can, and he
wanted to have these algorithms (like Ridder) available when he cannot
do without them. So the focus is not to have Ridder by itself, but
rather to compute derivatives, using Ridder or something else.
Of course, I can provide all the raw interfaces and finite differences
implementations. If someone provides me the paper for Ridder's method, I
can also implement this (or if someone wants to do it once the interface
have been set up, it is OK too).
What do you think about this ?
Luc
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
