Computing Fekete and Lebesgue points: Simplex, square, disk

We have computed point sets with maximal absolute value of the Vandermonde determinant (Fekete points) or minimal Lebesgue constant (Lebesgue points) on three basic bidimensional compact sets: the simplex, the square, and the disk. Using routines of the Matlab Optimization Toolbox, we have obtained some of the best bivariate interpolation sets known so far.     

A Lobatto interpolation grid over the triangle

^** Email: m.blyth{at}uea.ac.uk^*** Email: cpozrikidis{at}ucsd.edu A sequence of increasingly refined interpolation grids overthe triangle is proposed, with the goal of achieving uniformconvergence and ensuring high interpolation accuracy. The numberof interpolation nodes, N, corresponds to a complete mth-orderpolynomial expansion with respect to the triangle barycentriccoordinates, which arises by the horizontal truncation of thePascal triangle. The proposed grid is generated by deployingLobatto interpolation nodes along the three edges of the triangle,and then computing interior nodes by averaged intersectionsto achieve three-fold rotational symmetry. Numerical computationsshow that the Lebesgue constant and interpolation accuracy ofthe proposed grid compares favorably with those of the best-knowngrids consisting of the Fekete points. Integration weights correspondingto the set of Lobatto triangle base points are tabulated.     

Are the eigenvalues of preconditioned banded symmetric Toeplitz matrices known in almost closed form?

The problem of computing oscillatory integrals with general oscillators is considered. We employ a Filon-type method, where the interpolation basis functions are chosen in such a way that the moments are in terms of elementary functions and the oscillator only. This allows us to evaluate the moments rapidly and easily without needing to engage hypergeometric functions. The proposed basis functions form a Chebyshev set for any oscillator function even if it has some stationary points in the integration interval. This property enables us to employ the Filon-type method without needing any information about the stationary points if any. Interpolation by the proposed basis functions at the Fekete points (which are known as nearly optimal interpolation points), when combined with the idea of splines, leads to a reliable convergent method for computing the oscillatory integrals. Our numerical experiments show that the proposed method is more efficient than the earlier ones with the same advantages.     

A New Quasi-Monte Carlo Technique Based on Nonnegative Least Squares and Approximate Fekete Points

The computation of integrals in higher dimensions and on general domains, when no explicit cubature rules are known, can be "easily" addressed by means of the quasi-Monte Carlo method. The method, simple in its formulation, becomes computationally inefficient when the space dimension is growing and the integration domain is particularly complex. In this paper we present two new approaches to the quasi-Monte Carlo method for cubature based on nonnegative least squares and approximate Fekete points. The main idea is to use less points and especially good points for solving the system of the moments. Good points are here intended as points with good interpolation properties, due to the strict connection between interpolation and cubature. Numerical experiments show that, in average, just a tenth of the points should be used to maintain the same approximation order of the quasi-Monte Carlo method. The method has been satisfactorily applied to 2- and 3-dimensional problems on quite complex domains.     

Fekete points and convergence towards equilibrium measures on complex manifolds

Building on [BB1] we prove a general criterion for convergence of (possibly singular) Bergman measures towards pluripotential-theoretic equilibrium measures on complex manifolds. The criterion may be formulated in terms of the growth properties of the unit-balls of certain norms on holomorphic sections, or equivalently as an asymptotic minimization property for generalized Donaldson L-functionals. Our result settles in particular a well-known conjecture in pluripotential theory concerning the equidistribution of Fekete points and it gives the convergence of Bergman measures towards the equilibrium measure for Bernstein-Markov measures. Applications to interpolation of holomorphic sections are also discussed.     

Tensor product Gauss-Lobatto points are Fekete points for the cube

Tensor products of Gauss-Lobatto quadrature points are frequently used as collocation points in spectral element methods. Unfortunately, it is not known if Gauss-Lobatto points exist in non-tensor-product domains like the simplex. In this work, we show that the -dimensional tensor-product of Gauss-Lobatto quadrature points are also Fekete points. This suggests a way to generalize spectral methods based on Gauss-Lobatto points to non-tensor-product domains, since Fekete points are known to exist and have been computed in the triangle and tetrahedron. In one dimension this result was proved by Fejér in 1932, but the extension to higher dimensions in non-trivial.

     

