Springe zum Hauptinhalt
Dr. Manuel Gräf
Quadraturformeln auf Mannigfaltigkeiten
Dr. Manuel Gräf 

Quadrature Rules on Manifolds

Quadrature rules on manifolds play an important role for numerical integration with many applications in science. A quadrature rule on a manifold \( \mathcal M \subset \mathbb R^n \) with \(M\) quadrature points \( \boldsymbol p_1,\dots, \boldsymbol p_M \in \mathcal M \) and associated quadrature weights \( w_1,\dots,w_M \in \mathbb R\) approximates the integral of a continuous function \(f:\mathcal M \to \mathbb R\) over the manifold \(\mathcal M\) by a finite sum, i.e., \[ \int_{\mathcal M} f(\boldsymbol x) \mathrm d \boldsymbol x \approx \sum_{i=1}^M w_i f(\boldsymbol p_i).\]

Of particular importance are Gauß-type quadrature rules which integrate exactly all multivariate polynomials of maximal degree \(N\), i.e., \begin{equation}\label{eq:gauss}\int_{\mathcal M} f(\boldsymbol x) \mathrm d \boldsymbol x = \sum_{i=1}^M w_i f(\boldsymbol p_i), \qquad f(\boldsymbol x)=\prod_{i=1}^n x_i^{\alpha_i}, \; \sum_{i=1}^n \alpha_i \le N. \end{equation} If additionally, all quadrature weights are equal, i.e., \(w_1=\dots=w_M= \frac1M \int_{\mathcal M} \mathrm d \boldsymbol x\), such quadrature rules are of Chebyshev-type. Gauß- and Chebyshev-type quadrature rules are called optimal if for prescribed degree of exactness \(N\) the identity \eqref{eq:gauss} is achieved for the minimal number \(M\) of quadrature points.

The tables below list several quadrature rules for the two-dimensional sphere \[\mathrm S^2 := \left\{ \boldsymbol x \in \mathbb R^3 \;:\; \| \boldsymbol x \|_2 = 1 \right\}\] and the three-dimensional rotation group \[\mathrm{SO(3)}:=\left\{ \boldsymbol R \in \mathbb R^{3\times3} \;:\; \boldsymbol R^\top \boldsymbol R = \boldsymbol I,\; \det \boldsymbol R = 1 \right\}.\] The algorithms for the computation of such quadrature rules together with the general mathematical framework can be found in the PhD Thesis [Gr13Diss].

Note that the set of quadrature points of a Chebyshev-type quadrature rule on the sphere \(\mathrm S^2\) with degree of exactness \(N\) is also known as spherical N-design. For further collections of spherical designs see the site of R. H. Hardin and N. J. A. Sloane under related websites.

Chebyshev-type Quadratures on \(\mathrm S^2\)

