Rob Womersley

Last updated 03-Jun-2020

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

• Maximum Determinant 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.
• As is typical of problems for optimizing points on the sphere, there are many many local optima.
• The only guaranteed global maximum is for n = 1, d_n = 4 where the regular tetrahedrom has G = (4/|S²|) I which achives the upper bound.

• 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 maximum determinant systems the cubature weights are always positive.
• Maximum determinant 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.
• Maximum determinant 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²|.

• λ_min(G) = smallest eigenvalue.
  λ_avg(G) = average eigenvalue = d_n / |S²|,
  λ_max(G) = largest eigenvalue.
• 2-norm condition number
  cond₂(G) = λ_max(G) / λ_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.

• The Lagranian functions ℓ_j(x), j = 1,...,d_n satisfy
  ℓ_j(x_j) = 1 and ℓ_i(x_j) = 0 for i ≠ j

• The Lagrangians are, for x ∈ S², given by
  ℓ_j(x) = e_j^T G^-1 g(x)   j = 1,...,d_n.

• Lebesgue constant = ||L_n|| = interpolation operator norm (as a map from C(S²) to C(S²)) is
  max_{x ∈ S²}   ||ℓ(x)||₁.

• Reimer upper bound on the Lebesgue constant is
  R = (n+1) sqrt(λ_avg / λ_min).

• All calculated maximum determinant point systems have Lebesgue constant closer to (n+1) than the known upper bound of (n+1)².
• Lagrangian 2-norm,
  max_{x ∈ S²}   || ℓ(x) ||₂
  and infinity norm,
  max_{x ∈ S²}   max_{j = 1,...,dn} | ℓ_j(x) |,
  are calculated by finding global maximum over S². The infinity norm of the Lagrangians is ≥ 1, and should be 1 for maximum determinant 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 maximum determinant systems the minimum distance between points is known to be asymptotially greater than π/(2n). Numerically the minimum angle is closer to π/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 (Riesz s = 1 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(π)))
        [ 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 π / 3 = 4.18879...
• The Voronoi cell V_j for point x_j, j = 1,...,d_n is
  V_j = {x ∈ S² : dist(x, x_j) ≤ dist(x, x_i), i ≠ j}

• If there are only pentagonal (5 sides), hexagonal (6 sides) and heptagonal (7 sides) Voronoi cells then Euler's formuula implies the number of pentagons is equal to the number of heptagons + 12.

Caveat: All points are only approximate local maximizers of det(G). Attempts to find good local 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 zip file of the current set of all MaxDet points is in MD03-Jun-2020.zip (104 Mb compressed).  Last updated 03-Jun-2020
• Point sets for a specific degree are available from the table: Points, determinant, cubature weights.

Tables of values

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

• I. H. Sloan and R. S. Womersley, 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
• J. Marzo and J. Ortega-Cerdà, Equidistribution of Fekete Points on the Sphere, Constructive Approximation 32 (2010) 513--521. https://link.springer.com/article/10.1007/s00365-009-9051-5
• S.V. Borodochov, D. P. Hardin and E. B. Saff, Discrete Energy on Rectifiable Sets, Springer Monographs in Mathematics (2019). https://www.springer.com/gp/book/9780387848075

Acknowlegements

The use of the following high performance computing facilities is gratefully acknowledged:

• 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, the Australian Partnership for Advanced Computing;
• The Linux computational cluster Katana supported by UNSW Sydney.
• Research Technology Services at UNSW Sydney also supported this project with compute resources from the National Computational Infrastructure (NCI).