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: [hidden email] For additional commands, e-mail: [hidden email] |
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: [hidden email] > For additional commands, e-mail: [hidden email] > --------------------------------------------------------------------- To unsubscribe, e-mail: [hidden email] For additional commands, e-mail: [hidden email] |
Free forum by Nabble | Edit this page |