\input texinfo   @c -*-texinfo-*-
@c %**start of header
@setfilename lip.info
@settitle Lip Manual 1.2
@c %**end of header

@c==============================================================================
=@c this is the copyright lable which can be duplicated later on using the 
insert@c copyright command

@copying


GNU GENERAL PUBLIC LICENCE 

Version 2, June 1991

Copyright @copyright{} 1989, 1991 Free Software Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. 
 

@end copying


@c =============================================================================
@c the title page wich only appears if info page is passed to latex to produce
@c printed document.

@titlepage
@title Lip Scattered data Interpolation Software
@vskip 0pt plus 1filll
@insertcopying
@end titlepage

@c==============================================================================
@c Output the table of the contents at the beginning.

@contents

@c =============================================================================
@c declaring the top node of the info page.

@ifnottex
@node Top
@top Class Library lip for Multivariate Scattered Data Interpolation

This info manual describes a method of multivariate scattered data interpolation and the programming library @strong{lip} which implements this method.

We assume that the data set is generated by a Lipschitz continuous function @i{f}, with the Lipschitz constant @i{M}.This method will interpolate the data with a Lipschitz function @i{g}, which is the best approximation to @i{f} in the worst case scenario. It provides best uniform error bounds, and thus translates into reliable learning of @i{f}. The class library @b{lip} is written in @b{C++} language. It provides an interface to various methods of calculating @i{g}.The choice of the method depends on the dimension of the data, the size of the data set and on how many evaluations of the interpolant are required. The usage of @strong{lip} and its numerical performance are illustrated on several examples.


@insertcopying
@end ifnottex

@c =============================================================================
@c contents of the top node note that every entry in the menu must have a node
@c defined for it.

The menu below lists the major nodes, which give a brief background, overview of the library and illustrative examples on how to use it.

@menu
* Introduction::     		Overview of software.
* Features of the Interpolant::	Main properties of the interpolant
* Description of Library:: 	Interpolant methods. 
* Examples::			Interpolant in action.    
* Index::            		Complete index.
@end menu


@c ==============================================================================
@c first node definition must introduce chapter and index tags if you wish the
@c node to appear in the contents and index. Index tag can be placed anywere
@c in the document and will serve as a link for quick referencing from the info
@c page index to the location of the tag.

@c @node Introduction, Features of the Interpolant, Top, Top
@node Introduction
@chapter Introduction

@cindex chapter, Introduction

This document describes the programming library @strong{lip}, which implements a method of reliable multivariate interpolation of scattered data.The underlying
interpolation method assumes that the interpolated function is Lipschitz continuous, and relies on the knowledge (or estimate) of its Lipschitz constant. The
Lipschitz constant is easily interpreted as the upper bound on the rate of change of the function, but the function needs not be differentiable. The computed
interpolant has a distinctive feature of providing the best approximation to the unknown function that generated the data in the worst case scenario. 

The Lipschitz interpolant possesses a number of desirable features, such as continuous dependence on the data, preservation of Lipschitz properties and of the range of the data, uniform approximation and best error bounds. On the practical side, construction and evaluation of the interpolant is computationally stable. There are two alternative ways to compute the interpolant: fast and explicit. The fast method involves a preprocessing step after which the speed of evaluation is proportional to the logarithm of the size of the data set. For higher dimensions, the preprocessing step becomes too expensive, and limited RAM may prevent efficient storage and use of the data structures. In this case there is the second alternative to use the explicit evaluation method, which does not require preprocessing. The availability of two alternative evaluation methods is a distinctive feature of the presented approach.

The described interpolation method is highly competitive to the alternative approaches in terms of efficiency and accuracy, and works irrespectively of the dimension or distribution of data points.

@c===============================================================================
@c second node

@c @node Features of the Interpolant, Introduction, Description of Library, Top
@node Features of the Interpolant
@chapter Features of the Interpolant

@cindex chapter, Features of the Interpolant

