TOMS790: Any Info?

[DavidB]

I was recently directed to TOMS790, "Bivariate Interpolation of Scattered Data".
It employs a cubic polynomial (Shepard Method) to interpolate scattered data.

I found a little info about this routine on the NETLIB site (TOMS/790) and on the website of a Research Associate at The Florida State University.

Beyond that, I know next to nothing about this routine.

Anybody in these forums know anything about this routine? How does it differ from other interpolation routines?

I am particularly interested in knowing if this routine has been succeeded by a newer routine.
If not, and it is still a good routine, why does it seem to be so obscure and virtually unknown?
If it has been succeeded by a newer routine, what is the new routine?

Any help is appreciated.

[Julien Langou]

Hi David, the forum is more about the LAPACK software. (So netlib's ACM TOMS 790 is a little off topic.) On my end, I do not know this subroutine. Cheers, Julien.

[DavidB]

Hi, Julien.

Thanks for posting back.

" . . . the forum is more about the LAPACK software."

Yes, I know, but these forums do attract a crowd with numerical interests. If anybody might know something about this algorithm, they might visit these forums; these forums are the closest thing to any support for the old algorithms I can think of. Personally, I never heard of this algorithm before I was asked some questions about it, which I cannot answer. I can't help but wonder, if this software performs such a unique and/or useful task, why does it seem to be so unknown? What does it do that other interpolation routines do not?

Are there any other numerical forums on which I could post my questions?

[admin]

Hey,
I would contact the Author of the routine directly.
Just google his name, you will find his webpage.
Hope it hopes

[lawrence mulholland]

Further Info on this algorithm.

The various dimension variants of TOMS790 has been implemented in the NAG Library
see http://www.nag.co.uk/numeric/fl/nagdoc_ ... conts.html
the variants are listed under e01{s,t,z}*

As far as NAG is aware, this is a very robust algorithm provided there is a sufficient
number of points for the number of dimensions.

Most attention in this field in recent times has been given to radial basis functions for
which there is a wealth of literature and some software. This isn't my area of expertise,
but I believe that the TOMS790 algorithm could be viewed in this context also.

[CyLith]

Just for my own edification, why use radial basis function instead of, say, computing a Delaunay triangulation on the points and using spline interpolation (linear or higher order)? I'm genuinely curious about the applications of something like toms790.

[DavidB]

@admin:

Thanks for the suggestion. I did not think of that. Many TOMS routines are pretty old; I assumed that was the case here too, and that the author had moved on to other things long ago.


@lawrence Mulholland

" . . . this is a very robust algorithm provided there is a sufficient number of points for the number of dimensions."

So, in a nutshell, this algorithm is for cubic interpolation in multiple dimensions?

I am familiar with Hermite interpolation, cubic spline interpolation, polynomial interpolation, etc.--routines in one dimension (basically, whatever would be covered in an undergraduate numerical methods course).
And I have a couple numerical books on my bookshelf, but neither of them cover interpolation in multiple dimensions.

Now that I have some context for this routine, I can better research it.

A related question: does this routine get much use?
Or are its applications highly specialized and, therefore, rarely used?

[lawrence mulholland]

@DavidB

So, in a nutshell, this algorithm is for cubic interpolation in multiple dimensions?

Not quite (but maybe close enough): it is a weighted sum of interpolants where the weights are w.r.t. distance from interpolation point(IP)
and are zero outside a given radius from the IP. The interpolants can take several forms: linear, quadratic, cubic.

Now that I have some context for this routine, I can better research it.

If you have access to the ACM Digital Library you can download the source material (SHEPPACK) and try it out.
(Don't want to be salesy on this forum, but you could ask NAG Support for a trial licence of NAG Fortran, C or
MATLAB Library and start with the example programs for the e01{s,t,z}* routines there)

A related question: does this routine get much use?
Or are its applications highly specialized and, therefore, rarely used?

I can tell you that NAG added routines for 4, 5 and >5 dimensions in recent Marks of its libraries because of
special requests for these. So yes they are currently being used.

@CyLith

Just for my own edification, why use radial basis function instead of, say, computing a Delaunay triangulation on the points and using spline interpolation (linear or higher order)? I'm genuinely curious about the applications of something like toms790.

Yes, triangulation and interpolation within a containing triangle is a popular option we have found.
The appropriate choice is dependent on the nature of the data being interpolated. Shepard algorithms
are generally robust; the smoothing over interpolants means that non-smooth noisy data can still
produce a reasonable global approximating function.