LibLip - reliable interpolation of multivariate scattered data

Welcome to the home of LibLip . This page describes a method of fast and reliable interpolation of scattered data in many variables, using Lipschitz-continuous interpolant. It also describes the programming library LibLip which implements this method.

Version 2.0 of the library is now available (from June 3, 2006)
NEW! Matlab and Maple toolboxes available (from Dec 30, 2006)

LibLip interpolates scattered multivariate data with a Lipschitz function.

Downloads: Unix/Linux, Windows, Updated Dec 30,2006: Matlb toolbox, Maple toolbox.

Methods of interpolation of multivariate scattered data are scarce. See a review paper by P.Alfeld. The programming library Lip implements a new method by G. Beliakov, which relies on building reliable lower and upper approximations of Lipschitz functions [1,2]. If we assume that the function that we want to interpolate is Lipschitz-continuous, we can provide tight bounds on its values at any point, in the worse case scenario. Thus we obtain the interpolant, which approximates the unknown Lipschitz function f best in the worst case scenatio. This translates into reliable learning of f, something that other methods cannot do (the error of approximation of most other methods can be infinitely large, depending on what f generated the data). The details of the method are found here.

Lipschitz condition implies that the rate of change of the function is bounded:
|f(x)-f(y)|<M||x-y||.
It is easily interpreted as the largest slope of the function f. f needs not be differentiable.

The interpolant based on the Lipschitz properties of the function is piecewise linear, it possesses many useful properties, and it is shown that it is the best possible approximation to f in the worst case scenario. The value of the interpolant depends on the data points in the immediate neigbourhood of the point in question, and in this sense, the method is similar to the natural neighbour interpolation.

There are two methods of construction and evaluation of the interpolant. The explicit method processes all data points to find the neighbours of the point in question. It does not require any preprocessing, but the evaluation of the interpolant has linear complexity O(K) in terms of the number of data.

"Fast" method requires substantial preprocessing in the case of more than 3-4 variables, but then it provides O(log K) evaluation time, and thus is suitable for very large data sets (K of order of 500000) and modest dimension (n=1-4). For larger dimension, explicit method becomes practically more efficient. The class library Lip implements both fast and explicit methods.
The new version of LibLip also implements methods of monotone interpolation and smoothing, interpolation subject to other constraints, as well as a method of locally Lipschitz interpolation. For details see the manual.
A detailed description of the library is found here. This file also provides some benchmark data - time needed to construct and evaluate the interpolant for data sets of varying size and dimension.

Lip library is implemented in C++ language. The user needs to supply the data and the Lipschitz constant using a simple syntaxis, and then call the methods of construction and evaluation provided in Lip. The Lipschitz constant can be also found automaically. Here is an example of the user's code:

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

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

   LipInt.SetData(dim,npts, XData,YData);  	// suppy the data 
   LipConst=10; 				// Lipschitz constant
   LipInt.SetConstants(LipConst);  		// supply Lipschitz constant
   LipInt.Construct();     			// construct the interpolant 

   for(j=0;j<dim;j++) x[j]=random(3.0,0); 	// choose some random x
   w=LipInt.Value(dim,x); 			// calculate the value of the interpolant
   w=LipInt.ValueExplicit(dim,x); 		// same using explicit method
}

Unix/Linux distribution

The source code for Lip library is available here: liblip-2.0.0.tar.gz
The user needs to install the library and compile the library files (running lipinstall script on unix) . The installation script will install the static and shared libraries, documentation and the example programs.

Windows distribution

Updated 24.12.2006
The source code and compiled dlls are available here liblip2_dll.zip
The user needs to unzip the distribution file into a separate derectory. Both the source files, static library dliblip.lib and DLL dliblip.dll files will be installed (there are several versions, depending on code genration and whether GLPK or LPSOLVE are used).
The easiest way to use Lip is to copy dliblip.dll file to a common directory specified on your path (like c:\windows), copy dliblip.lib file to a directory it can be easily located by your compiler, and follow the example in exampledll.cpp. The user can use either C/C++ language, or call the dll from another language, like VB or Fortran.

The precompiled static versions of the libraries are available here liblip2static.zip

Important note

LibLip depends on the libraries GLPK or LPSOLVE, which implement various linear programming techniques. These libraries are available from http://www.gnu.org/software/glpk/glpk.html and http://groups.yahoo.com/group/lp_solve/. Please see the manual how to proceed. Windows precompiled dll already contains GLPK or LPSOLVE.

References

[1] Beliakov, G., Interpolation of Lipschitz functions. J. of Comp. and Applied Mathematics, 2006. 196: pp.20-44. Preprint
[2] Beliakov, G., Monotonicity preserving approximation of multivariate scattered data. BIT, 2005. 45: p. 653-677.Preprint
[3] Beliakov, G., A review of applications of the Cutting Angle methods, in Continuous Optimization, A. Rubinov and V. Jeyakumar, Editors. 2005, Springer: New York. p. 209-248.Preprint

LibLip is copyright subject to GNU Lesser General Public License conditions (see the distribution files for details).

Please send your comments/requests to the author at gleb@deakin.edu.au