File Exchange

image thumbnail

Extrimely fast general n-dimensional interpolators

version 1.0 (41.6 KB) by

Mex C++ interpolator routines for general pp-forms in any dimension. Multithreaded.



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

Comments and Ratings (4)

Richard Crozier

Very useful, and very quick. My only gripe is that it's MSVC specific in it's current form. I wrapped the MSVC specific parts in #idefs to get it to work on linux, like:

#ifdef _MSC_VER
#include <ppl.h>
#define nParMin 1024

You will also need to put the parallel bits of the code in an #ifdef, which obviously means the parallelised parts won't work, but very useful all the same. Thanks.


Regarding my last post:
I call ppuval very often in an optimization. If I write 'clear mex' at the end of one complete optimization run, the mexfile is cleared from memory but the memory is not released. Writing 'clear mex' after each call to the mexfile slows down the computation considerably. How to clear the memory without slowing down the computation? Thank you.


It works fine (almost), but I have a problem with memory. It seems that the memory allocated by ppuval is not freed afterwards. This leads to an increasing Matlab memory demand which finally gives me an 'Out of Memory' error for often repeated evaluations. I'm using Matlab 2011b 32 bit with Windows 7 64 bit.
Do you have any hint how to fix this? Thank you.

@ Travis Storm: I think you miss some header files. If you download Visual C++ 2010 Express, they should be included though.

Travis Storm

Love the idea, but I get the following error when I try to run installer:

interpUtil.cpp(3) : fatal error C1083: Cannot open include file: 'ppl.h': No such file or directory
  C:\PROGRA~1\MATLAB\R2010A\BIN\MEX.PL: Error: Compile of 'interpUtil.cpp' failed.
??? Error using ==> mex at 222
Unable to complete successfully.

Error in ==> installer at 5
    mex interpUtil.cpp -c

Is a header file missing?

MATLAB Release
MATLAB 7.11 (R2010b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video