finitediff

Finite difference weights for any derivative order on arbitrarily spaced grids.

Project description

finitediff

finitediff containts three implementations of Begnt Fornberg’s formulae for generation of finite difference weights on aribtrarily spaced one dimensional grids:

The finite difference weights can be used for optimized inter-/extrapolation data series for up to arbitrary derivative order. Python bindings (to the C versions) are also provided.

Capabilities

finitediff currently provides callbacks for estimation of derivatives or interpolation either at a single point or over an array (available from the Python bindings).

The user may also manually generate the corresponding weights. (see calculate_weights)

Documentation

Autogenerated API documentation for latest stable release is found here: https://bjodah.github.io/finitediff/latest (and the development version for the current master branch is found here: http://hera.physchem.kth.se/~finitediff/branches/master/html).

Examples

Generating finite difference weights is simple using C++11:

#include "finitediff_templated.hpp"
#include <vector>
#include <string>
#include <iostream>

int main(){
    const unsigned max_deriv = 2;
    std::vector<std::string> labels {"0th derivative", "1st derivative", "2nd derivative"};
    std::vector<double> x {0, 1, -1, 2, -2};  // Fourth order of accuracy
    auto coeffs = finitediff::generate_weights(x, max_deriv);
    for (unsigned deriv_i = 0; deriv_i <= max_deriv; deriv_i++){
        std::cout << labels[deriv_i] << ": ";
        for (unsigned idx = 0; idx < x.size(); idx++){
            std::cout << coeffs[deriv_i*x.size() + idx] << " ";
        }
        std::cout << std::endl;
    }
}

$ cd examples/
$ g++ -std=c++11 demo.cpp -I../include
$ ./a.out
Zeroth derivative (interpolation): 1 -0 0 0 -0
First derivative: -0 0.666667 -0.666667 -0.0833333 0.0833333
Second derivative: -2.5 1.33333 1.33333 -0.0833333 -0.0833333

and of course using the python bindings:

>>> from finitediff import get_weights
>>> import numpy as np
>>> c = get_weights(np.array([0, -1., 1]), 0, maxorder=1)
>>> np.allclose(c[:, 1], [0, -.5, .5])
True

from Python you can also use the finite differences to interpolate values (or derivatives thereof):

>>> from finitediff import interpolate_by_finite_diff as ifd
>>> x = np.array([0, 1, 2])
>>> y = np.array([[2, 3, 5], [3, 4, 7], [7, 8, 9], [3, 4, 6]])
>>> xout = np.linspace(0.5, 1.5, 5)
>>> r = ifd(x, y, xout, maxorder=2)
>>> r.shape
(5, 4, 3)

see the examples/ directory for more examples.

Installation

You can install finitediff by using pip:

$ python -m pip install --user finitediff

(you can skip the --user flag if you have got root permissions), to run the tests you need pytest too:

$ python -m pip install --user --upgrade pytest
$ python -m pytest --pyargs finitediff

alternatively (on Linux) you may also use conda package manager:

$ conda install -c bjodah finitediff pytest

Dependencies

You need either a C, C++ or a Fortran 90 compiler. On debian based linux systems you may install (all) by issuing:

$ sudo apt-get install gfortran g++ gcc

See setup.py for optional (Python) dependencies.

Notes

There is a git subtree under finitediff, update through:

git subtree pull --prefix finitediff/external/newton_interval newton_interval master --squash

where the repo “newton_interval” is https://github.com/bjodah/newton_interval.git

First time you need to add it:

git subtree add --prefix finitediff/external/newton_interval git://github.com/bjodah/newton_interval master

References

The algortihm is a rewrite of:

http://dx.doi.org/10.1137/S0036144596322507

@article{fornberg_classroom_1998,
  title={Classroom note: Calculation of weights in finite difference formulas},
  author={Fornberg, Bengt},
  journal={SIAM review},
  volume={40},
  number={3},
  pages={685--691},
  year={1998},
  publisher={SIAM}
  doi={10.1137/S0036144596322507}
}

Which is based on an article of the same author:

http://dx.doi.org/10.1090/S0025-5718-1988-0935077-0

@article{fornberg_generation_1988,
  title={Generation of finite difference formulas on arbitrarily spaced grids},
  author={Fornberg, Bengt},
  journal={Mathematics of computation},
  volume={51},
  number={184},
  pages={699--706},
  year={1988}
  doi={10.1090/S0025-5718-1988-0935077-0}
}