The interpolant @i{g(x)} implemented in this library provides the best estimate of the unknown function @i{f} in the worst case scenario, based on the provided data and its Lipschitz constant @i{M}. An estimate of @i{M} should be provided by the user, but can also be computed from the data. In many cases an educated guess is enough.

In addition, this method has several useful features.

The interpolant @i{g} provides a local approximation scheme (i.e., values of @i{g} depend only on the nearest data points).

@enumerate
@item Preservation of the range of the data: @i{min_k@{y^k@} <= g(x) <= max_k@{y^k@}.}

@item
@i{g} approximates @i{f} uniformly. The upper bound on the error of approximation is 
@i{M max_x min_k d(x,x^k)}, i.e., proportional to the distance between the most remote @i{x} and its nearest neighbour in the data set. This upper bound provides a guarantee on the quality of approximation regardless the distribution of data points or which particular function @i{f element of Lip(M)} generated these data. 

@item
For simplicial distance @i{d(x,x^k)} the interpolant is a piecewise continuous linear function.

@item
The Lipschitz constant of @i{g} with respect to @i{d} is @i{M}. 

@item
The interpolant @i{g} depends continuously on the data. 

@item
The interpolant @i{g} provides a local approximation scheme (i.e., values of @i{g} depend only on the nearest data points).

@end enumerate

@c===============================================================================
@c third node

@c @node Description of Library, Examples, Features of the Interpolant, Top
@node Description of Library
@chapter Description of Library
@cindex chapter, Lib Description

The main class which provides the interface to the preprocessing and computation is called @code{STCInterpolant}. It is illustrated in the following sections, together with amore extencive description of the interface.  Can be viewed via the following menu:

@menu
* Classes STCInterpolant & SLipInt::	interface of class STCInterpolant 
* STCInterpolant member methods::	more detailed view of STCInterpolant interface
* SLipInt member methods::		more detailed view of SLipInt functionality
@end menu


@c ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
@c chapter three section

@c @node Classes STCInterpolant and SLipInt, Description of Library, Closer Look at Interface, Description of Library
@node Classes STCInterpolant & SLipInt
@section Class STCInterpolant
@cindex section, interface of class STCInterpolant

@example
class STCInterpolant @{ //saw-tooth cover interpolant
public:
 // supplies the data set to this class. 
 // All other methods are called after SetData.
      void SetData(int dim, int K, double* x, double* y, int test=0);
 // Determines an estimate of the Lipschitz constant from the data    
      double DetermineLipschitz();
 // Constructs the interpolant for either fast or explicit evaluation 
      void Construct();
      void ConstructExplicit();
 // Computes the value of the interpolant
      double Value(int dim, double* x);
      double ValueExplicit(int dim, double* x);
// Sets the value of the Lipschitz constant (or its estimate)
      void SetConstants(double newconst);
... 
@};
@end example

@example
class SLipInt @{ //simple Lipschitz interpolant
public:
//  Computes the interpolant value by explicit method in l-2,l-Inf norm
      double  ValueInf(int dim,int K,double* x,double* X,double* Y,double LC);
 double  Value2(int dim,int K, double* x, double* X,double* Y,double LC);
// Estimates the Lipschitz constant in l-2 or l-Inf norm
      void    ComputeLipschitzInf(int dim, int K, double* X, double* Y);
      void    ComputeLipschitz2(int dim, int K, double* X, double* Y);
...
@};
@end example

@c ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
@c chapter three section

@c @node Closer Look at Interface, Class STCInterpolant, Closer Look at Interface, Description of Library
@node STCInterpolant member methods
@section STCInterpolant member methods
@cindex section, STCInterpolant member methods

@subsection SetData(int dim, int K, double* x, double* y, int test=0)