N M Group Coordinates
1 2 \(\overline{\mathrm C}_1\) File
2 4 \(\mathrm T\) File
3 6 \(\mathrm O\) File
5 12 \(\mathrm I\) File
7 24 \(\mathrm O\) File
8 36 \(\mathrm T\) File
9 48 \(\mathrm O\) File
10 60 \(\mathrm T\) File
11 70 \(\mathrm C_5\) File
12 84 \(\mathrm T\) File
13 94 \(\overline{\mathrm C}_1\) File
14 108 \(\mathrm T\) File
15 120 \(\mathrm O\) File
16 144 \(\mathrm T\) File
17 156 \(\mathrm T\) File
18 180 \(\mathrm T\) File
19 192 \(\mathrm C_3\) File
20 216 \(\mathrm T\) File
21 234 \(\mathrm C_3\) File
22 264 \(\mathrm O\) File
23 278 \(\mathrm C_3\) File
24 312 \(\mathrm O\) File
25 328 \(\overline{\mathrm C}_1\) File
26 360 \(\mathrm O\) File
27 380 \(\mathrm C_3\) File
28 420 \(\mathrm T\) File
29 432 \(\mathrm I\) File
30 480 \(\mathrm O\) File
31 498 \(\mathrm C_3\) File
32 540 \(\mathrm T\) File
33 564 \(\mathrm C_3\) File
34 612 \(\mathrm I\) File
35 632 \(\mathrm C_3\) File
36 684 \(\mathrm T\) File
37 706 \(\overline{\mathrm C}_1\) File
38 756 \(\mathrm T\) File
39 782 \(\mathrm C_3\) File
40 840 \(\mathrm O\) File
41 864 \(\mathrm C_3\) File
42 924 \(\mathrm T\) File
44 1008 \(\mathrm O\) File
46 1104 \(\mathrm O\) File
48 1200 \(\mathrm O\) File
50 1296 \(\mathrm O\) File
52 1404 \(\mathrm T\) File
54 1512 \(\mathrm I\) File
56 1620 \(\mathrm T\) File
58 1740 \(\mathrm T\) File
60 1860 \(\mathrm T\) File
62 1980 \(\mathrm T\) File
64 2112 \(\mathrm I\) File
66 2244 \(\mathrm T\) File
68 2376 \(\mathrm O\) File
70 2520 \(\mathrm O\) File
72 2664 \(\mathrm O\) File
74 2808 \(\mathrm O\) File
76 2964 \(\mathrm T\) File
78 3120 \(\mathrm O\) File
80 3276 \(\mathrm T\) File
82 3444 \(\mathrm T\) File
84 3612 \(\mathrm I\) File
86 3780 \(\mathrm T\) File
88 3960 \(\mathrm O\) File
90 4140 \(\mathrm T\) File
94 4512 \(\mathrm I\) File
98 4896 \(\mathrm O\) File
100 5100 \(\mathrm T\) File
114 6612 \(\mathrm I\) File
124 7812 \(\mathrm I\) File

Left-click and drag to rotate.

The following table contains some examples of computed Chebyshev-type quadrature rules (spherical N-designs) for high degree of exactness \(N\), and shows the practicability of the CG-method proposed in [GrPo11] for such highdimensional optimization problems. The text file for each point set consists of two columns which contain the spherical coordinates \((\varphi,\theta) \in [0,2\pi] \times [0,\pi) \) of the quadrature points \( \boldsymbol p := (\sin\theta \cos\varphi, \sin\theta \sin\varphi, \cos \theta)^{\top} \in \mathrm S^2 \).

(Non-Optimal) Chebyshev-type Quadratures on \(\mathrm S^2\) of high degree \(N\) (spherical N-designs)

N M (starting distribution) Error \(E_N\) \(\|\nabla E_N\|_2\) CG-Iterations Time
100 5200 (random) 9.9e-12 9.8e-14 4211 27min
100 5200 (spiral) 1.6e-10 9.7e-14 57235 7.5h
200 21000 (random) 4.1e-12 9.9e-14 2597 1h
200 21000 (spiral) 1.0e-9 9.4e-14 173675 3d
500 130000 (random) 1.0e-11 9.9e-14 5394 21h
1000 520000 (random) 2.7e-11 1.3e-13 18000 17d
1000 1002000 (random) 9.7e-12 9.8e-14 4286 5d

Putatively Optimal Quadrature Rules on the Rotation Group \(\mathrm{SO}(3)\)

The quadrature rules on the rotation group \(\mathrm{SO}(3)\) have been computed numerically by minimizing the worst-case quadrature error \[ E_N( \boldsymbol p_1, w_1, \dots, \boldsymbol p_M, w_M ) := \left( \sum_{n=0}^N \frac{2n+1}{8\pi^2} \sum_{k,l=-n}^n \left| \delta_{0,n} - \sum_{i=1}^M w_i \overline{D_{k,l}^n(\boldsymbol p_i)} \right|^2 \right)^{\frac12}\] over the product manifold \( (\mathrm{SO}(3) \times \mathbb R)^M \), where \(\delta_{0,n}\) is the Kronecker-delta and \(D_{k,l}^n:\mathrm{SO}(3) \to \mathbb C\) are the Wigner D-functions.

For the efficient evaluation of the worst-case quadrature error \(E_N\) in our optimization routine we utilized the nonequispaced fast Fourier transforms on the rotation group (NFSOFT), which are implemented in the NFFT-library.

