Extremal (Maximum Determinant)
points on the sphere S2

Rob Womersley

Last updated 17-Oct-2007

Contents

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.
log det G

(Upper bound - log det G)/ dn

infinity norm of gradient of log det G

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|,

    eT w = |S2|

    .
  • The average, or equal, cubature weight is

    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.
  • Extremal points provide good starting points for numerically finding spherical designs of degree n with dn = (n+1)2 points for which

    wi = wavg   for   i = 1,...,dn.

Scaled minimum and maximum cubature weights Worst case cubature error in Sobolev space H<sup>3/2</sup>

Eigenvalues and condition numbers
  • Many systems of dn = (n+1)2 points on S2 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.
Eigenvalues of G 1-norm condition number of G

Lagrangian norms, Lebesgue constant
  • Lagranians

    Lj(x) = ejT G-1 g(x)   j = 1,...,dn

    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   || L(x) ||2

    and infinity norm,

    maxx in S2   maxj = 1,...,dn | 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.
Lagrangian 1-norm (Lebesgue constant) Lagrangian 2-norm

Geometric Properties
  • The geodesic distance 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...
Voronoi cells

Minimum angle between points

Mesh norm (covering radius) Mesh ratio (covering radius/packing radius)

Notes on point sets

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 xj, yj, and zj cartesian coordinates in [-1, 1], and the cubature weight wj for that point. The number of rows is equal to the number of points.
  • All points are on the unit sphere so should have xj2 + yj2 + zj2 = 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

References

  • 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;
is gratefully acknowledged.


Last updated 17-Oct-2007   |   Page contact: R.Womersley (AT) unsw.edu.au   |   Top