fast_interpolation_matlab
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).
Examples
- run_example_simple.m - Minimal working example for the interpolation code.
- run_example_ode.m - Example with interpolation inside an ODE function.
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:
- run_benchmark_compile.m - Compile the MATLAB files into MEX files.
- run_benchmark_run.m - Run the benchmark for the different methods.
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
andinterp_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.
引用格式
Thomas Guillod (2024). fast_interpolation_matlab (https://github.com/otvam/fast_interpolation_matlab), GitHub. 检索来源 .
MATLAB 版本兼容性
平台兼容性
Windows macOS Linux标签
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!benchmark_matlab
无法下载基于 GitHub 默认分支的版本
版本 | 已发布 | 发行说明 | |
---|---|---|---|
1.2 | Better documentation |
|
|
1.1 | New method for evenly spaced points. |
|
|
1.0.0 |
|