image thumbnail

fast_interpolation_​matlab

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

16 Downloads

Updated 12 May 2022

From GitHub

View license on GitHub

MATLAB Code for Fast Linear Interpolation

license - BSD language - MATLAB category - science status - maintained

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).

Examples

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

License

This project is licensed under the BSD License, see LICENSE.md.

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

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.