Kernel-based interpolation at approximate Fekete points

Numerical Algorithms - We construct approximate Fekete point sets for kernel-based interpolation by maximising the determinant of a kernel Gram matrix obtained via truncation of an orthonormal...     

Weighted Fejér constants and Fekete sets

We indicate the connections among the Fekete set, the zeros of orthogonal polynomials, 1(w)-normal point systems, and the nodes of an interpolatory process which is called stable and the most economical, via the Fejér constants. Finally the convergence of a weighted Grünwald interpolation is proved.     

Zur approximation des transfiniten durchmessers bei bis auf ecken analytischen geschlossenen jordankurven

LetC be a closed Jordan curve in the complex plane and letf(z)=dz+a ₀+a ₁ z ^?1+… be the analytic function mapping |z|>1 schlicht onto the exterior ofC (d>0 is the transfinite diameter ofC). Similar to the Fekete points a point system will be defined calledextremal points. One can use the Fekete points or the extremal points to approximated. The author has proved [3] that in the case of an analytic closed Jordan curve the approximation ofd by means of extremal points is much better than the approximation ofd by the use of Fekete points. Here we show how to approximated by means of extremal points in the case of a piecewise analytic, closed Jordan curve possessing corners of openingαπ (0<α<2).     

Weakly Admissible Meshes and Discrete Extremal Sets

We present a brief survey on (Weakly) Admissible Meshes and corresponding Discrete Extremal Sets, namely Approximate Fekete Points and Discrete Leja Points. These provide new computational tools for polynomial least squares and interpolation on multidimensional compact sets, with different applications such as numerical cubature, digital filtering, spectral and high-order methods for PDEs.     

Potential and Discrepancy Estimates for Weighted Extremal Points

We derive estimates for Green and logarithmic potentials of measures associated with extremal points. These results are applied to obtain discrepancy estimates for weighted Fekete and Tsuji points on quasiconformal arcs or curves. September 21, 1998. Date revised: July 6, 1999. Date accepted: September 22, 1999.     

The numerical stability of evaluation schemes for polynomials based on the lagrange interpolation form

For evaluation schemes based on the Lagrangian form of a polynomial with degreen, a rigorous error analysis is performed, taking into account that data, computation and even the nodes of interpolation might be perturbed by round-off. The error norm of the scheme is betweenn ² andn ²+(3n+7) _n , where _n denotes the Lebesgue constant belonging to the nodes. Hence, the error norm is of least possible orderO(n ²) if, for instance, the nodes are chosen to be the Chebyshev points or the Fekete points.     

On the Asymptotics of Fekete-Type Points for Univariate Radial Basis Interpolation

Suppose that K ^d is compact and that we are given a function fC(K) together with distinct points x_iK, 1in. Radial basis interpolation consists of choosing a fixed (basis) function g : ⁺→ and looking for a linear combination of the translates g(|x−x_j|) which interpolates f at the given points. Specifically, we look for coefficients c_j such that has the property that F(x_i)=f(x_i), 1in. The Fekete-type points of this process are those for which the associated interpolation matrix [g(|x_i−x_j|)]_1i,jn has determinant as large as possible (in absolute value). In this work, we show that, in the univariate case, for a broad class of functions g, among all point sequences which are (strongly) asymptotically distributed according to a weight function, the equally spaced points give the asymptotically largest determinant. This gives strong evidence that the Fekete points themselves are indeed asymptotically equally spaced.     

Equidistribution of points via energy

We study the asymptotic equidistribution of points with discrete energy close to Robin’s constant of a compact set in the plane. Our main tools are the energy estimates from potential theory. We also consider the quantitative aspects of this equidistribution. Applications include estimates of growth for the Fekete and Leja polynomials associated with large classes of compact sets, convergence rates of the discrete energy approximations to Robin’s constant, and problems on the means of zeros of polynomials with integer coefficients.     

