Extrimely fast general n-dimensional interpolators

Version (41.6 KB) by Quant Guy
Mex C++ interpolator routines for general pp-forms in any dimension. Multithreaded.
Updated 23 Mar 2011

View License

This interpolation package re-implements Matlab's built in methods ppval (1-d case polynomial evaluator) and ppual (multidimensional polynomial evaluator) which are used by Matlab to evaluate polynomial in their so called "pp-form". Matlab's built in versions are extrimely slow even though considering their high relative importance in many fields, such as finance or computer graphics. In my own field efficient polynomial evaluation is as important as efficient FFT is for signal processing engineers.

This package introduces two functions named ppmval and ppuval ('m' for multivariate, 'u' for univariate) which evaluate general polynomials in their pp-form. Representing polynomial in pp-form is the most cost-efficient way to evaluate piecewise polynomials.

As name suggest ppmval is optimized for evaluating any polynomial mappings from R^m to R^n where m > 1 and n >= 1. ppuval on the other hand is optimized for univariate polynomials of any m (constant, linear, quadratic, spline, etc...)

Interfaces are vectorized meaning that you can fetch many evaluation sites at one call. In addition to that, algorithms are multi threaded meaning that you can utilize your computer's every core to do the calculation. The valuation problem is embarrassingly parallel so that you can expect good multi-threading results.

Algorithms are designed to use only single threaded evaluation for small input sizes as there are threading overhead involved. For small sized inputs single threaded evaluation is more faster as the lump cost of threading dominates. For larger inputs, speed increase can be seen clearly. The "threshold" limit is macro defined in interpUtil.cpp so that you can easily change it to fit your environment and purposes. In my own computer I came to the conclusion that if you need to evaluate over 1024 points at once, then multi threading is used.

The multithreading uses Visual C++ native parallel pattern library that ships with VS 2010. This means that you can't compile and link the libraries with older VS as this library is not present there. However free Express Edition from Microsoft can be downloaded if you do not already have VS 2010. For older users I tried to attatch pre-compiled mexw32 files, but Mahworks did not like the idea (sorry!).

Here are the installation instructions

1. Unzip Interpolators.zip to folder of your desire.
2. Start Matlab
3. Add the unzip folder to your Matlab path.
4. In Matlab prompt type installer(<your install folder goes here>)
5. Installer automatically compiles the library and makes necessary linkings to generate two mex-files ppmval and ppual.

6. Read the docs that explain the function behaviour and contain very simple examples.

7. Run Results.m that does benchmark comparison of this implementation to Matlab's built in evaluators. This also shows examples of the use cases how this interface is supposed to be used. It might be the case that you need to have spline (or curve fit toolbox) to be able to generate general splines in higher dimensions.

8. Enjoy!

When I have (and IF) some spare time, will make the CUDA implementation of these interpolators.

Cite As

Quant Guy (2024). Extrimely fast general n-dimensional interpolators (https://www.mathworks.com/matlabcentral/fileexchange/30836-extrimely-fast-general-n-dimensional-interpolators), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2010b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Call C++ from MATLAB in Help Center and MATLAB Answers

Community Treasure Hunt

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

Start Hunting!
Version Published Release Notes