What is the preferred and efficient approach for interpolating multidimensional data?

Things I'm worried about:

1. performance and memory for construction, single/batch evaluation
2. handling dimensions from 1 to 6
3. linear or higher-order
4. ability to obtain gradients (if not linear)
5. regular vs scattered grid
6. using as Interpolating Function, e.g. to find roots or to minimize
7. extrapolation capabilities

Is there efficient open-source implementation of this?

I had partial luck with scipy.interpolate and kriging from scikit-learn.

I did not try splines, Chebyshev polynomials, etc.

Here is what I found so far on this topic:

[Python 4D linear interpolation on a rectangular grid][1]

[Fast interpolation of regularly sampled 3D data with different intervals in x,y, and z][2]

[Fast interpolation of regular grid data][3]

[What method of multivariate scattered interpolation is the best for practical use?][4]

  [1]: http://stackoverflow.com/questions/14119892
  [2]: http://stackoverflow.com/questions/16217995
  [3]: http://stackoverflow.com/questions/16983843
  [4]: http://stackoverflow.com/questions/592026