Near Optimal Points for Multivariate Interpolation

Starting date
January 1, 2010
Duration (months)
Computer Science
Managers or local contacts
Bos Leonard Peter

Fekete points for polynomial interpolation are points that maximize the Vandermonde determinant (in any polynomial basis) on a given compact set, and thus ensure that the corresponding Lebesgue constant is bounded by the dimension of the polynomial space. These point sets are important since they always give near optimal points for polynomial interpolation. They have been much studied and recently Berman and Boucksom have
established their asymptotic distribution in terms of complex potential theory -- a true theoretical breakthrough. The problem is that to compute them requires a highly non-linear, unstable, computationally expensive numerical optimization. We have developed a greedy algorithm, that computes multivariate {\it Approximate} Fekete points by extracting maximum volume submatrices from rectangular Vandermonde matrices on suitable discretization meshes. It works for arbitrary geometries and uses only a basic (optimized) tool of numerical linear algebra, i.e., the QR factorization, and hence is computationally feasible, and indeed, highly efficient.

Recently, it has come to our attention, that another basic tool, the LU
decomposition with pivoting applied to the Vandermonde matrix, can be used to extract a set of multivariate
{\it Approximate} Leja points from a suitable discrete mesh that replaces the underlying domain of interest. The cost of this latter method seems to be about one third of the computational cost for Approximate Fekete points,
but comes at the expense of having somewhat higher Lebesgue constants. One of our goals in this project
is to understand better the trade off between the computational cost of producing these points sets versus the
accuracy of the resulting interpolant. We would like to emphasize that these techniques, for the first time, provide
computationally feasible methods for producing good polynomial interpolants on general multivariate
There is a strong connection with the theory of admissible meshes for multivariate polynomial approximation, recently developed by J.P. Calvi and N. Levenberg. Approximate Fekete and Leja points in polygons and polyhedra, as well as in nonstandard geometries, could give new tools for numerical cubature and for numerical solution of PDEs by spectral and high order methods.

With regard to RBFs this project aims at the development, analysis and implementation of stable,
accurate, and efficient adaptive approximation algorithms by using radial
kernel functions. The resulting computational methods rely on adaptive concepts
for meshfree multivariate approximation from scattered data, where special
emphasis is placed on (near) optimal distributions of the sample points.
This in turn leads to novel concepts for the construction of meshfree particle
methods, as they are used for the numerical solution of time-dependent
parabolic and hyperbolic problems. We hope to apply such new approaches to relevant
applications, such as the numerical simulation of multiscale phenomena in
time-dependent evolution processes of fluid flow.


Gruppo Nazionale Calcolo Scientifico
Funds: assigned and managed by an external body

Project participants

Leonard Peter Bos
Research Assistants
Marco Caliari
Full Professor

Collaboratori esterni

Marco Vianello
Padova Matematica Pura ed Applicata
Stefano De Marchi
Padova Matematica Pura ed Applicata
Alvise Sommariva
Universita` di Padova Dipartimento di Matematica Pura ed Applicata


Research facilities