This method supplies the data set to be interpolated. The data set is supplied in the variables @i{x} and @i{y}. @i{x} is a two-dimensional array @i{K x dim} that contains values @i{x^k_i} in its rows, and @i{y} is an array of size @i{K} which contains the values @i{y^k}. @i{K} is the size of the data set and $dim$ is the dimension. The last parameter @i{test} may be omitted, but if it is set to 1, then the data will be screened for repeated @i{x} (which slows down the process marginally). The construction algorithm assumes that all data points are unique. If the user is unsure, @i{test} must be set to 1. The original data in @i{x}, @i{y} is not needed after the call to @i{SetData}. @i{SetData} must be called only once before any other method.

@subsection double DetermineLipschitz()

This method determines an (under)estimate of the Lipschitz constant based on the data. Bear in mind that @i{DetermineLipschitz} is a rather slow procedure
@i{O(mK^2)} and should be avoided if there are other means to estimate the Lipschitz constant. Returns the computed value of the Lipschitz constant.

@subsection SetConstants(double newconst) and SetConstants()

Supplies the Lipschitz constant to the algorithm, either provided by the user, or calculated from the data. It can be called with no parameters after @i{DetermineLipschitz} only. 

@subsection Construct()

Performs the preprocessing step, necessary for the subsequent evaluation by the fast method. This method may require significant computational effort. @strong{Should not be called after @i{ConstructExplicit()}.}

@subsection ConstructExplicit()

Prepares the data for the subsequent evaluation of the interpolant using explicit evaluation. No significant preprocessing. @strong{Should not be called after @i{Construct()}.} 

@subsection double Value(int dim, double* x )

Computes and returns the value of the interpolant @i{g(x)} using the fast method. Should be called after preprocessing by @i{Construct}. If called after @i{ConstructExplicit}, the explicit evaluation routine @i{ValueExplicit} will be executed instead. Parameter @i{x} is an array of size @i{dim}. @i{dim} should be specified as the dimension of the data @i{m} (the algorithm will automatically compute the required slack variable). The user may precompute the slack variable himself (see examples in the next section), and specify @i{dim} as @i{m+1}, which is marginally faster. 

@subsection double ValueExplicit(int dim, double* x )

Computes the value of the interpolant at @i{x} using explicit method. Can be called after @i{Construct} or @i{ConstructExplicit}. As in @i{Value}, @i{dim} should be specified as the dimension of the data @i{m} (the algorithm will automatically compute the required slack variable). The user may precompute the slack variable himself, and specify @i{dim} as @i{m+1}, which is marginally faster. Parameter @i{x} is an array of size @i{dim}. Returns @i{g(x)}.

@subsection FreeMemory()

Frees the memory occupied by the data structures computed in @i{Construct()}, which can be very large. @i{It destroys the interpolant, and @i{Value()} methods cannot be called after @i{FreeMemory()}.} Automatically called from the destructor. This method is useful to deallocate memory while the object @i{STCInterpolant} still exists. 

@subsection int LastError()

Returns the error code of the last operation. Useful to check whether the construction or evaluation of the interpolant were successful. 0 indicates a successful operation. Other possible values defined in the @i{interpol.h} file are: 1 -- lower interpolation failed, 2-- upper interpolation failed, 3 -- both failed, 10 -- Lipschitz constant too small, or repeated data. 

