No BSD License  

Highlights from
Fast interpolation

4.4

4.4 | 12 ratings Rate this file 32 Downloads (last 30 days) File Size: 3.44 KB File ID: #10286
image thumbnail

Fast interpolation

by

 

08 Mar 2006 (Updated )

Performs nearest-neighbor or linear interpolation much faster than interp1 when an evenly-spaced lib

| Watch this File

File Information
Description

This function performs interpolation faster than MATLAB's "interp1" function. In the limit of small library and search arrays, it is ~5x faster. In the limit of large library arrays, qinterp1 has a flat scaling, while interp1 has a linearly increasing scaling (see the image for this file). qinterp1 requires an evenly spaced, monotonically increasing x array. Like interp1, qinterp1 returns NaN for xi values that are out of bounds.

Per John D'Errico's suggestion, the nearest-lower-neighbor method has been changed to now use true nearest-neighbor interpolation (at a slight speed cost).

A note on error checking: Because any error checking of the library array would destroy the flat scaling law, this function performs no error checking on the library (x and y) arrays. This function will return an error if the y and xi arrays are not both column or both row vectors.

Type "help qinterp1" for usage instructions.

This should be backwards compatible for quite a few releases. It is platform-independent.

The attached image shows the result of speed tests performed on a 2.4GHz, 2GB Windows XP machine. The same x, y, and xi vectors were used for each algorithm. The qinterp1 method came out ahead in all parameters tested. Note that, surprisingly, in the case of evenly-spaced x vectors, interp1q is slower than interp1 for most parameters, and interp1's nearest-neghbor interpolation is almost always slower than linear interpolation!

Note: After writing this function, I noticed Umberto Picchini's fast interpolation function, which provides up to a 4x speedup without the requirement of an evenly-spaced array. The file ID is 8627.

Acknowledgements

This file inspired Fast 2 Dimensional Interpolation, Scale Time, and Quicker 1 D Linear Interpolation: Interp1qr.

MATLAB release MATLAB 7.1.0 (R14SP3)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (13)
16 Jun 2014 Philip

It is true that 'qinterp1' is faster than MATLAB's 'interp1q', but I find that 'griddedInterpolant' is much faster than 'qinterp1'. Perhaps this function was created before 'griddedInterpolant'. Do you think it's possible to beat the execution time of 'griddedInterpolant'? Thanks for sharing the code.

06 Oct 2012 Massimo Ciacci

I liked this function in terms of speed, especially for large sized xi. However I found two shortcomings, which i explain in these examples:

Shortcoming 1:
--------------
Yi = qinterp1([14,15,16],[10 38 40],[17])

??? Error using ==> times
Matrix dimensions must agree.

Shortcoming 2:
--------------
>> Yi = qinterp1([3,15,16],[10 38 40],[2 3 14 15.5 16 17])

Yi =

NaN
10.0000
35.6667
38.0833
38.1667
38.3333

whereas the correct result should have been

>> Yi = interp1([3,15,16],[10 38 40],[2 3 14 15.5 16 17])

Yi =
NaN 10.0000 35.6667 39.0000 40.0000 NaN

The problem lies in the fact that the function assumes uniform spacing in the input x, which can be checked adding this extra check:

if sum(diff(diff(x)))
error('this function assumes uniform x spacing!');
end

07 Aug 2012 Daniel

This is very very well done. Thank you so much for creating this!

23 Jul 2012 Elizabeth  
23 Jul 2012 Elizabeth  
31 May 2012 Martin Saravia

Excellent job!!!,it works 7 times faster than linterp 1 in my code.

23 Jan 2009 Adam Chapman

Brilliant job, well done. Works even better with Greg Palmer's suggestion.

Thanks

28 Dec 2007 ahmed khaled  
05 May 2007 si aj√°  
18 Sep 2006 Greg Palmer

Works great! I found it to be about 2x faster for my application. One thing I noticed you may want to change is to use NaN(...) instead of NaN*ones(...), which should be faster.

10 Mar 2006 John D'Errico

Better now with a proper nearest computation. The goal of this code is maximum speed, any error checks are inconsistent with that goal. This code will be as fast as I would reasonably expect it to be.

10 Mar 2006 John D'Errico

This does not actually do nearest neighbor interpolation, but instead nearest lower neighbor. In the branch for nearest neighbor, the author could have used round instead of floor to produce true nearest neighbor interpolation with no loss in speed. My rating would go up if this was repaired.
For those who really do need a simple fast interpolant, this code should provide it, as long as your independent variable is uniform. In its quest for speed however, this code also has no error checks on its inputs. I do very much like that this is an m file, not mexed.

09 Mar 2006 Duane Hanselman

FYI: Umberto Picchini's submission 8627 is a mex file, so it is not as platform independent as this submission.

Updates
10 Mar 2006

Previous version returned the wrong result (shifted by one index from the proper result). Extra speed-ups also added.

10 Mar 2006

Changed nearest-lower-neighbor to true nearest-neighbor.

Contact us