accurate sums and products for Python

## Project Description

Accurate sums and (dot) products for Python.

## Sums

Summing up values in a list can get tricky if the values are floating point numbers; digit cancellation can occur and the result may come out wrong. A classical example is the sum

1.0e16 + 1.0 - 1.0e16

The actual result is `1.0`, but in double precision, this will result
in `0.0`. While in this example the failure is quite obvious, it can
get a lot more tricky than that. accupy provides

p, exact, cond = accupy.generate_ill_conditioned_sum(100, 1.0e20)

which given a length and a target condition number will produce an array if floating point numbers that’s hard to sum up.

accupy has the following methods for summation:

`accupy.kahan_sum(p)`: Kahan summation`accupy.fsum(p)`: A vectorization wrapper around math.fsum (which uses Shewchuck’s algorithm [1] (see also here)).`accupy.ksum(p, K=2)`: Summation in K-fold precision (from [2])

All summation methods sum the first dimension of a multidimensional NumPy array.

Let’s compare them.

### Accuracy comparison (sum)

As expected, the naive
sum performs
very badly with ill-conditioned sums; likewise for
``numpy.sum` <https://docs.scipy.org/doc/numpy/reference/generated/numpy.sum.html>`__
which uses pairwise summation. Kahan summation not significantly better;
this, too, is
expected.

Computing the sum with 2-fold accuracy in `accupy.ksum` gives the
correct result if the condition is at most in the range of machine
precision; further increasing `K` helps with worse conditions.

Shewchuck’s algorithm in `math.fsum` always gives the correct result
to full floating point precision.

### Speed comparison (sum)

We compare more and more sums of fixed size (above) and larger and
larger sums, but a fixed number of them (below). In both cases, the
least accurate method is the fastest (`numpy.sum`), and the most
accurate the slowest (`accupy.fsum`).

## Dot products

accupy has the following methods for dot products:

`accupy.fdot(p)`: A transformation of the dot product of length*n*into a sum of length*2n*, computed with math.fsum`accupy.kdot(p, K=2)`: Dot product in K-fold precision (from [2])

Let’s compare them.

### Accuracy comparison (dot)

accupy can construct ill-conditioned dot products with

x, y, exact, cond = accupy.generate_ill_conditioned_dot_product(100, 1.0e20)

With this, the accuracy of the different methods is compared.

As for sums, `numpy.dot` is the least accurate, followed by instanced
of `kdot`. `fdot` is provably accurate up into the last digit

### Speed comparison (dot)

NumPy’s `numpy.dot` is *much* faster than all alternatives provided by
accupy. This is because the bookkeeping of truncation errors takes more
steps, but mostly because of NumPy’s highly optimized dot
implementation.

## References

## Dependencies

accupy needs the C++ Eigen
library,
provided in Debian/Ubuntu by
``libeigen3-dev` <https://packages.ubuntu.com/search?keywords=libeigen3-dev>`__.

## Installation

accupy is available from the Python Package Index, so with

pip install -U accupy

you can install/upgrade.

## Testing

To run the tests, just check out this repository and type

MPLBACKEND=Agg pytest

## Distribution

To create a new release

bump the

`__version__`number,publish to PyPi and GitHub:

$ make publish

## License

accupy is published under the MIT license.

## Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, Size & Hash SHA256 Hash Help | File Type | Python Version | Upload Date |
---|---|---|---|

accupy-0.1.1.tar.gz
(10.3 kB) Copy SHA256 Hash SHA256 |
Source | None | Mar 2, 2018 |