Book contents
- Frontmatter
- Contents
- Preface
- 1 Applications and motivations
- 2 Haar spaces and multivariate polynomials
- 3 Local polynomial reproduction
- 4 Moving least squares
- 5 Auxiliary tools from analysis and measure theory
- 6 Positive definite functions
- 7 Completely monotone functions
- 8 Conditionally positive definite functions
- 9 Compactly supported functions
- 10 Native spaces
- 11 Error estimates for radial basis function interpolation
- 12 Stability
- 13 Optimal recovery
- 14 Data structures
- 15 Numerical methods
- 16 Generalized interpolation
- 17 Interpolation on spheres and other manifolds
- References
- Index
14 - Data structures
Published online by Cambridge University Press: 22 February 2010
- Frontmatter
- Contents
- Preface
- 1 Applications and motivations
- 2 Haar spaces and multivariate polynomials
- 3 Local polynomial reproduction
- 4 Moving least squares
- 5 Auxiliary tools from analysis and measure theory
- 6 Positive definite functions
- 7 Completely monotone functions
- 8 Conditionally positive definite functions
- 9 Compactly supported functions
- 10 Native spaces
- 11 Error estimates for radial basis function interpolation
- 12 Stability
- 13 Optimal recovery
- 14 Data structures
- 15 Numerical methods
- 16 Generalized interpolation
- 17 Interpolation on spheres and other manifolds
- References
- Index
Summary
So far we have dealt mainly with the theoretical background of scattered data approximation and interpolation. Except for the moving least squares approximation we have not discussed an efficient implementation of our theory. But from the investigation of the condition number of straightforward interpolation matrices we know that special techniques have to be developed to get an efficient but still accurate approximation method. Several approaches will be discussed in the next chapter.
Crucial to all these methods is the choice of the underlying data structure. It is worth reflecting for a while on how the centers can be stored in a computer most successfully. Thus, in this chapter we will discuss different ways of representing the centers X = {x1, …, xN} ⊆ Ω ⊆ ℝd.
Let us start by collecting possible requests about the set of points X that the data structure should be able to answer efficiently.
The first question every user has to answer is whether all points should be kept in the main memory of the computer or whether the number of points is so large that it has to be stored on a hard disk or other external device. The difference is that in the latter case a reasonable ordering of the data points reduces the number of disk accesses, resulting in a dramatic reduction in run time. There is also an improvement in the first situation by a reasonable ordering, because of the cache of the computer, but it is not dramatic. We will concentrate on the situation where all points can be kept in the main memory of the computer.
- Type
- Chapter
- Information
- Scattered Data Approximation , pp. 230 - 252Publisher: Cambridge University PressPrint publication year: 2004