Contents

1. Notation
2. Point Sets
   • Extremal (maximum determiant) points (updated 16-Jan-2003)
   • Minimum energy points (updated 24-Jan-2003)
   • Extremal spherical designs (updated xx-Jan-2003)
3. Mesh Norms
4. Interpolation Norms
5. Condition numbers and eigenvalues
6. Uniform errors in approximations
7. Cubature weights
8. Related publications
9. Related web sites

Notation

• n = degree of interpolating polynomial.
• P_n = space of all spherical polynomials of degree at most n.
• d_n = dimension of P_n
• d_n = number of interpolation points in a fundamental system for P_n
• d_n = (n+1)² for S²
• A system of d_n points is a fundamental system if and only if the only polynomial of P_n which is zero at all points is the zero polynomial.
• G = d_n by d_n  Gram matrix from reproducing kernel basis;
• G_ij = G_n(< x_i, x_j >) where G_n(z) is the reproducing kernel for P_n.
• G_ij depends only on the angle between the points x_i and x_j, so G is symmetric.
• G is positive semi-definite for any set of d_n points.
• G is positive definite if and only if {x_j, j = 1,...,d_n} is a fundamental system.
• G_jj = d_n / |S²| for j = 1,...,d_n and any point set.
• The vector of reproducing kernel polynomials is g : S² -> R^d_n where
  g_j(x) = G_n ( < x_j, x>) for j = 1,...,d_n and x in S².
• Associated with each point x_j of a fundamental system is the Lagrange polynomial L_j in P_n, determined by L_j(x_j) = 1 for j = 1,...,d_n  and   L_j(x_i) = 0, for i not equal to j
  • For a fundametnal system L_j(x) = (G^-1  g(x))_j.
  • The vector of Lagrangians is l(x) = G^-1  g(x).
• The norms of the vector of Lagrangians of interest are
  • the 1-norm || l (x) ||₁,
  • the 2-norm || l (x) ||₂,
  • the max-norm || l (x) ||_infinity.
• ||L_n|| = norm of the interpolation operator L_n as a map from C(S²) to  C(S²),
• ||L_n|| = max_{x in S²}   || l(x) ||₁.
• The eigenvalues of the Gram matrix G are
  • l_min = smallest eigenvalue of the matrix G,
  • l_avg = average eigenvalue of the matrix G = trace G / d_n  = d_n / |S²| =  d_n / (4 p),
  • l_max = largest eigenvalue of the matrix G
  • The 2-norm condition number of G is l_max / l_min
•  R = sqrt(d_n) sqrt(l_avg / l_min)  =  Reimer's upper bound on ||L_n||,
• Cubature weights w_j, j = 1,...,d_n, such that the rule
  Q(f) = sum_{j=1}^{d_n}   w_j f(x_j)

  is exact for all polynomials in P_n are given by the solution of

  Gw = e, where e is the vector of all ones.
  • As cubature rule is exact for constant polynomials the average cubature weight is w_avg = e^T w / d_n = |S²| / d_n.
  • For comparison it is easier to consider the scaled cubature weights w_j / w_avg.
• Spherical n-designs are equal weight cubature rules with m <= d_n points which are exact for all polynomials of degree less than or equal to n.
  • Fundamental systems with w_j / w_avg = 1 for j = 1,...,d_n are spherical n-desigins.
• Mesh norm h = max_{x in S²} min_{j = 1,...,d_n} dist(x, x_j)  where
  • Geodesic distance between x and y in S² is dist(x, y) = cos^-1(<x, x_j>),
  • The mesh norm is the covering radius for convering S² with spherical caps of radius h centered at each point x_j for j = 1,...,d_n.
  • The mesh norm function is  min_{j=1,...,d_n}   cos^-1 (< x, x_j>) for x in S²
• Potential energy (PE) is
  sum_{i=1}^d_n   sum(j=i+1}^d_n  1/|| x_i - x_j ||₂
  • || x_i - x_j ||₂² = 2(1 - < x_i, x_j >)
• The minimum distance (angle) between the points x_j, j = 1,...,d_n
  min_{i, j = 1,...,d_n} cos^-1 (< x_i, x_j >)

  is twice the packing radius for spherical caps centred at each of the points.

Click on the following links to obtain images or tables of different point sets. Point sets obtained by the four criteria below have very different characteristics, the differences being generally not understood theoretically.

• Each set of interpolation points has d_n points x_j, j = 1,...,d_n on S².
• Point sets are normalized so that the first point is at the north pole (theta = 0, phi irrelevant) and the second point is on the prime meridian (phi = 0). <

Caveat: All point sets are only approximate local optimizers of their respective criteria.

