[math] New finite differencing framework

[Fran Lattanzio <sy...@gmail.com>]

Hello all,

(I tried to send this yesterday, but it looks like my message bounced,
as I received some weird errors; apologies if you are receiving a
duplicate of this message.)

I have created a pull request with a new univariate finite difference
framework for [math]. The main features of this framework are:
1. *Exact* calculation of the coefficients for any stencil type
(forward, backward, central), derivative order, and accuracy order.
This is done by solving the system of linear equations generated by
repeated Taylor expansion, using the field LU decomp over
BigFractions. This is actually an important feature because it ensures
there is no roundoff error in the coefficients; and we can tell if a
coefficient is *exactly* zero.
2. Separation of derivative calculation and bandwidth selection -
specifically, there is a strategy interface that decides the
bandwidth, based on point at which the derivative is desired (and the
nature of the stencil, etc).
3. Several canned bandwidth strategies:
 a. A fixed bandwidth.
 b. A "rule-of-thumb" strategy (which covers far more general cases
than the rule-of-thumb suggested in a certain numerical cookbook).
 c. An adaptive strategy that estimates the error scale of the finite
difference function in order to determine the optimal bandwidth. This
is done using a technique akin to Richardson extrapolation.
 d. A decorator strategy to round bandwidths to a power-of-two. (Using
powers-of-two bandwidths is good because they have exact IEEE floating
point representations, so x +/- h will be correct to full precision.)

Strategies b. and c. can also accept a function condition error
parameter. This is quite important if you know that the underlying
function is not computed to full machine precision, e.g. the function
is an approximation accurate to 1e-10; or done over the IEEE 32s
rather than 64s.

Bandwidth strategy c. is derived from a thesis published by Ravi
Mathur. Mathur provides formulae that shows how to find the optimal
bandwidth - optimal in the sense that it will minimize the total error
(which is a delicate balancing act!). His thesis can be found here:
https://repositories.lib.utexas.edu/bitstream/handle/2152/ETD-UT-2012-05-5275/MATHUR-DISSERTATION.pdf?sequence=1

(This is the first implementation of Mathur's ideas that I have seen.
Most of his work is thorough, so although this implementation is "new"
 and thus not considered an industry standard, I think it is
definitely worth including. Some initial numerical experiments confirm
as much.)

These strategies should cover the vast majority of use cases, and of
course the strategy interface allows users to implement anything
bespoke if the need arises.

I am working on generating more unit tests now. For now, there are
only relatively simple tests for the coefficient generation and
"integration tests" that compare analytical vs. numerical derivatives.
If this is something that the community wants to include in math4, I
will be happy to fully flesh them out.

I am also working on a multivariate version. Generating the
coefficients is easy... the tricky part for the multivariate case is
the bandwidth strategies. The fixed bandwidth strategy is obviously
trivial. I am trying to expand Mathur's work to the multivariate case
to derive analogous rule-of-thumb and adaptive strategies but the
equations are bit ticklish in the multivariate world.

In any case, the JIRA ticket and pull request are here:
https://issues.apache.org/jira/browse/MATH-1325
https://github.com/apache/commons-math/pull/24

Any suggestions are welcome,
Fran.

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