Rob Womersley

Last updated 17-Oct-2007

• Extremal Systems
• Interpolatory Cubature
• Eigenvalues and Condition Numbers
• Lagrangian norms, Lebesgue constant
• Geometric Properties
• Notes on point sets
• Tables of Points and Values
• References
• Acknowledgements

• Unit sphere S² in R³ has area |S²| = 4 p.
• The space P_n of polynomials of degree at most n on S² has dimension
  d_n = (n+1)².

• Extremal Systems are sets of d_n points x_j on S² 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 d_n = (n+1)².
• There are many local maxima, often with objective values close to the global maximum.
• Here the reproducing kernel basis functions
  g_j(x),   j = 1,...,d_n
  and associated Gram matrix G
  G_ij = g_j(x_i)
  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 (d_n!  /  |S²|^d_n).

• An upper bound on log det G is
  d_n log (d_n / |S²|).

• 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.

• Cubature rule sum_{j = 1 to dn}   w_j f(x_j) 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 = |S²|,
  e^T w = |S²|
  .
• The average, or equal, cubature weight is
  w_avg = |S²| / d_n

• Scaled cubature weights are w_i / w_avg,
• smallest   w_min / w_avg <= 1,
• largest     w_max / w_avg >= 1.
• Conjecture: For extremal systems the cubature weights are always positive.
• Extremal points provide good starting points for numerically finding spherical designs of degree n with d_n = (n+1)² points for which
  w_i = w_avg   for   i = 1,...,d_n.

• Many systems of d_n = (n+1)² points on S² 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
  cond₁(G) = || G ||₁   || G^-1 ||₁.

• As G_ii = d_n / |S²|,
  trace(G) = sum of eigenvalues of G = d_n² / |S²|.

• l_min(G) = smallest eigenvalue.
  l_avg(G) = average eigenvalue = d_n / |S²|,
  l_max(G) = largest eigenvalue.
• 2-norm condition number
  cond₂(G) = l_max(G) / l_min(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.

• Lagranians
  L_j(x) = e_j^T G^-1 g(x)   j = 1,...,d_n
  for x in S².
• Lebesgue constant = ||L_n|| = interpolation operator norm (as a map from C(S²) to C(S²)) is
  max_{x in S²}   ||L(x)||₁.

• Reimer upper bound on the Lebesgue constant is
  R = (n+1) sqrt(l_avg / l_min).

• All calculated extremal point systems have Lebesgue constant closer to (n+1) than the known upper bound of (n+1)².
• Lagrangian 2-norm,
  max_{x in S²}   || L(x) ||₂
  and infinity norm,
  max_{x in S²}   max_{j = 1,...,dn} | L_j(x) |,
  are calculated by finding global maximum over S². As L_j(x_j) = 1 and L_i(x_j) = 0 for i not equal to j, the infinity norm of the Lagrangians is >= 1, and should be 1 for extremal systems.

• The geodesic distance between two points x and y on the unit sphere S² is dist(x,y) = cos^-1(x^T 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 = max_{x in S²}   min_j=1,...,dn   dist(x, x_j).
  This is also the covering radius for covering the sphere by spherical caps.
• Potential energy is sum over all distinct points x_i and x_j of 1 / ||x_i - x_j||₂
• Cui and Freeden discrepancy is

  D = (1/(2 d_n sqrt(p)))
        [ sum_j=1,...,dn sum_k=1,...,dn
        (1 - 2 log(1 + sqrt((1 - x_j^T x_k)/2)) ]^1/2.

• Volume of the convex hull of a set of points on S² 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.

• 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 current set of extremal points is in md.tar.gz (61 Mb compressed, 155 Mb uncompressed!). The main differences are for degrees 80 and above.  Last updated 17-Oct-2007

Tables of values

• Points, determinant, cubature weights
• Eigenvalues and Lagrangian norms
• Geometrical properties

• R. S. Womersley and I. H. Sloan, How good can polynomial interpolation on the sphere be? Advances in Computational Mathematics 14 (2001) 195--226.
• I. H. Sloan and R. S. Womersley, Extremal systems of points and numerical integration on the sphere, Advances in Computational Mathematics 21 (2004) 107--125. extremal.pdf

Acknowlegements

The use of the high performance computing facilities of

• Matrix the School of Mathematics AMD Opteron Linux computational cluster
• The School of Mathematics Condor pool
• ac3, The Australian Center for Advanced Computing and Communication;
• APAC, Australian Partnership for Advanced Computing;