Recent point sets

For these point sets attempts to find global optima have been made, but with decreasing reliability as the degree n of the polynomials increases.

• Extremal (maximum determiant) points
• Minimum energy points
• Extremal spherical designs

Point Sets from the "How Good ... " paper

Code	Points, Data and Images	Criterion
ME	Minimum Energy points	Minimize the potential energy (from Fliege and Maier)
MD	Maximum Determinant points	Maximizime det(G)
EV	Eigenvalue points	Maximize lmin, the smallest eigenvalue of G
MN	Minimum Norm points	Minimize ||Ln||, the interpolation operator norm

Mesh norms

The mesh norm gives a measure of how geometrically well distirbuted the points on the sphere are.

  Interpolation norms

The norm of the ploynomial interpolation operator, as a map from C(S²) to C(S²), gives a bound on the quality of the polynomial interpolant.

Points with small mesh norm do not necessarily correspond to points with low interpolation norm.

Condition number and smallest eigenvalues

Some point sets, like the minimal energy points sets of Fliege and Maier and the generlaized spiral points, have interpolation matrices which are very close to singular, making it numerically difficult to accuratley solve the linear system for the interpolation weights. A very small eigenvalue also makes the Reimers bound R on the Lebesgue constant is large. Plot of the condition number, largest and smallest eigenvalues for the ME, EV, MD and MN points

Uniform error of approximation

To illustrate the effect that a poor choice of interpolation points can have, the interpolants and the errors in the interpolation are plotted for the minimum energy (ME) and minimum norm (MN) points for the cosine cap.

Cubature weights

Cubature weights w so that the rule Q(f) is exact for all polynomials of degree at most n are given by G*w = e. These weights may not be positive for any given point set. However the maximum determinant point set numerically has positive weights. As the weights sum to give the surface area of the sphere, the plots show the minimum and maximum of the scaled weights w_j / w_avg.

Related publications by Ian Sloan and Robert Womersley

• Ian H. Sloan and Robert S. Womersley, Extremal systems of points and numerical integration on the Sphere, Advances in Computational Mathematics 21 (2004) 102-125.
  Applied Mathematics Report AMR15-01, School of Mathematics, University of New South Wales. Gzipped postscript extremal.ps.gz (339 Kb), PDF: extremal.pdf (354 Kb),
• Ian H. Sloan and Robert S. Womersley, Good approximation on the sphere, with application to geodesy and the scattering of sound, Jounral of Computational and Applied Mathematics 149 (2002) 227-238.
• Robert S. Womersley and Ian H. Sloan, How Good can Polynomial Interpolation on the Sphere be?, Advances in Computational Mathematics 14 (2001) 195-226.
• Robert S. Womersley, A continuous minimax problem for calculating minimum norm polynomial interpolation points on the sphere, ANZIAM Journal 42 (E), (2000) C1536--C1557.
• Ian H. Sloan and Robert S. Womersley, The search for good polynomial interpolation points on the sphere, in: D. F. Griffiths and G. A. Watson eds., Numerical Analysis 1999 CRC Press LLC (2000) 211-230.
• Ian H. Sloan and Robert S. Womersley, The Uniform Error of Hyperinterpolation on the Sphere, in: K. Jetter, W. Haussmann and M. Reimer eds. Advances in Multivariate Approximation, (1999) 289-306. Postscript version hyperr.ps (456Kb), Gzipped postscript version hyperr.ps.gz (200Kb)
• Ian H. Sloan and Robert S. Womersley, Constructive Approximation on the Sphere, Journal of Approximation Theory, 103, 1 (2000) 91-118.
• Ian H. Sloan, Interpolation and hyperinterpolation on the sphere, in: W. Haussmann, K. Jetter and M. Reimer eds., Multivariate Approximation: Recent Trends and Results, Akademie Verlag GmbH, Berlin (1997) 255-268.
• Ian H. Sloan, Polynomial interpolation and hyperinterpolation over general regions, Journal of Approximation Theory 83 (1995) 238-254.

Related web sites

• Visualization of 1089 Extremal points on the sphere, Ben Simons (Sydney VisLab) and Rob Womersley.
• Neil Sloane's home page, and the Spherical Designs page by R. H. Hardin and N. J. A. Sloane.
• Ed Saff's home page, in particular the Sphere Points (Equal Area points) page and references.
• Willi Freeden's Geomathematics Group, at the University of Kaiserslautern.
• Dave Rusin, Sphere FAQ.
• J. Fliege and U. Maier, Integration nodes for the sphere.
• M. Neubauer et al, Potential minimizing configurations of points on the sphere.