QUESTION
I'm looking for some explanation or advice, not help in solving something. Recently I finished my program and my supervisor said "Ok, now it's time for your first paper: write a scientific text about how your program works". If I understand him correctly it means I have to describe the algorithm I used instead of writing in a manner like "for this purpose I use the builtin Interpolation
function, and for this purpose I use NDSolve
" etc. I know how FindRoot
and NDSolve
work because there is an explanation in the doc pages about the methods they use, but I did not find detailed information about Interpolation
. The only thing I know it fits with polynomial curves.
So my question is: What exactly does the Interpolation
function do? How does it work? How does it determinate (partial) derivatives? And why do 3D data points have to be situated in rectangle order to interpolate a surface?
If there is some literature I may read and then reference it would be great too.
ANSWER
Interpolation function methods
Interpolation
supports two methods:
 Hermite interpolation (default, or
Method>"Hermite"
)  Bspline interpolation (
Method>"Spline"
)
Hermite method
I really can't find any good reference to Hermite method within Mathematica's documentation. Instead, I recommend you to take a look at this Wikipedia article.
The benefits of Hermite interpolation are:
 You can compute them locally at the time of evaluation. No global system solving required. So construction time is shorter, and the resulting
InterpolatingFunction
is smaller.  Multilevel derivatives can be specified at each point.
One problem is that the resulting function is not continuously differentiable ($C^1$ or higher), even if InterpolationOrder>2
or higher is used. See the following example:
Spline method
To be specific, we are using Bspline interpolation with certain knot configurationdepending on the distribution of sample points. I could not find a good web source to describe the method (the Wikipedia article is not great). Although, you can find a stepbystep description of the method in 1D case within Mathematica's documentation (BSplineCurve
documentation, Applications > Interpolation section). Multidimension is simply tensor product version.
The benefits:

InterpolationOrder>d
always guarantees a smooth function of $C^{d1}$ class. 
Evaluation/derivative computation is very fast.
 You can take
BSplineFunction
out of the resultingInterpolatingFunction
(it's the 4th part), which is compatible withBSplineCurve
andBSplineSurface
for fast rendering.
The problems (of current implementation in V8):
 It is machine precision onlyalthough, it is not hard to implement it manually for arbitrary precision using
BSplineBasis
.  It does not support derivative specification.
 Initially it solves global linear system and store the result. So the resulting function is much larger than Hermite method (this is not implementation problem).
Other functions
Some plot functions such as ListPlot3D
have their own methods. Sometimes they call the Bspline method, sometimes they use a method based on distance field (for unorganized points), etc. But probably it is not useful here since they are only supported as a visual measure.