Code covered by the BSD License  

Highlights from
Extrimely fast general n-dimensional interpolators

4.0

4.0 | 1 rating Rate this file 14 Downloads (last 30 days) File Size: 41.6 KB File ID: #30836
image thumbnail

Extrimely fast general n-dimensional interpolators

by

 

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

| Watch this File

File Information
Description

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.

MATLAB release MATLAB 7.11 (R2010b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (3)
10 Aug 2012 Matthias

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.

10 Aug 2012 Matthias

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.

26 Sep 2011 Travis Storm

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

interpUtil.cpp
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?

Contact us