bjodah / finitediff

Finite difference weights for any derivative order on arbitrarily spaced grids. C89, C++ and Fortran 90 implementations with Python bindings.

finitediff

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

• C89
• Fortran 90
• C++

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)

Finitediff can be conditionally compiled to make finitediff_interpolate_by_finite_diff multithreaded (when FINITEDIFF_OPENMP is defined). Then the number of threads used is set through the environment variable FINITEDIFF_NUM_THREADS (or OMP_NUM_THREADS).

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

Simplest way to install is to use the conda package manager:

$ conda install -c conda-forge finitediff pytest
$ python -m pytest --pyargs finitediff

tests should pass.

Manual 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

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.

Citing

The algortihm is from the following paper:

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}
}

You may want to, in addition to the paper, cite finitediff (for e.g. reproducibility), and you can get per-version DOIs from the zenodo archive:

Licensing

The source code is Open Source and is released under the very permissive "simplified (2-clause) BSD license". See LICENSE for further details.

Author

Björn Ingvar Dahlgren (gmail address: bjodah). See file AUTHORS in root for a list of all authors.

finitediff's Issues

Apply along axis of array

Wonderful package, however, the interpolation module seems to only support 1D arrays.

Is it possible to structure inputs for interpolation such that it can be applied applied column-wise (or row-wise) along an axis of a 2D array? From what I've tried, the only solution I've found is looping the interpolation in Python over the rows or columns of a 2D, which nullifies the speed advantage of the Fortran/C++ implementation.

If it is not currently possible to directly input 2D arrays into the interpolation module, I would highly recommend adding this feature. This is a really special and useful package, and the addition of that feature could make it feasible to use this module in real-time or near real-time applications.

Thank you for all of your hard work on this package.

Compile under windows failed

Compilation ends up with following error:

build\temp.win-amd64-2.7\Release\.\finitediff\_finitediff_templated.o:_finitedif
f_templated.cpp:(.text+0x186d3): undefined reference to `__imp_get_interval_from
_guess'
collect2.exe: error: ld returned 1 exit status

Mingw-user maillist has a discussion about this http://mingw-users.1079350.n2.nabble.com/imp-prefixes-when-linking-td7386007.html. I am not familiar with Cython, how can I fix this error?