8

I'm trying to perform Fitted Value Iteration (FVI) in python (involving approximating a 5 dimensional function using piecewise linear interpolation).

scipy.interpolate.griddata works perfectly for this. However, I need to call the interpolation routine several thousand times (since FVI is a MC based algorithm).

So basically, the set of points where the function is known is static (and large - say 32k), but the points i need to approximate (which are small perturbations of the original set) is very large (32k x 5000 say).

Is there an implementation of what scipy.interpolate.griddata does that's been ported to CUDA? alternatively, is there a way to speed up the calculation somehow?

Thanks.

user1726633
  • 356
  • 2
  • 10

1 Answers1

1

For piece-wise linear interpolation, the docs say that scipy.interpolate.griddata uses the methods of scipy.interpolate.LinearNDInterpolator, which in turn uses qhull to do a Delaunay tesellation of the input points, then performs standard barycentric interpolation, where for each point you have to determine inside which hypertetrahedron each point is, then use its barycentric coordinates as the interpolation weights for the hypertetrahedron node values.

The tesellation is probably hard to parallelize, but you can access the CPU version with scipy.spatial.Delaunay. The other two steps are easily parallelized, although I don't know of any freely available implementation.

If your known-function points are on a regular grid, the method described here is specially easy to implement in CUDA, and I have worked with actual implementations of it, albeit none publicly available.

So I am afraid you are going to have to do most of the work yourself...

Jaime
  • 65,696
  • 17
  • 124
  • 159
  • Hi, yes - I did eventually end up doing most of the work myself. I looked at the implementation of find_simplex in scipy.spatial.Delauny and found that the basic idea can be easily parallelized for sufficiently many points. So basically I run 2 loops - one to find (and store) the simplex for each MC sample and one to look up the stored simplex and calculate its barycentric coordinates for interpolation. It's limited by video memory but it's very fast. – user1726633 Jan 02 '13 at 13:39
  • 1
    Did you ever upload this anywhere? I'm looking for a cuda version of griddata now. – TomNorway Jan 12 '21 at 15:53