@strong{NOTE:} There are variations of @i{Value} and @i{ValueExplicit} methods, which use parameter @i{x} of type @i{dVec}. This type is defined as @i{TNT::Vector<double>} in @i{common.h}, and it uses @i{TNT} library (included). @i{TNT} library available from (@url{http://math.nist.gov/tnt/}) provides a convenient way of coding vectors and matrices, and is used internally by @strong{lip}. Since the user may prefer other ways to code vectors, generic type @i{double* } is used in this document. See @i{interpol.h} and examples for more detailed information.
                                                                                                                
@c ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
@c chapter three section

@c @node Closer Look at Interface, Class STCInterpolant, Closer Look at Interface, Description of Library
@node SLipInt member methods
@section SLipInt member methods
@cindex section, SLipInt member methods

@subsection double  ValueInf(int dim,int K,double* x,double* X,double* Y,double LC)

Computes and returns the value of the interpolant @i{g(x)} with @i{d(x,z)=max(|x_i -z_i|)}. Does not require any preprocessing. @i{dim} is the dimension, @i{K} is the number of data, @i{x} is the vector of size @i{dim}, @i{X} is the vector of data of size @i{K * dim} which contains values @i{x^k}_i$ in its rows, @i{y} is the vector of size @i{K} of values to be interpolated, @i{LC} is the Lipschitz constant.

@subsection double  ValueInf(int dim,int K,double* x,double* X,double* Y,double*LC)

Variation of the above, but @i{LC} is a vector of size @i{dim} of Lipschitz constants with respect to the @i{i}-th variable.

@subsection double  ValueInf(int dim,int K,double* x,double* X,double* Y)

Variation of the above, uses Lipschitz constants automaticlly identified from the data. @strong{Should only be called after @i{ComputeLipschitzInf()}}.

@subsection double  Value2(int dim,int K, double* x, double* X,double* Y,double LC)

Computes and returns the value of the interpolant @i{g(x)} with @i{d(x,z)} being Euclidean distance. The parameters are the same as in @i{ValueInf()}.

@subsection double  Value2(int dim,int K, double* x, double* X,double* Y)

Variation of the above, uses Lipschitz constants automaticlly identified from the data. @strong{Should only be called after @i{ComputeLipschitz2()}}.

@subsection void  ComputeLipschitzInf(int dim,int K,double* X,double* Y)

Computes an (under)estimate of the Lipschitz constant in $l-\infty$-norm from the data. Bear in mind that @i{ComputeLipschitzInf} is a rather slow procedure @i{O(nK^2)} and should be avoided if there are other means to estimate the Lipschitz constant. The value(s) are kept in @i{LipConst} member variable.

@subsection void  ComputeLipschitz2(int dim,int K,double* X,double* Y)

Same as above, but uses Euclidean norm.

There are versions of the above methods with @i{Col} suffix in their names, these are used when the calling routine is written in another language, like Fortran, which stores the data columnwise (not row wise, like C). The only difference is that the matrix @i{X} is transposed.


@c ==============================================================================
@c third node

@c @node Examples, Index, Description of Library, Top
@node Examples
@chapter Examples

@cindex chapter, examples

There are several examples of the usage of @strong{lip} provided in the distribution. The best way to use @strong{lip} is to declare an instance of the class @i{STCInterpolant} and call its members directly. There are four basic steps: to supply the data, to supply the Lipschitz constant, to construct the interpolant, and to evaluate it at the desired point.

@menu
* Common Use Example::		Common usage.
* TNT Example::			Example uses TNT classes to make vector manipulation easier.
* Example Using SLipInt::	
@end menu


@c ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
@c third node subnode

@c @node Common Use Example, TNT Example, Examples, Examples
@node Common Use Example
@section Common Use Example
@cindex Examples, Common Use Example

@example
#include "interpol.h"
int dim=4;             // the dimension and size of the data set
int	npts=1000;
 
void main(int argc, char *argv[])@{
   double LipConst;   
   double *x, *XData, *YData;
// arrays to store the data
   x=(double*)malloc(dim*sizeof(double));
   XData=(double*)malloc(dim*npts*sizeof(double));
   YData=(double*)malloc(npts*sizeof(double)); 

   STCInterpolant LipInt;
   for(i=0;i<npts;i++) @{
     for(j=0;j<dim;j++) // generate random data in [0,3]^m
       XData[i*dim + j]=x[j]=random(3.0,0);  
     YData[i]=fun(x); // some function values
    @}
// suppy the data and eliminate repeated values
   LipInt.SetData(dim,npts, XData,YData,1);  
   LipConst=LipInt.DetermineLipschitz();
   LipInt.SetConstants();  // supply Lipschitz constant
   LipInt.Construct();     // construct the interpolant
   free(XData); free(YData); // may now destroy the data 

   double w,s,x1[10];  // reserve space for at least dim+1 components
   for(j=0;j<dim;j++) x1[j]=random(3.0,0); // some random x
   w=LipInt.Value(dim,x1); // calculate the value

// alternatively, pre-compute the slack variable
   for(s=0,j=0; j<dim; j++) s+=x1[j]; 
   x1[dim]= 1.0-s;
   w=LipInt.Value(dim+1,x1);         // calculate the value
   w=LipInt.ValueExplicit(dim+1,x1); // same using explicit method
   LipInt.FreeMemory();  // destroys the interpolant
@}
@end example

@c ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
@c third node subnode

@c @node TNT Example, Examples, Common Use Example, Examples
@node TNT Example
@section TNT Example
@cindex Examples, TNT Example

@example
// another example of usage with TNT library
#include "interpol.h"
#include "common.h"    // various types, such as dVec, dMat
int dim=4;             // the dimension and the data set
int	npts=1000;
double LipConst=10; 

void main(int argc, char *argv[])@{
// arrays to store the data
   dVec  x(dim), YData(npts); // these types defined in common.h
   dMat  XData(npts,dim);
   STCInterpolant LipInt;
   for(i=0;i<npts;i++) @{
     for(j=0;j<dim;j++) @{     // generate random data in [0,3]^dim
       XData[i][j]=x[j]=random(3.0,0); 
     @}
     YData[i]=fun(x.begin()); // some function values
   @}
// suppy the data 
   LipInt.SetData(dim,npts,&(XData[0][0]),YData.begin());  
   LipInt.SetConstants(LipConst);  // supply Lipschitz constant
   LipInt.Construct();             // construct the interpolant

   double s,w; 
   dVec x1(dim+1);   
   for(j=0;j<dim;j++) x[j]=random(3.0,0);  // some random x
   w=LipInt.ValueSlack(x);         // calculate the value of g(x)
   w=LipInt.Value(dim,x.begin());  // the same calculation

// alternatively, pre-compute the slack variable
   for(s=0,j=0; j<dim; j++) @{ x1[j]=random(3.0,0); s+=x1[j];@}
   x1[dim]= 1.0-s;
   w=LipInt.Value(x1);         // calculate the value
   w=LipInt.ValueExplicit(x1); // same using explicit method
@}
@end example

@c ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
@c third node subnode

@c @node TNT Example, Examples, Common Use Example, Examples
@node Example Using SLipInt
@section Example Using SLipInt
@cindex Examples, Example Using SLipInt

@example
// example of usage of SLipInt class
#include "slipint.h"
int dim=4;        // the dimension and size of the data set
int npts=1000;

void main(int argc, char *argv[])@{
   double LipConst=4;
   double *x, *XData, *YData;
// arrays to store the data
   x=(double*)malloc(dim*sizeof(double));
   XData=(double*)malloc(dim*npts*sizeof(double));
   YData=(double*)malloc(npts*sizeof(double));

   SlipInt LipInt;
   for(i=0;i<npts;i++) @{
     for(j=0;j<dim;j++) // generate random data in [0,3]^m
       XData[i*dim + j]=x[j]=random(3.0,0);
     YData[i]=fun(x); // some function values
    @}

   for(j=0;j<dim;j++) x[j]=random(3.0,0); // some random x

// calculate the value
   w=LipInt.ValueInf(dim,npts,x,XData, YData,LipConst);
// estimate Lipschitz constant
   LipInt.ComputeLipschitzInf(dim,npts,XData, YData);
// uses the computed Lipschitz constant
   w=LipInt.ValueInf(dim,npts,x,XData, YData);

// the same in Euclidean norm
   LipInt.ComputeLipschitz2(dim,npts,XData, YData);
// calculate the value
   w=LipInt.ValueInf(dim,npts,x,XData, YData);

   // Overwrite Lipschitz constant and calculate value
   w=LipInt.ValueInf(dim,npts,x,XData, YData,LipConst);

    free(XData); free(YData); free(x);
@}
@end example

@c ==============================================================================
@c here the index is declared as a node
@node Index
@unnumbered Index

@printindex cp

@bye