Group Symmetries: Quadrature rules which are invariant under finite rotation groups \( \mathcal H \subset \mathrm{SO(3)}\) and \(\mathcal G := \mathcal G_1 \times \mathcal G_2 \subset \mathrm{SO(3)} \times \mathrm{SO(3)}\) may be written in the form \[ \sum_{i=1}^M w_i f(\boldsymbol p_i) = \sum_{i=1}^{M_{\mathrm{gen}}} w_i \sum_{\boldsymbol p \in \mathcal H \boldsymbol p_i} f(\boldsymbol p), \qquad M=\sum_{i=1}^{M_{\mathrm{gen}}} \left| \mathcal H \boldsymbol p_i \right|,\] and \[\sum_{i=1}^M w_i f(\boldsymbol p_i) = \sum_{i=1}^{M_{\mathrm{gen}}} w_i \sum_{\boldsymbol p \in (\mathcal G_1 \times \mathcal G_2) \boldsymbol p_i} f(\boldsymbol p),\qquad M= \sum_{i=1}^{M_{\mathrm{gen}}} \left|(\mathcal G_1 \times \mathcal G_2) \boldsymbol p_i\right|,\] where the first \(M_{\mathrm{gen}}\) quadrature points are the generators of the disjoint orbits \( \mathcal H \boldsymbol p_i := \{ \boldsymbol H \boldsymbol p_i \;:\; \boldsymbol H \in \mathcal H \} \subset \mathrm{SO(3)},; i=1,\dots, M_{\mathrm{gen}}\) and \( (\mathcal G_1 \times \mathcal G_2) \boldsymbol p_i := \{ \boldsymbol G \boldsymbol p_i \boldsymbol H^\top \;:\; \boldsymbol G \in \mathcal G_1, \boldsymbol H \in \mathcal G_2 \} \subset \mathrm{SO}(3),\; i=1,\dots,M_{\mathrm{gen}}\), respectively.

In particular we considered to compute optimal Gauß- and Chebyshev-type quadrature rules which are invariant under the tetrahedral group \(\mathrm T\ \times \mathrm C_1\), the octahedral group \(\mathrm O\times \mathrm C_1\), or the icosahedral group \(\mathrm I \times \mathrm C_1\).

Tables: The listed quadrature rules have a worst-case quadrature error \(E_N < 10^{-12}\). The columns indicate the degree of exactness \(N\), the number of quadrature points \(M\), the symmetry group \(\mathcal G\), and provide a link to the text files containing the Cartesian coordinates of the quadrature points/weights. For Gauß-type quadrature rules the ten Cartesian coordinates \((p_{11},p_{12},p_{13},p_{21},p_{22},p_{23},p_{31},p_{32},p_{33},w)\) of a quadrature point \(\boldsymbol p := (p_{ij})_{i,j=1}^3 \in \mathrm{SO(3)}\) with weight \(w\) are provided row-wise, whereas for Chebyshev-type quadrature rules the weight \(w\) is omitted. The two first numbers in the text files provide the number of the coordinates (10 or 9) and the number \(M\) of quadrature points.

Note that quadrature rules with degree of exactness \(N\) on the rotation group \(\mathrm{SO}(3)\) are in one-to-one correspondence to quadrature rules with degree of exactness \(2N+1\) and \(2M\) quadrature points on the three-dimensional sphere \( S^3 := \{ \boldsymbol x \in \mathbb R^4 \;:\; \|\boldsymbol x \|_2 = 1 \} \) which are invariant under the inversion group.

For illustration of the quadrature points we convert rotation matrices \( \boldsymbol R \in \mathrm{SO}(3) \) to unit quaternions \( \boldsymbol q := (q_0,q_1,q_2,q_3) \in \mathrm S^3 \) with real part \(q_0 \ge 0\) and project them stereographically by \( \boldsymbol q \mapsto \frac{1}{1+q_0}(q_1,q_2,q_3) \in \mathbb R^3 \) into the unit ball \( \{ \boldsymbol x \in \mathbb R^3 \;:\; \| \boldsymbol x \|_2 \le 1 \} \). Note that antipodal quaternions \( \pm \boldsymbol q \) correspond to exactly one rotation matrix, so that we plot for symmetry reasons two antipodal quaternions if \( q_0 = 0 \).

