# 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., $$\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.$$ 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].

### Putatively Optimal Quadrature Rules on the Sphere $$\mathrm S^2$$

The quadrature rules on the sphere $$\mathrm S^2$$ 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 \sum_{k=-n}^n \left| \frac{1}{\sqrt{4\pi}} \delta_{0,n} - \sum_{i=1}^M w_i \overline{Y_n^k(\boldsymbol p_i)} \right|^2 \right)^{\frac12}$ over the product manifold $$(\mathrm S^2 \times \mathbb R)^M$$, where $$\delta_{0,n}$$ is the Kronecker-delta and $$Y_n^k:\mathrm S^2 \to \mathbb C$$ are the orthonormalized spherical harmonics.

For the efficient evaluation of the worst-case quadrature error $$E_N$$ in our optimization routine we utilized the nonequispaced fast spherical Fourier transforms (NFSFT), which are implemented inthe NFFT-library.

Group Symmetries: Quadrature rules on the sphere $$\mathrm S^2$$which are invariant under finite rotation groups $$\mathcal G \subset \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 G \boldsymbol p_i} f(\boldsymbol p),\qquad M= \sum_{i=1}^{M_{\mathrm{gen}}} \left|\mathcal G \boldsymbol p_i\right|,$ where the first $$M_{\mathrm{gen}}$$ quadrature points are the generators of the disjoint orbits $$\mathcal G \boldsymbol p_i := \{ \boldsymbol G \boldsymbol p_i \;:\; \boldsymbol G \in \mathcal G\} \subset \mathrm S^2,\; i=1,\dots,M_{\mathrm{gen}}.$$

The idea of taking group symmetries for quadrature rules into account dates back to Sobolev [So62] and McLaren [McL63]. In particular we considered to compute optimal Gauß- and Chebyshev-type quadrature rules which are invariant under the inversion group $$\overline{\mathrm C}_1$$, the cyclic group $$\mathrm C_k \; (k=1,\dots,5)$$, the tetrahedral group $$\mathrm T$$, the octahedral group $$\mathrm O$$, or the icosahedral group $$\mathrm I$$.

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 four Cartesian coordinates $$(p_1,p_2,p_3,w)$$ of a quadrature point $$\boldsymbol p:=(p_1,p_2,p_3)^\top \in \mathrm S^2$$ with weight $$w$$ are provided row-wise, whereas for Chebyshev-type quadrature rules the weight $$w$$ is omitted. The two first numbers in the dat-files provide the number of the coordinates (4 or 3) and the number $$M$$ of quadrature points.

The accuracy of the computed quadrature rules can keep up with algebraically constructed quadrature rules. In fact, we recomputed with a precision of 11 digits the well-know Gauß-type quadrature rules with degree of exactness $$N = 1,2,3,5$$ and the one constructed in [Po94] with $$N=4,6,7,17$$, in [Po95] with $$N=8$$, in [Po98] with $$N=11$$, and in [McL63] with $$N=9,14$$.

#### Gauß-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 4 10 $$\mathrm C_4$$ File 5 12 $$\mathrm I$$ File 6 18 $$\mathrm C_4$$ File 7 22 $$\mathrm C_5$$ File 8 28 $$\mathrm T$$ File 9 32 $$\mathrm I$$ File 10 42 $$\mathrm C_4$$ File 11 48 $$\mathrm O$$ File 12 58 $$\mathrm C_4$$ File 13 64 $$\overline{\mathrm C}_1$$ File 14 72 $$\mathrm I$$ File 15 82 $$\mathrm C_5$$ File 16 98 $$\mathrm C_4$$ File 17 104 $$\mathrm C_3$$ File 18 122 $$\mathrm C_4$$ File 19 130 $$\overline{\mathrm C}_1$$ File 20 148 $$\mathrm T$$ File 21 156 $$\mathrm C_3$$ File 22 178 $$\mathrm C_4$$ File 23 186 $$\mathrm C_3$$ File 24 210 $$\mathrm C_4$$ File 25 220 $$\overline{\mathrm C}_1$$ File 26 244 $$\mathrm T$$ File 27 254 $$\mathrm C_3$$ File 28 282 $$\mathrm C_4$$ File 29 292 $$\mathrm C_5$$ File 30 322 $$\mathrm C_4$$ File 32 364 $$\mathrm T$$ File 34 410 $$\mathrm C_4$$ File 35 422 $$\mathrm C_5$$ File 36 458 $$\mathrm C_4$$ File 37 472 $$\mathrm C_5$$ File 38 508 $$\mathrm T$$ File 39 522 $$\mathrm C_5$$ File 44 672 $$\mathrm I$$ 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 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$$

N M 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_{21},p_{31},p_{12},p_{22},p_{32},p_{13},p_{23},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 optimization 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.