Near Optimal Points for Multivariate Interpolation
Scheda Progetto di ricerca
Condividi sui principali social network: Data inizio
 1 gennaio 2010
 Durata (mesi)
 12
 Dipartimenti
 Informatica
 Responsabili (o referenti locali)
 Bos Leonard Peter
Descrizione
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 nonlinear, 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
domains.
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 timedependent
parabolic and hyperbolic problems. We hope to apply such new approaches to relevant
applications, such as the numerical simulation of multiscale phenomena in
timedependent evolution processes of fluid flow.
established their asymptotic distribution in terms of complex potential theory  a true theoretical breakthrough. The problem is that to compute them requires a highly nonlinear, 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
domains.
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 timedependent
parabolic and hyperbolic problems. We hope to apply such new approaches to relevant
applications, such as the numerical simulation of multiscale phenomena in
timedependent evolution processes of fluid flow.
Enti finanziatori:
 Gruppo Nazionale Calcolo Scientifico

Finanziamento: assegnato e gestito da un ente esterno all'ateneo
Partecipanti al progetto
 Leonard Peter Bos
 Professore ordinario
 Marco Caliari
 Ricercatore
 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