Optimized interpolation method with fixed-location sample data points?
Welcome to an interesting and important field of research!

Interpolation is a large topic and there are many techniques. I agree that the GIS or math forum could be more initiated, but for completeness, I'll post some thoughts here. 

The choice of method depends on the type of data you are using and the implementation depends on your environment. GIS software should always have a number of methods and parameters to adjust. It's also rather easy to create a script in e.g python or matlab to test and evaluate interpolation methods (E.g this). 

Some questions to answer before you chose your method are:


Can I trust all my data? How much noise do I have?
Should only the nearest points be considered for the interpolation? How far should I 'feel' the values from data points?
How many dimensions should be interpolated? E.g. should I take time  into consideration?
Should the curves be as smooth as possible? 
Should all interpolated values be in a specific range, within min-max of the whole data set or between the nearest points? 
Do I know the total value? E.g. when interpolating population density I might know the total population and this could help me find the right interpolation method. 
Process speed, that is an issue in your case might force you to choose a simpler technique. 


Wikipedia has an overview and Caruso, C., and F. Quarta. "Interpolation methods comparison." Gives a rather good introduction of the techniques and there are some good webpages on GIS and interpolation. 

The most important step is to test the method you choose. Again, there are various ways to do so, but the easiest is to simply leave points out from you data set and interpolate the values without them. Try to make the interpolated value as close to the data value as possible. 

Kriging are methods based on the actual data instead of a curve. It's often a good first try on spatial data but also in other application like this.
Spline methods produces smoother curves. People doing computer graphics are experts on this, but there can also be applications where you'll aspect smooth changes in a model. 

Naturally, more complex methods (e.g. kriging) take longer time to process, whiles simpler algorithms (e.g. bilinear or nearest-neighbor) are faster. Lower resolution of your output raster (array) would also speed up the process. You can let your resolution depend on the variance of the data, so that you interpolate less points in a flat surface and more points for a surface with higher relief. This techniques are common practice in signal processing and the experts are here.