fast_interpolation_​matlab

version 1.2 (104 KB) by
MATLAB Code for Fast Linear Interpolation

Updated 12 May 2022

From GitHub

MATLAB Code for Fast Linear Interpolation

The MATLAB code offers fast 1D linear interpolation methods.

The following fast interpolation methods is implemented:

• Linear interpolation inside the domain, linear extrapolation outside.
• Support vector or matrix (set of 1D values) for the sample values.
• Support for evenly spaced sample points: `interp_regular`.
• Support for evenly arbitrarily spaced sample points: `interp_fast`.
• These algorithms can be up to 30x faster than the MATLAB builtin interpolation methods.

The following algorithm is used for `interp_regular`:

• The sample points are evenly spaced.
• The position (index) of the query points can be computed without searching.
• Hence, the complexity is O(1).

The following algorithm is used for `interp_fast`:

• The sample points are arbitrarily spaced.
• After each query, the position (index) of the point is returned.
• This index is used as an initial value for the next query point.
• Hence, the computational cost is reduced if the query points are partially sorted.
• For randomly distributed query points, the complexity is O(n).
• For sorted query points, the complexity is reduced from O(n) to O(1).

These methods should be used in the following case:

• Many calls are done with the same sample points and values.
• The calls cannot be vectorized (interdepency between the query points).
• A typical use case is ODE integration where the calls cannot be vectorized.

These functions can be compiled to MEX files with the MATLAB Coder.

Functions

• interp_regular.m - Fast interpolation method (evenly spaced sample points).
• interp_fast.m - Fast interpolation method (arbitrarily spaced sample points).

Benchmark

The following sample points and values are considered (1000 points):

``````% sample points (sorted)
x_vec = linspace(0, 1, 1000);

% sample values (3 rows)
y_mat = [-1+x_vec+x_vec.^2 ; +1+x_vec-x_vec.^2; +2-x_vec-x_vec.^2];
``````

The following query points (sorted and random) are considered (12500 points):

``````% query point, mostly sorted
x_vec_pts_sort = [...
linspace(-1.0, +2.0, 2500)...
linspace(+2.0, -0.5, 2500)...
linspace(-0.5, +0.5, 2500)...
linspace(+0.5, -1.0, 2500)...
linspace(-1.0, +2.0, 2500)...
];

% randomly sorted query points
idx = randperm(length(x_vec_pts_sort));
x_vec_pts_rand = x_vec_pts_sort(idx);
``````

The following algorithms are compared with sorted and random query points:

• `interp1` code (MATLAB builtin function, MATLAB and MEX)
• `griddedInterpolant` code (MATLAB builtin function, MATLAB)
• `interp_regular` code (proposed method, MATLAB and MEX)
• `interp_fast` code (proposed method, MATLAB and MEX)
• In this document, the benchmark is run on a Intel i5-8250U laptop on Linux (64 bits).

The following files are required to run the benchmark:

Vectorized Call

All the 12500 query points are evaluated at once with a vectorized call.

``````============================ vectorized call

interp1              MATLAB   sorted = 0.74 ms     random = 0.70 ms
interp1              MEX      sorted = 0.70 ms     random = 0.85 ms

griddedInterpolant   MATLAB   sorted = 0.18 ms     random = 0.21 ms
griddedInterpolant   MEX      sorted = NaN ms      random = NaN ms

interp_regular       MATLAB   sorted = 1.92 ms     random = 1.59 ms
interp_regular       MEX      sorted = 2.89 ms     random = 4.18 ms

interp_fast          MATLAB   sorted = 3.62 ms     random = 18.61 ms
interp_fast          MEX      sorted = 1.12 ms     random = 18.45 ms

============================ vectorized call
``````
• MEX files are not faster than MATLAB files.
• Sorted query points are better for `interp_fast`.
• The best overall algorithm is `griddedInterpolant`.
• For vectorized call, `griddedInterpolant` should be prefered.

Non-Vectorized Call

All the 12500 query points are evaluated one by one (in a for-loop).

``````============================ non-vectorized call

interp1              MATLAB   sorted = 534.80 ms   random = 649.80 ms
interp1              MEX      sorted = 94.57 ms    random = 75.42 ms

griddedInterpolant   MATLAB   sorted = 37.21 ms    random = 45.32 ms
griddedInterpolant   MEX      sorted = NaN ms      random = NaN ms

interp_regular       MATLAB   sorted = 45.32 ms    random = 29.57 ms
interp_regular       MEX      sorted = 1.16 ms     random = 1.11 ms

interp_fast          MATLAB   sorted = 11.36 ms    random = 27.46 ms
interp_fast          MEX      sorted = 1.11 ms     random = 17.61 ms

============================ non-vectorized call
``````
• MEX files are faster than MATLAB files.
• Sorted query points are better for `interp_fast`.
• The best overall algorithm is `interp_regular` and `interp_fast`.
• For non-vectorized call, `interp_regular` should be prefered with evenly spaced samples points.
• For non-vectorized call, `interp_fast` should be prefered with arbitrarily spaced samples points.

Compatibility

• Tested with MATLAB R2021a.
• The MATLAB Coder toolbox is required for compiling MATLAB into MEX.
• Compatibility with GNU Octave not tested but probably easy to achieve.

Author

Thomas Guillod - GitHub Profile

Cite As

Thomas Guillod (2022). fast_interpolation_matlab (https://github.com/otvam/fast_interpolation_matlab), GitHub. Retrieved .

MATLAB Release Compatibility
Created with R2021b
Compatible with any release
Platform Compatibility
Windows macOS Linux