Expline v0.1.0 Expline.Spline

Expline.Spline is the module defining the struct and functions for constructing cubic splines and interpolating values along them. It is the core module and data structure for the library.

Mathematics

Expline uses information from the “Spline interpolation”, “Cholesky decomposition”, and “Triangular matrix” Wikipedia pages.

Spline interpolation requires the curvatures at the spline’s given points. To determine the curvatures, a system of linear equations needs to be solved.

There are a number of ways cubic splines can extrapolate values beyond their minimum and maximum. Currently, the only way Expline implements is “Natural Spline”. Others, such as “Clamped Spline” and “Not-A-Knot”, may be implemented depending on feedback from users.

For “Natural Splines”, a case of splines where the ends of the spline have no curvature, and are therefore can be linearly extrapolated, the matrix X in the system Xk = y (where the solution k is the vector of curvatures for the spline) is by definition Hermitian and positive-definite, a conclusion one can make by analyzing the equations and enforcing certain conditions by manipulating the input parameters. This allows us to generate the components necessary for solving for the curvatures in a more specialized fashion, and in the author’s experience, a fairly simple fashion.

Cholesky decomposition is a special type of Matrix decomposition that applies to Hermitian, positive-definite matrices. Its runtime is half of LU decomposition, another popular matrix decomposition.

With the Cholesky decomposition, the procedure described in the first paragraph of the “Applications” section of the “Cholesky decomposition” Wikipedia page is used to find the curvatures.

Performance

Given n points, the algorithm for building a spline is O(n^3) and interpolating a value is O(n).

Summary

Types

creation_error()

The errors that can arise from improper input to from_points/1

curvature()

The type used to denote the rate of change in the curvature of function at a given point

dependent_value()

The type used to denote a value that depends on another, whether it is by relation to an independent value in point/0 or returned by interpolate/2

extrapolation_method()

The method by which a spline’s end conditions are evaluated

independent_value()

The type used to denote a value that is independent and may be used to interpolate a dependent value from interpolate/2, reference a point, or determine the extrema of a spline or its ranges

interpolation_error()

The errors that can arise from improper input to interpolate/2

point()

The type used to initialize a spline and returned from Expline.interpolate/2 and Expline.interpolate/3

range()

The type used to denote the open range within which a point is interpolated

t()

The Expline’s internal representation of a cubic spline

Functions

from_points(list_of_points)

Create a spline from a list of floating point pairs (tuples)

interpolate(spline, x)

Interpolate a value from the spline

Types

creation_error()

creation_error ::
  :too_few_points |
  {:range_too_small, point, point}

The errors that can arise from improper input to from_points/1.

:too_few_points occurs when less than 3 points are used to create the spline. If this error occurs, providing more points should mitigate the issue. If you want to interpolate values between two points, Linear interpolation may be of more interest, but is not in the interest of this library.

{:range_too_small, point(), point()} occurs when the distance between the independent_value/0 in each of at least two points are too close for the virtual machine to determine a curvature between them. If this error occurs, increasing the resolution between the provided points or dropping points that are too close before input are both straightforward examples of mitigation strategies.

curvature()

curvature() :: float

The type used to denote the rate of change in the curvature of function at a given point.

dependent_value()

dependent_value() :: float

The type used to denote a value that depends on another, whether it is by relation to an independent value in point/0 or returned by interpolate/2.

extrapolation_method()

extrapolation_method() :: :natural_spline

The method by which a spline’s end conditions are evaluated.

This can have a significant effect on the runtime for the spline creation.

“Natural Spline”, denoted by the :natural_spline extrapolation method, uses a particular shape of system of linear equations be solved that is more performant to solce than a more general system. Currently, it is also the only extrapolation method implemented.

independent_value()

independent_value() :: float

The type used to denote a value that is independent and may be used to interpolate a dependent value from interpolate/2, reference a point, or determine the extrema of a spline or its ranges.

interpolation_error()

interpolation_error() :: :corrupt_extrema | :corrupt_spline

The errors that can arise from improper input to interpolate/2.

:corrupt_extrema occurs when the minimum/maximum is not greater/less than a point that does not fall into a range in the spline.

:corrupt_spline occurs when the spline’s internal information does not conform to various mathematical invariants.