Discrete weighted least-squares method for the Poisson and biharmonic problems on domains with smooth boundary

In this article a discrete weighted least-squares method for the numerical solution of elliptic partial differential equations exhibiting smooth solution is presented. It is shown how to create well-conditioned matrices of the resulting system of linear equations using algebraic polynomials, carefully selected matching points and weight factors. Two simple algorithms generating suitable matching points, the Chebyshev matching points for standard two-dimensional domains and the approximate Fekete points of Sommariva and Vianello for general domains, are described. The efficiency of the presented method is demonstrated by solving the Poisson and biharmonic problems with the homogeneous Dirichlet boundary conditions defined on circular and annular domains using basis functions in the form satisfying and in the form not satisfying the prescribed boundary conditions.     

Lagrange interpolation and finite element superconvergence

We consider the finite element approximation of the Laplacian operator with the homogeneous Dirichlet boundary condition, and study the corresponding Lagrange interpolation in the context of finite element superconvergence. For d‐dimensional Q_k‐type elements with d ≥ 1 and k ≥ 1, we prove that the interpolation points must be the Lobatto points if the Lagrange interpolation and the finite element solution are superclose in H¹ norm. For d‐dimensional P_k‐type elements, we consider the standard Lagrange interpolation—the Lagrange interpolation with interpolation points being the principle lattice points of simplicial elements. We prove for d ≥ 2 and k ≥ d + 1 that such interpolation and the finite element solution are not superclose in both H¹ and L² norms and that not all such interpolation points are superconvergence points for the finite element approximation. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 33–59, 2004.     

Harmonic Properties of the Logarithmic Potential and the Computability of Elliptic Fekete Points

We investigate the properties of the function sending each N-tuple of points to minus the logarithm of the product of their mutual distances. We prove that, as a function defined on the product of N spheres, this function is subharmonic, and indeed its (Riemannian) Laplacian is constant. We also prove a mean value equality and an upper bound on the derivative of the function. We use these results to get sharp upper bounds for the precision needed to describe an approximation to elliptic Fekete points (in the sense demanded by Smale’s 7th problem). We also conclude that Smale’s 7th problem has solutions given by rational spherical points of bounded (small) bit length, proving that there exists an exponential running time algorithm which solves it on the Turing machine model.     

On polynomial interpolation of two variables

Polynomial interpolation of two variables based on points that are located on multiple circles is studied. First, the poisedness of a Birkhoff interpolation on points that are located on several concentric circles is established. Second, using a factorization method, the poisedness of a Hermite interpolation based on points located on various circles, not necessarily concentric, is established. Even in the case of Lagrange interpolation, this gives many new sets of poised interpolation points.     

A Point Balance Algorithm for the Spherical Code Problem

The Spherical Code (SC) problem has many important applications in such fields as physics, molecular biology, signal transmission, chemistry, engineering and mathematics. This paper presents a bilevel optimization formulation of the SC problem. Based on this formulation, the concept of balanced spherical code is introduced and a new approach, the Point Balance Algorithm (PBA), is presented to search for a 1-balanced spherical code. Since an optimal solution of the SC problem (an extremal spherical code) must be a 1-balanced spherical code, PBA can be applied easily to search for an extremal spherical code. In addition, given a certain criterion, PBA can generate efficiently an approximate optimal spherical code on a sphere in the n-dimensional space ⁿ. Some implementation issues of PBA are discussed and putative global optimal solutions of the Fekete problem in 3, 4 and 5-dimensional space are also reported. Finally, an open question about the geometry of Fekete points on the unit sphere in the 3-dimensional space is posed.     

The Multivariate Integer Chebyshev Problem

The multivariate integer Chebyshev problem is to find polynomials with integer coefficients that minimize the supremum norm over a compact set in ℂ ^d . We study this problem on general sets but devote special attention to product sets such as cube and polydisk. We also establish a multivariate analog of the Hilbert–Fekete upper bound for the integer Chebyshev constant, which depends on the dimension of space. In the case of single-variable polynomials in the complex plane, our estimate coincides with the Hilbert–Fekete result.