NAG Library Function Document

nag_2d_spline_fit_ts_scat (e02jdc)

Note: this function uses optional arguments to define choices in the problem specification and in the details of the algorithm. If you wish to use default settings for all of the optional arguments, you need only read Sections 1 to 10 of this document. If, however, you wish to reset some or all of the settings please refer to Section 11 for a detailed description of the specification of the optional arguments produced by the function.

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

▸▿ 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

▸▿ 11 Optional Arguments

11.1 Description of the Optional Arguments

1 Purpose

nag_2d_spline_fit_ts_scat (e02jdc) computes a spline approximation to a set of scattered data using a two-stage approximation method.

The computational complexity of the method grows linearly with the number of data points; hence large datasets are easily accommodated.

2 Specification

#include <nag.h>

#include <nage02.h>

void	nag_2d_spline_fit_ts_scat (Integer n, const double x[], const double y[], const double f[], Integer lsminp, Integer lsmaxp, Integer nxcels, Integer nycels, Integer lcoefs, double coefs[], Integer iopts[], double opts[], NagError *fail)

Before calling nag_2d_spline_fit_ts_scat (e02jdc), nag_fit_opt_set (e02zkc) must be called with optstr set to "Initialize = e02jdc". Settings for optional algorithmic arguments may be specified by calling nag_fit_opt_set (e02zkc) before a call to nag_2d_spline_fit_ts_scat (e02jdc).

3 Description

nag_2d_spline_fit_ts_scat (e02jdc) determines a smooth bivariate spline approximation to a set of data points

(x_{i}, y_{i}, f_{i})

, for

i = 1, 2, \dots, n

. Here, ‘smooth’ means

C^{1}

C^{2}

. (You may select the degree of smoothing using the optional argument

Global Smoothing Level

The approximation domain is the bounding box

[x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}]

, where

x_{\min}

(respectively

y_{\min}

) and

x_{\max}

(respectively

y_{\max}

) denote the lowest and highest data values of the

(x_{i})