Gauß-type Quadratures on \(\mathrm{SO}(3)\)

N M Group Coordinates
1 4 \(\mathrm O \) File
2 11 \(\mathrm T\) File
3 23 \(\mathrm C_1\) File
4 43 \(\mathrm C_1\) File
5 60 \(\mathrm I \times \mathrm I\) File
6 116 \(\mathrm C_1\) File
7 168 \(\mathrm O \times \mathrm C_7\) File
8 240 \(\mathrm T \times \mathrm C_1\) File
9 300 \(\mathrm I \times \mathrm C_1\) File
11 504 \(\mathrm O \times \mathrm C_1\) File
14 960 \(\mathrm I \times \mathrm C_1\) File

Left-click and drag to rotate.
Color coding of the quadrature weights:

Note that the set of quadrature points of a Chebyshev-type quadrature rule on the rotation group \(\mathrm{SO}(3)\) with degree of exactness \(N\) can be considered as spherical (2N+1)-design on the sphere \(\mathrm S^3\).

Chebyshev-type Quadratures on \(\mathrm{SO}(3)\)

N M Group Coordinates
1 4 \(\mathrm O \) File
2 12 \(\mathrm T \times \mathrm T\) File
3 24 \(\mathrm O \times \mathrm O\) File
4 57 \(\mathrm C_1\) File
5 60 \(\mathrm I \times \mathrm I\) File
6 154 \(\mathrm C_1\) File
7 168 \(\mathrm O \times \mathrm C_7\) File
8 312 \(\mathrm T \times \mathrm C_2\) File
9 360 \(\mathrm I \times \mathrm C_3\) File
11 672 \(\mathrm O \times \mathrm C_2\) File
13 1176 \(\mathrm O \times \mathrm C_7\) File
14 1260 \(\mathrm I \times \mathrm C_7\) File
15 1776 \(\mathrm O \times \mathrm C_1\) File
17 2520 \(\mathrm I \times \mathrm C_1\) File
19 3300 \(\mathrm I \times \mathrm C_1\) File
23 5880 \(\mathrm I \times \mathrm C_7\) File

Left-click and drag to rotate.
Color coding of the distance from the origin:

C++ Software Library

We implemented the optimization algorithms in a C++ library for optimazation on Riemannian manifolds (LORM), which is Free Software licensed under the MPL2.

Publications

[Gr13Diss]
M. Gräf.
Efficient Algorithms for the computation of optimal quadrature points on Riemannian manifolds. (PDF)
PhD Thesis, Chemnitz University of Technology, Universitätsverlag Chemnitz, ISBN 978-3-941003-89-7, 2013.
[GrPo11]
M. Gräf and D. Potts.
On the computation of spherical designs by a new optimization approach based on fast spherical Fourier transforms. (PDF)
Numer. Math. 119, 699 - 724, 2011.

Selected References

[McL63]
A.D. McLaren.
Optimal numerical integration on a sphere. (JSTOR)
Math. Comput. 17, 361 - 383, 1963.
[Po94]
A.S. Popov.
Cubature formulae for a sphere invariant under cyclic rotation groups. (DOI)
Russian J. Numer. Anal. Math. Modelling. 9, 535 - 546, 1994.
[Po95]
A.S. Popov.
Cubature formulae for a sphere which are invariant with respect to the tetrahedral group.
Comput. Math. Math. Phys. 35, 369 - 374, 1995.
[Po98]
A.S. Popov.
Cubature formulas on a sphere that are invariant with respect to octahedron rotation groups.
Comput. Math. Math. Phys. 38, 30 - 37, 1998.
[So62]
S.L. Sobolev.
Cubature Formulas on the Sphere Invariant under Finite Groups of Rotations. (DOI)
Dokl. Akad. Nauk SSSR. 146, 310 - 313, 1962.