MUPORAIA research project

MUPORAIA: Multivariate Polynomial and Rational Interpolation and Approximation (01-01-2014 - 31-12-2017)

Proposed research situation

In the project summary we wrote that we want to compute “good points” and “good representations” for certain geometries, compact sets, in the multivariate space of variables and corresponding to certain function spaces, e.g., polynomial functions or rational functions. The points are called “good” because interpolation in these points gives an approximant that approximates the original function not only very well in the neighbourhood of the interpolation points but in the whole compact set. The representation is called “good” when it can be computed and manipulated in an efficient and accurate way.

For the problem of approximating univariate functions by polynomials in a typical compact set on the real line, i.e., an interval, the theory as well as the corresponding software is welldeveloped. We refer to Chebfun, a Matlab toolbox, whose theoretical foundation and several of its applications are described in the book by Trefethen. If one transforms an arbitrary compact interval to the inverval [-1,1], it turns out that different types of Chebyshev points are not only “good points” but that the computation of the corresponding interpolant can be performed very efficiently (and accurately) by using the Fast Fourier Transform (FFT). The zero sets of other orthogonal polynomials, e.g., Legendre polynomials, have similar approximating properties but they can not be represented explicitly and the corresponding approximant can not be computed so efficiently. For univariate rational interpolation, the so-called rational Chebyshev points are nearly optimal on the interval [-1,1].

For the univariate polynomial interpolant, one of the “good representations” is a barycentric interpolation formula. This representation can be evaluated in O(n) flops where n is the degree of the interpolating polynomial and it has excellent numerical stability properties. This representation can also be used for rational functions as shown by Berrut et al.

For multivariate polynomial and rational interpolation and approximation, the problem setting is much more complicated because the geometry can take much more forms than in the univariate case and also the degree structure of the polynomial and rational functions can be more general. For a theoretical overview, we refer the interested reader to the literature. One of the criteria to determine the location of “good points” for polynomial approximation is locating those points within the geometry such that the Lebesgue constant, i.e., the maximum of the Lebesgue function, is as small as possible within the geometry. The Padua points seem to be the first known example of nearly-optimal points for total degree polynomial interpolation in two variables, with a Lebesgue constant increasing like log square of the degree. The corresponding geometry is a square or rectangle (or another derived form). These Padua points have been discovered and extensively studied by the Padova-Verona research group on “Constructive Approximation and Applications” (CAA-group) and their collaborators. For other geometries there are no explicit representations known for (near-)optimal points with respect to minimizing the Lebesgue constant. The CAA-group has developed Matlab software to compute such near-optimal points for several other geometries, e.g., the disk, the simplex, not only for minimizing the Lebesgue constant but also for minimizing the corresponding Vandermonde determinant (Fekete-points). Initializing the software with reasonably “good points”, it can also be used to derive point sets with a smaller Lebesgue constant than the initial set. A disadvantage of this software is that it is rather slow and that it is limited to a relatively small number of points because of the ill-conditioning of the corresponding Vandermonde matrices. On March 4, an extension of Chebfun will be made available to work with functions in two variables defined on a rectangle. In our approach we want to work with functions on more general geometries with corresponding “good points” and “good representations”.

Concerning “good representations” for multivariate polynomial and rational functions, it is still not clear how to generalize the barycentric representation for univariate functions to the multivariate case. This approach gives a rational interpolant but it is not clear if the minimal degree interpolant can always be represented in this way and, if this is possible, how the parameters of the representation have to be determined to get this minimal degree interpolant.

Proposed research:

The aim of this project is the theoretical study and efficient computation and use of “good points” and “good representations” to approximate multivariate functions on general geometries with polynomial and rational approximants. This aim can be divided and specialised in several subaims as follows:

• The theory of “good points”, i.e., (nearly) optimal points according to a certain criterion to measure the goodness of these sets of points, will be extended from simpler geometries like, e.g., the unit cube, the unit ball, the simplex, . . . , to more complicated geometries like, e.g., the L-shape, a connected compact set but having “holes” in it, nonconvex sets, . . . . We will also generalize the results for the space of polynomial functions to the space of rational functions (with prescribed poles).
• The algorithms to compute these “good points” in an accurate and efficient way will be developed and implemented as part of a Matlab-toolbox. This toolbox will be written such that not only a specialist but also a non-expert will be able to use this toolbox.
• Once the “good points” are known, the theory and algorithms have to be developed and implemented to compute a “good representation” of the corresponding interpolant, a polynomial or rational function. It will be important that this interpolant can be computed, evaluated, differentiated, integrated in an efficient and numerically stable way, not only for low degrees but also for much more complicated polynomial or rational functions.
• Besides “good points” for interpolation, we will also investigate “good points” for least squares approximation.
• Several applications of “good points” and “good representations” will be studied, e.g., numerical integration, solution of partial differential equations.