(respectively

(y_{i})

The spline is computed by local approximations on a uniform triangulation of the bounding box. These approximations are extended to a smooth spline representation of the surface over the domain. The local approximation scheme is controlled by the optional argument

Local Method

. The schemes provided are: by least squares polynomial approximation (Davydov and Zeilfelder (2004)); by hybrid polynomial and radial basis function (RBF) approximation (Davydov et al. (2006)); or by pure RBF approximation (Davydov et al. (2005)).

The two-stage approximation method employed by nag_2d_spline_fit_ts_scat (e02jdc) is derived from the TSFIT package of O. Davydov and F. Zeilfelder.

Values of the computed spline can subsequently be computed by calling nag_2d_spline_ts_eval (e02jec) or nag_2d_spline_ts_eval_rect (e02jfc).

4 References

Davydov O, Morandi R and Sestini A (2006) Local hybrid approximation for scattered data fitting with bivariate splines Comput. Aided Geom. Design 23 703–721

Davydov O, Sestini A and Morandi R (2005) Local RBF approximation for scattered data fitting with bivariate splines Trends and Applications in Constructive Approximation M. G. de Bruin, D. H. Mache, and J. Szabados, Eds ISNM Vol. 151 Birkhauser 91–102

Davydov O and Zeilfelder F (2004) Scattered data fitting by direct extension of local polynomials to bivariate splines Advances in Comp. Math. 21 223–271

5 Arguments

1: $n$ – IntegerInput

On entry:

n

, the number of data values to be fitted.

Constraint:

n > 1

2: $x [n]$ – const doubleInput

3: $y [n]$ – const doubleInput

4: $f [n]$ – const doubleInput

On entry: the

(x_{i}, y_{i}, f_{i})

data values to be fitted.

Constraint:

x [j - 1] \neq x [0]

for some

j = 2, \dots, n

and

y [k - 1] \neq y [0]

for some

k = 2, \dots, n

; i.e., there are at least two distinct

x

and

y

values.

5: $lsminp$ – IntegerInput

6: $lsmaxp$ – IntegerInput

On entry: are control parameters for the local approximations.

Each local approximation is computed on a local domain containing one of the triangles in the discretization of the bounding box. The size of each local domain will be adaptively chosen such that if it contains fewer than lsminp sample points it is expanded, else if it contains greater than lsmaxp sample points a thinning method is applied. lsmaxp mainly controls computational cost (in that working with a thinned set of points is cheaper and may be appropriate if the input data is densely distributed), while lsminp allows handling of different types of scattered data.

Setting

lsmaxp < lsminp

, and therefore forcing either expansion or thinning, may be useful for computing initial coarse approximations. In general smaller values for these arguments reduces cost.

A calibration procedure (experimenting with a small subset of the data to be fitted and validating the results) may be needed to choose the most appropriate values for lsminp and lsmaxp.

Constraints:

$1 \leq lsminp \leq n$ ;
$lsmaxp \geq 1$ .

7: $nxcels$ – IntegerInput

8: $nycels$ – IntegerInput

On entry: nxcels (respectively nycels) is the number of cells in the

x

(respectively

y

) direction that will be used to create the triangulation of the bounding box of the domain of the function to be fitted.

Greater efficiency generally comes when nxcels and nycels are chosen to be of the same order of magnitude and are such that n is

O (nxcels \times nycels)

. Thus for a ‘square’ triangulation — when

nxcels = nycels

— the quantities

\sqrt{n}

and nxcels should be of the same order of magnitude. See also Section 9.

Constraints:

$nxcels \geq 1$ ;
$nycels \geq 1$ .

9: $lcoefs$ – IntegerInput

10: $coefs [lcoefs]$ – doubleOutput

On exit: if

fail . code =

NE_NOERROR on exit, coefs contains the computed spline coefficients.

Constraints:

if $Global Smoothing Level = 1$ , $lcoefs \geq (((nxcels + 2) \times (nycels + 2) + 1) / 2) \times 10 + 1$ ;
if $Global Smoothing Level = 2$ , $lcoefs \geq 28 \times (nxcels + 2) \times (nycels + 2) \times 4 + 1$ .

11: $iopts [\dim]$ – IntegerCommunication Array

Note: the dimension,

\dim

, of this array is dictated by the requirements of associated functions that must have been previously called. This array MUST be the same array passed as argument iopts in the previous call to nag_fit_opt_set (e02zkc).

On entry: the contents of iopts MUST NOT be modified in any way either directly or indirectly, by further calls to nag_fit_opt_set (e02zkc), before calling either or both of the evaluation routines nag_2d_spline_ts_eval (e02jec) and nag_2d_spline_ts_eval_rect (e02jfc).

12: $opts [\dim]$ – doubleCommunication Array

Note: the dimension,

\dim

, of this array is dictated by the requirements of associated functions that must have been previously called. This array MUST be the same array passed as argument opts in the previous call to nag_fit_opt_set (e02zkc).

On entry: the contents of opts MUST NOT be modified in any way either directly or indirectly, by further calls to nag_fit_opt_set (e02zkc), before calling either or both of the evaluation routines nag_2d_spline_ts_eval (e02jec) and nag_2d_spline_ts_eval_rect (e02jfc).

13: $fail$ – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_ALL_ELEMENTS_EQUAL: On entry, all elements of x or of y are equal.
NE_ALLOC_FAIL: Dynamic memory allocation failed.
See Section 3.2.1.2 in the Essential Introduction for further information.
NE_BAD_PARAM: On entry, argument $〈value〉$ had an illegal value.
NE_INITIALIZATION: Option arrays are not initialized or are corrupted.
NE_INT: On entry, $lcoefs = 〈value〉$ .
Constraint:
if $Global Smoothing Level = 1$ ,
$lcoefs \geq (((nxcels + 2) \times (nycels + 2) + 1) / 2) \times 10 + 1$ ;
if $Global Smoothing Level = 2$ ,
$lcoefs \geq 28 \times (nxcels + 2) \times (nycels + 2) \times 4 + 1$ .

On entry, $lsmaxp = 〈value〉$ .
Constraint: $lsmaxp \geq 1$ .

On entry, $n = 〈value〉$ .
Constraint: $n > 1$ .

On entry, $nxcels = 〈value〉$ .
Constraint: $nxcels \geq 1$ .

On entry, $nycels = 〈value〉$ .
Constraint: $nycels \geq 1$ .
NE_INT_2: On entry, $lsminp = 〈value〉$ and $n = 〈value〉$ .
Constraint: $1 \leq lsminp \leq n$ .
NE_INTERNAL_ERROR: An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.

An unexpected algorithmic failure was encountered. Please contact NAG.

An unexpected error has been triggered by this function. Please contact NAG.
See Section 3.6.6 in the Essential Introduction for further information.
NE_INVALID_OPTION: The selected radial basis function cannot be used with the RBF local method.

The value of optional argument $Polynomial Starting Degree$ was invalid.
NE_NO_LICENCE: Your licence key may have expired or may not have been installed correctly.
See Section 3.6.5 in the Essential Introduction for further information.

7 Accuracy

Technical results on error bounds can be found in Davydov and Zeilfelder (2004), Davydov et al. (2006) and Davydov et al. (2005).

Local approximation by polynomials of degree

d

for

n

data points has optimal approximation order

n^{- (d + 1) / 2}

. The improved approximation power of hybrid polynomial/RBF and of pure RBF approximations is shown in Davydov et al. (2006) and Davydov et al. (2005).

The approximation error for

C^{1}

global smoothing is

O (n^{- 2})

. For

C^{2}

smoothing the error is

O (n^{- 7 / 2})

when

Supersmooth C2 = YES

and

O (n^{- 3})

when

Supersmooth C2 = NO

Whether maximal accuracy is achieved depends on the distribution of the input data and the choices of the algorithmic parameters. The references above contain extensive numerical tests and further technical discussions of how best to configure the method.

8 Parallelism and Performance

nag_2d_spline_fit_ts_scat (e02jdc) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.

nag_2d_spline_fit_ts_scat (e02jdc) makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.

Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

n

-linear complexity and memory usage can be attained for sufficiently dense input data if the triangulation parameters nxcels and nycels are chosen as recommended in their descriptions above. For sparse input data on such triangulations, if many expansion steps are required (see lsminp) the complexity may rise to be loglinear.

Parts of the pure RBF method used when

Local Method = RBF

have

n

-quadratic memory usage.

Note that if

Local Method = HYBRID

and an initial hybrid approximation is deemed unreliable (see the description of optional argument

Minimum Singular Value LHA

), a pure polynomial approximation will be used instead on that local domain.

10 Example

The Franke function

\begin{matrix} f (x, y) & = & 0.75 \exp (- ({(9 x - 2)}^{2} + {(9 y - 2)}^{2}) / 4) + \\ 0.75 \exp (- {(9 x + 1)}^{2} / 49 - (9 y + 1) / 10) + \\ 0.5 \exp (- ({(9 x - 7)}^{2} + {(9 y - 3)}^{2}) / 4) - \\ 0.2 \exp (- {(9 x - 4)}^{2} - {(9 y - 7)}^{2}) \end{matrix}

is widely used for testing surface-fitting methods. The example program randomly generates a number of points on this surface. From these a spline is computed and then evaluated at a vector of points and on a mesh.

11 Optional Arguments

Several optional arguments in nag_2d_spline_fit_ts_scat (e02jdc) control aspects of the algorithm, methodology used, logic or output. Their values are contained in the arrays iopts and opts; these must be initialized before calling nag_2d_spline_fit_ts_scat (e02jdc) by first calling nag_fit_opt_set (e02zkc) with optstr set to "Initialize = e02jdc".

Each optional argument has an associated default value; to set any of them to a non-default value, or to reset any of them to the default value, use nag_fit_opt_set (e02zkc). The current value of an optional argument can be queried using nag_fit_opt_get (e02zlc).

The remainder of this section can be skipped if you wish to use the default values for all optional arguments.

The following is a list of the optional arguments available. A full description of each optional argument is provided in Section 11.1.

11.1 Description of the Optional Arguments

For each option, we give a summary line, a description of the optional argument and details of constraints.

The summary line contains:

the keywords;
a parameter value, where the letters $a$ , $i$ and $r$ denote options that take character, integer and real values respectively;
the default value.

Keywords and character values are case insensitive.

For nag_2d_spline_fit_ts_scat (e02jdc) the maximum length of the parameter cvalue used by nag_fit_opt_get (e02zlc) is

16

Averaged Spline

a

Default

= NO

When the bounding box is triangulated there are 8 equivalent configurations of the mesh. Setting

Averaged Spline = YES

will use the averaged value of the

8

possible local polynomial approximations over each triangle in the mesh. This usually gives better results but at (about 8 times) higher computational cost.

Constraint:

Averaged Spline = YES

NO

Global Smoothing Level

i

Default

= 1

The smoothness level for the global spline approximation.

$Global Smoothing Level = 1$: Will use $C^{1}$ piecewise cubics.
$Global Smoothing Level = 2$: Will use $C^{2}$ piecewise sextics.

Constraint:

Global Smoothing Level = 1

2

Interpolation Only RBF

a

Default

= YES

Interpolation Only RBF = YES

, each local RBF approximation is computed by interpolation.

Interpolation Only RBF = NO

, each local RBF approximation is computed by a discrete least squares approach. This is likely to be more accurate and more expensive than interpolation.

Local Method = HYBRID

POLYNOMIAL

, this option setting is ignored.

Constraint:

Interpolation Only RBF = YES

NO

Local Method

a

Default

= POLYNOMIAL

The local approximation scheme to use.

$Local Method = POLYNOMIAL$: Uses least squares polynomial approximations.
$Local Method = HYBRID$: Uses hybrid polynomial and RBF approximations.
$Local Method = RBF$: Uses pure RBF approximations.

In general

POLYNOMIAL

is less computationally expensive than

HYBRID

is less computationally expensive than

RBF

with the reverse ordering holding for accuracy of results.

Constraint:

Local Method = POLYNOMIAL

HYBRID

RBF

Minimum Singular Value LHA

r

Default

= 1.0

A tolerance measure for accepting or rejecting a local hybrid approximation (LHA) as reliable.

The solution of a local least squares problem solved on each triangle subdomain is accepted as reliable if the minimum singular value

σ

of the collocation matrix (of polynomial and radial basis function terms) associated with the least squares problem satisfies

Minimum Singular Value LHA \leq σ

In general the approximation power will be reduced as

Minimum Singular Value LHA

is reduced. (A small

σ

indicates that the local data has hidden redundancies which prevent it from carrying enough information for a good approximation to be made.) Setting

Minimum Singular Value LHA

very large may have the detrimental effect that only approximations of low degree are deemed reliable.

A calibration procedure (experimenting with a small subset of the data to be fitted and validating the results) may be needed to choose the most appropriate value for this parameter.

Local Method = POLYNOMIAL

RBF

, this option setting is ignored.

Constraint:

Minimum Singular Value LHA \geq 0.0

Minimum Singular Value LPA

r

Default

= 1.0

A tolerance measure for accepting or rejecting a local polynomial approximation (LPA) as reliable. Clearly this setting is relevant when

Local Method = POLYNOMIAL

, but it also may be used when

Local Method = HYBRID

(see Section 9.)

The solution of a local least squares problem solved on each triangle subdomain is accepted as reliable if the minimum singular value

σ

of the matrix (of Bernstein polynomial values) associated with the least squares problem satisfies

Minimum Singular Value LPA \leq σ

In general the approximation power will be reduced as

Minimum Singular Value LPA

is reduced. (A small

σ

indicates that the local data has hidden redundancies which prevent it from carrying enough information for a good approximation to be made.) Setting

Minimum Singular Value LPA

very large may have the detrimental effect that only approximations of low degree are deemed reliable.

Minimum Singular Value LPA

will have no effect if

Polynomial Starting Degree = 0

, and it will have little effect if the input data is ‘smooth’ (e.g., from a known function).

A calibration procedure (experimenting with a small subset of the data to be fitted and validating the results) may be needed to choose the most appropriate value for this parameter.

Local Method = RBF

, this option setting is ignored.

Constraint:

Minimum Singular Value LPA \geq 0.0

Polynomial Starting Degree

i

Default

= 5

Local Method = HYBRID

,
Default

= 1

otherwise

The degree to be used for the polynomial part in the initial step of each local approximation.

At this initial step the method will attempt to fit with a local approximation having polynomial part of degree

Polynomial Starting Degree

. If

Local Method = POLYNOMIAL

and the approximation is deemed unreliable (according to

Minimum Singular Value LPA

), the degree will be decremented by one and a new local approximation computed, ending with a constant approximation if no other is reliable. If

Local Method = HYBRID

and the approximation is deemed unreliable (according to

Minimum Singular Value LHA

), a pure polynomial approximation of this degree will be tried instead. The method then proceeds as in the

POLYNOMIAL

case.

Polynomial Starting Degree

is bounded from above by the maximum possible spline degree, which is

6

(when performing

C^{2}

global super-smoothing). Note that the best-case approximation error (see Section 7) for

C^{2}

smoothing with

Supersmooth C2 = NO

is achieved for local polynomials of degree

5

; that is, for this level of global smoothing no further benefit is gained by setting

Polynomial Starting Degree = 6

The default value gives a good compromise between efficiency and accuracy. In general the best approximation can be obtained by setting:

If Local Method=POLYNOMIAL
- if $Global Smoothing Level = 1$ , $Polynomial Starting Degree = 3$ ;
- if Global Smoothing Level=2;
  - if $Supersmooth C2 = NO$ , $Polynomial Starting Degree = 5$ ;
  - otherwise $Polynomial Starting Degree = 6$ .
If $Local Method = HYBRID$ , $Polynomial Starting Degree$ as small as possible.

Local Method = RBF

, this option setting is ignored.

Constraints:

if Local Method=HYBRID,
- if $Radial Basis Function = MQ2$ , $MQ3$ , $TPS$ or $POLYHARMONIC3$ , $Polynomial Starting Degree \geq 1$ ;
- if $Radial Basis Function = TPS4$ or $POLYHARMONIC5$ , $Polynomial Starting Degree \geq 2$ ;
- if $Radial Basis Function = TPS6$ or $POLYHARMONIC7$ , $Polynomial Starting Degree \geq 3$ ;
- if $Radial Basis Function = POLYHARMONIC9$ , $Polynomial Starting Degree \geq 4$ ;
otherwise $Polynomial Starting Degree \geq 0$ ;
if $Local Method = POLYNOMIAL$ and $Global Smoothing Level = 1$ , $Polynomial Starting Degree \leq 3$ ;
otherwise $Polynomial Starting Degree \leq 6$ .

Radial Basis Function

a

Default

= MQ

Scaling Coefficient RBF

r

Default

= 1.0

Radial Basis Function

selects the RBF to use in each local RBF approximation, while

Scaling Coefficient RBF

selects the scale factor to use in its evaluation, as described below.

A calibration procedure (experimenting with a small subset of the data to be fitted and validating the results) may be needed to choose the most appropriate scale factor and RBF.

Local Method = POLYNOMIAL

, these option settings are ignored.

Local Method = HYBRID

RBF

, the following (conditionally) positive definite functions may be chosen.

Define

R = \sqrt{x^{2} + y^{2}}

and

ρ = R / r

$GAUSS$	Gaussian $\exp (- ρ^{2})$
$IMQ$	inverse multiquadric $1 / \sqrt{r^{2} + R^{2}}$
$IMQ2$	inverse multiquadric $1 / (r^{2} + R^{2})$
$IMQ3$	inverse multiquadric $1 / {(r^{2} + R^{2})}^{(3 / 2)}$
$IMQ0_5$	inverse multiquadric $1 / {(r^{2} + R^{2})}^{(1 / 4)}$
$WENDLAND31$	H. Wendland's $C^{2}$ function ${\max (0, 1 - ρ)}^{4} (4 ρ + 1)$
$WENDLAND32$	H. Wendland's $C^{4}$ function ${\max (0, 1 - ρ)}^{6} (35 ρ^{2} + 18 ρ + 3)$
$WENDLAND33$	H. Wendland's $C^{6}$ function ${\max (0, 1 - ρ)}^{8} (32 ρ^{3} + 25 ρ^{2} + 8 ρ + 1)$
$BUHMANNC3$	M. Buhmann's $C^{3}$ function $112 / 45 ρ^{(9 / 2)} + 16 / 3 ρ^{(7 / 2)} - 7 ρ^{4} - 14 / 15 ρ^{2} + 1 / 9$ if $ρ \leq 1$ , $0$ otherwise
$MQ$	multiquadric $\sqrt{r^{2} + R^{2}}$
$MQ1_5$	multiquadric ${(r^{2} + R^{2})}^{(1.5 / 2)}$
$POLYHARMONIC1_5$	polyharmonic spline $ρ^{1.5}$
$POLYHARMONIC1_75$	polyharmonic spline $ρ^{1.75}$

Local Method = HYBRID

the following conditionally positive definite functions may also be chosen.

$MQ2$	multiquadric $(r^{2} + R^{2}) \log (r^{2} + R^{2})$
$MQ3$	multiquadric ${(r^{2} + R^{2})}^{(3 / 2)}$
$TPS$	thin plate spline $ρ^{2} \log ρ^{2}$
$POLYHARMONIC3$	polyharmonic spline $ρ^{3}$
$TPS4$	thin plate spline $ρ^{4} \log ρ^{2}$
$POLYHARMONIC5$	polyharmonic spline $ρ^{5}$
$TPS6$	thin plate spline $ρ^{6} \log ρ^{2}$
$POLYHARMONIC7$	polyharmonic spline $ρ^{7}$
$POLYHARMONIC9$	polyharmonic spline $ρ^{9}$

Constraints:

if $Radial Basis Function = MQ2$ , $MQ3$ , $TPS$ or $POLYHARMONIC3$ , $Local Method = HYBRID$ and $Polynomial Starting Degree \geq 1$ ;
if $Radial Basis Function = TPS4$ or $POLYHARMONIC5$ , $Local Method = HYBRID$ and $Polynomial Starting Degree \geq 2$ ;
if $Radial Basis Function = TPS6$ or $POLYHARMONIC7$ , $Local Method = HYBRID$ and $Polynomial Starting Degree \geq 3$ ;
if $Radial Basis Function = POLYHARMONIC9$ , $Local Method = HYBRID$ and $Polynomial Starting Degree \geq 4$ ;
$Scaling Coefficient RBF > 0.0$ .

Separation LRBFA

r

Default

= 16.0 / Scaling Coefficient RBF

A knot-separation parameter used to control the condition number of the matrix used in each local RBF approximation (LRBFA). A smaller value may mean greater numerical stability but fewer knots.

Local Method = HYBRID

POLYNOMIAL

, this option setting is ignored.

Constraint:

Separation LRBFA > 0.0

Supersmooth C2

a

Default

= NO

Supersmooth C2 = YES

, the

C^{2}

spline is generated using additional smoothness constraints. This usually gives better results but at higher computational cost.

Global Smoothing Level = 1

this option setting is ignored.

Constraint:

Supersmooth C2 = YES

NO

nag_2d_spline_fit_ts_scat (e02jdc) (PDF version)

e02 Chapter Contents

e02 Chapter Introduction

NAG Library Manual

NAG Library Function Documentnag_2d_spline_fit_ts_scat (e02jdc)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

11 Optional Arguments

11.1 Description of the Optional Arguments

NAG Library Function Document

nag_2d_spline_fit_ts_scat (e02jdc)