Extremal (Maximum Determinant)
points on the sphere S²

Extremal Systems

Unit sphere S2 in R3 has area |S2| = 4 p. The space Pn of polynomials of degree at most n on S2 has dimension dn = (n+1)2. Extremal systems are sets of dn points xj on S2 that maximize the determinant of a basis matrix. The points are independent of the choice of basis. For a global maximum, it follows that the Lebesgue constant is at most dn = (n+1)2. There are many local maxima, often with objective values close to the global maximum. Here the reproducing kernel basis functions gj(x), j = 1,...,dn and associated Gram matrix G: Gij = gj(xi) are used. G is symmetric positive semidefinite and for any fundamental system of points nonsingular (hence positive definite). A lower bound on log det G is log (dn!  /  |S2|dn). An upper bound on log det G is dn log (dn / |S2|). For n >= 3 the upper bound cannot be achieved. The norm of the gradient with respect to a spherical parametrization of the points gives an idea how close it is to a stationary point (gradient = 0). Keep in mind the size of the objective when thinking about how small it is numerically possible to get this.

Interpolatory Cubature

Cubature rule sumj = 1 to dn   wj f(xj) approximates the integral of f(x) over the surface of the unit sphere. Cubature weights w such that the cubature rule is exact for all polynomials of degree <= n satsify G w = e, e = vector of 1s. Cubature rule exact for p(x) = 1 implies that the sum of cubature weights = |S2|. Average, or equal, cubature weight wavg = |S2| / dn Scaled cubature weights are wi / wavg , smallest   wmin / wavg <= 1, largest   wmax / wavg >= 1. Conjecture: For extremal systems the cubature weights are always positive.

Eigenvalues and condition numbers

Many systems have very large condition numbers, making solving a linear system for interpolation or cubature weights unreliable. Extremal systems have excellent conditioning, making the cubature weiights reliable 1-norm condition number cond1(G) = || G ||1   || G-1 ||1. As Gii = dn / |S2|, trace(G) = sum of eigenvalues of G = dn2 / |S2|. lmin(G) = smallest eigenvalue. lavg(G) = average eigenvalue = dn / |S2|, lmax(G) = largest eigenvalue. 2-norm condition number cond2(G) = lmax(G) / lmin(G) The 2-norm condition number is generally an order of magnitude less than the 1-norm condition number Maximizing the product of the eigenvalues, while keeping the sum of the eigenvalues fixed, tries to make all eigenvalues equal, improving the condition number.

Lagrangian norms

Lagranians Lj(x) = ejT G-1 g(x) for x in S2. Lebesgue constant = ||Ln|| = interpolation operator norm (as a map from C(S2) to C(S2)) is maxx in S2 ||L(x)||1. Reimer upper bound on the Lebesgue constant is R = (n+1) sqrt(lavg / lmin). All calculated extremal point systems have Lebesgue constant closer to (n+1) than the known upper bound of (n+1)2. Lagrangian 2-norm, maxx in S2 || Lj(x) ||2 and infinity norm, maxx in S2 maxj | Lj(x) |, are calculated by finding global maximum over S2. As Lj(xj) = 1 and Li(xj) = 0 for i not equal to j, the infinity norm of the Lagrangians is >= 1, and should be 1 for extremal systems.

Geometrical properties

The geodesic dsitance between two points x and y on the unit sphere S2 is dist(x,y) = cos-1(xT y). The sphere packing problem is to place m points on a sphere to as to maximize the the minimal distance, or minimal separation, between them. For extremal systems the minimum distance between points is known to be asymptotially greater than p/(2n). Numerically the minimum angle is closer to p/n. Mesh norm is h = maxx in S2   minj=1,...,dn   dist(x, xj). This is also the covering radius for covering the sphere by spherical caps. Potential energy is sum over all distinct points xi and xj of 1 / ||xi - xj||2 Cui and Freeden discrepancy is D = (1/(2 dn sqrt(p)))       [ sumj=1,...,dn sumk=1,...,dn       (1 - 2 log(1 + sqrt((1 - xjT xk)/2)) ]1/2. Volume of the convex hull of a set of points on S2 is always less than the volume of the unit sphere = 4 p / 3 = 4.18879...

Caveat: All points are only approximate local maximizers of det(G). Attempts to find global extrema have been made, with decreasing reliability as n increases.

Notes on point sets

• For each point set the text file has four items per row: the x_j, y_j, and z_j cartesian coordinates in [-1, 1], and the cubature weight w_j for that point. The number of rows is equal to the number of points.
• All points are on the unit sphere so should have x_j² + y_j² + z_j² = 1.
• The file names have three components: point set, degree, number of points.
• Background programs to search for global extrema are run. This web page and tables are updated when a better system is found.
• A gzipped tar file of the complete set of extremal points is in md.tar.gz (12 Mb!).  Last updated 16-Jan-2003

References

• R. S. Womersley and I. H. Sloan, How good can polynomial interpolation on the sphere be? Advances in Computational Mathematics 23 (2001) 195--226.
• I. H. Sloan and R. S. Womersley, Extremal systems of points and numerical integration on the sphere, Applied Mathematics Report AMR15-01, University of New South Wales. extremal.pdf

Acknowlegements

• ac3, The Australian Center for Advanced Computing and Communication;
• APAC, Australian Partnership for Advanced Computing;