[math] New finite differencing framework for math4

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

Hello all,

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

Re: [math] New finite differencing framework for math4

[Eric Barnhill <er...@gmail.com>]

Dear Fran, this is very interesting especially the bandwidth control 
which I would find useful. I will be happy to look this code over and 
test it on some problems in my field. Right now that will be in a month 
or two due to some personal issues.

I added a couple of questions to the JIRA.

Best,
Eric

On 17/02/16 03:41, Fran Lattanzio wrote:
> Hello all,
>
> 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
>


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