For either of these values, a bug report may be needed, as in normal operation, neither should occur.

point()

point() :: {independent_value, dependent_value}

The type used to initialize a spline and returned from Expline.interpolate/2 and Expline.interpolate/3.

range()

range() :: {independent_value, independent_value}

The type used to denote the open range within which a point is interpolated.

t()

The Expline’s internal representation of a cubic spline

Functions

from_points(list_of_points)

from_points([point]) :: {:ok, t} | {:error, creation_error}

Create a spline from a list of floating point pairs (tuples).

This function bootstraps a spline and prepares it for use in the interpolate/2 function.

If fewer than 3 points are passed to the function, the function will short-circuit and return {:error, :too_few_points}. This is a mathematical constraint. A cubic spline cannot be built on fewer than 3 points.

Due to the constraints of Erlang and Elixir, there is a limit on how close points can be. If points are too close to each other, this leads to a situation where an error similar to dividing by zero occurs. In light of this, there is a check that occurs and short-circuits the construction of the spline. It returns {:error, {:range_too_small, p1, p2}} where p1 and p2 are two point/0s that are too close together. If this error is encountered, mitigating it is use-case specific. In order to find the points that are too close, the following snippet may prove useful:

points
|> Enum.group_by(fn ({x, y}) -> Float.round(x, 15) end)

Float.round/2 has a maximum precision of 15, and while floating point numbers appear to have higher precision, with representations with much higher points of precision, being able to reliably reconcile points is important.

If this is an issue, a smaller closeness threshold will be used, but until then, the threshold for determining points that are too close is 1.0e-15, the smallest value that can’t be rounded by Float.round/2.

Examples

# A point that is too close
iex> Expline.Spline.from_points([{0.0, 0.0}, {1.0, 1.0}, {5.0e-324, 0.0}])
{:error, {:range_too_small, {0.0, 0.0}, {5.0e-324, 0.0}}}

# Not enough points
iex> Expline.Spline.from_points([{0.0, 0.0}, {1.0, 1.0}])
{:error, :too_few_points}

# Well-spaced, enough points
iex> Expline.Spline.from_points([{0.0, 0.0}, {1.0, 1.0}, {2.0, 2.0}])
{:ok, %Expline.Spline{derivatives: %{0.0 => 0.9999999999999999,
                                     1.0 => 0.9999999999999999,
                                     2.0 => 1.0000000000000002},
                      extrapolation_method: :natural_spline,
                      max: 2.0, min: 0.0,
                      points: %{0.0 => 0.0, 1.0 => 1.0, 2.0 => 2.0},
                      ranges: [{0.0, 1.0}, {1.0, 2.0}]}}

interpolate(spline, x)

interpolate(t, independent_value) ::
  {:ok, dependent_value} |
  {:error, interpolation_error} |
  {:error, :corrupt_spline}

Interpolate a value from the spline.

In regular usage, when the function is given a float and a spline, it will return a tuple of {:ok, float} corresponding to the interpolated value of dependent variable from the given value of the independent variable and the spline.

If any of the invariants of the spline’s internal representation are not satisfied, then {:error, :corrupt_spline} will be returned. If this happens, please report it, as that would be a sign that there is an issue with the underlying data structures or algorithms used in the library.

Examples

iex> with {:ok, spline} <- Expline.Spline.from_points([{0.0, 0.0}, {1.0, 1.0}, {2.0, 2.0}]),
...> do: Expline.Spline.interpolate(spline, -0.5)
{:ok, -0.49999999999999994}

iex> with {:ok, spline} <- Expline.Spline.from_points([{0.0, 0.0}, {1.0, 1.0}, {2.0, 2.0}]),
...> do: Expline.Spline.interpolate(spline, 0.5)
{:ok, 0.5}

iex> with {:ok, spline} <- Expline.Spline.from_points([{0.0, 0.0}, {1.0, 1.0}, {2.0, 2.0}]),
...> do: Expline.Spline.interpolate(spline, 1.5)
{:ok, 1.5}

iex> with {:ok, spline} <- Expline.Spline.from_points([{0.0, 0.0}, {1.0, 1.0}, {2.0, 2.0}]),
...> do: Expline.Spline.interpolate(spline, 2.5)
{:ok, 2.5}