Explicit Formulas for Interpolatory Rules for $U_n$

If a particular choice of the $u_i (=\sqrt{\frac{i+\mu}{m+\mu n}})$ sequence is specified, then explicit formulas for the weights can be determined by repeated use of the formula (Stroud [7], p. 221)

\begin{displaymath}\int_{U_n}x_1^{k_1} x_2^{k_2} \cdots x_n^{k_n}d\sigma = 2\fr... ...amma(\frac{k_n+1}{2})} {\Gamma(\frac{\vert{\bf k}\vert+n}{2})}.\end{displaymath}

The most efficient interpolatory rules for $U_n$, in terms of fewest integrand values, come from the closed ($\mu = 0$) interpolation formulas. The closed rules have many points with several zero-valued components and therefore have fewer terms in the symmetric sums. The rest of this section will focus on the closed case, and will provide explicit weight formulas for this case.

Denote the surface content for $U_n$ by $V_n =\int_{U_n}d\sigma= 2\Gamma(\frac{1}{2})^n/\Gamma(\frac{n}{2}),$ and notice that $w_{\bf p}= w_{\bf q}$ if ${\bf q}$ is a permutation of ${\bf p}$, so it is sufficient to determine only those weights $w_{\bf p}$ for $Q^{(m,n)}(f)$ for which ${\bf p}$ is a distinct $n-$partition of $m$.

First consider the degree three ($m=1$) case. In this case, $u_0 = 0$ and $u_1 = 1$, and the interpolatory rule uses $2n$ integration rule points. The only distinct weight is

\begin{displaymath} w_{(1,0,\ldots,0)} =\int_{U_n}z_1^2d\sigma = 2\frac{\Gamma(\... ...a(\frac{1}{2})^{n-1}}{\Gamma(\frac{n+2}{2})} = \frac{1}{n}V_n. \end{displaymath}

This rule appears in the book by Stroud ([7], p. 294).

The degree five ($m=2$) case uses $u_0 = 0$, $u_1 = \frac{1}{\sqrt{2}}$ and $u_2 = 1$, and the interpolatory rule uses $2n+2n(n-1)= 2n^2$ integration rule points. The two distinct weights are

\begin{eqnarray*} w_{(2,0,\ldots,0)} & = &\int_{U_n} \frac{z_1^2(z_1^2-\frac{1}{... ...frac{1}{2}}{\frac{n+2}{2}\frac{n}{2}}V_n = \frac{4}{n(n+2)}V_n . \end{eqnarray*}



This rule also appears in Stroud's book ([7], p. 294, and in Mysovskih's book [5]).

The degree 7 ($m=3$) rule uses $u_0 = 0$, $u_1 = \frac{1}{\sqrt{3}}$, $u_2 = \frac{\sqrt{2}}{\sqrt{3}}$ and $u_3 = 1$, and the interpolatory rule uses $2n+4n(n-1)+4n(n-1)(n-2)/3$ points. Similar algebraic work shows that the three distinct weights are

\begin{eqnarray*} w_{(3,0,\ldots,0)}&=& \int_{U_n}\frac{z_1^2(z_1^2-\frac{1}{3})... ...z_2^2z_3^2} {\frac{1}{3}^3}d\sigma = \frac{27}{n(n+2)(n+4)}V_n . \end{eqnarray*}



This rule is apparently new.

Table 3.1 provides a summary of these formulas, and also includes formulas for the degree 9, 11, and 13 weights. The generator for a weight $w_{{\bf p}}$ is a point ${\bf z}_{\bf p}$ with $z_{p_1} \geq z_{p_2} \geq \ldots \geq z_{p_n} \geq 0$. The (fully symmetric) set of integration rule points for $w_{{\bf p}}$ is the set of all permutations of ${\bf z}_{\bf p}$ with all possible $\pm$ sign combinations. The rules for $2m+1>5$ are new. All formulas have been checked using a computer algebra system. To save space in the Table 3.1, all of the zero entries for each generator have been truncated, and the weight(s) given for each $m$ have been scaled by dividing by the common factor $\frac{V_n}{n(n+2)\cdots(n+2m-2)}$.
Table 3.1: Points and Weights for Fully Symmetric Interpolatory Rules for $U_n$
$m$ Truncated Generator Scaled Weight
1 $(1)$ $1$
  $(1)$ $4-n$
2 $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$ $4$
  $(1)$ $(2n^2-15n+43)/2$
3 $(\frac{\sqrt{2}}{\sqrt{3}},\frac{1}{\sqrt{3}})$ $9(5-n)/2$
  $(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})$ $27$
  $(1)$ $(4-n)(n^2-6n+40)$
  $(\frac{\sqrt{3}}{2},\frac{1}{2})$ $16(n^2-8n+36)/3$
4 $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$ $4(n-2)(n-12)$
  $(\frac{\sqrt{2}}{2},\frac{1}{2},\frac{1}{2})$ $32(6-n)$
  $(\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2})$ $256$
  $(1)$ $(8n^4-90n^3+995n^2-5300n+11947)/8$
  $(\frac{2}{\sqrt{5}},\frac{1}{\sqrt{5}})$ $-25(2n^3-19n^2+188n-631)/8$
  $(\frac{\sqrt{3}}{\sqrt{5}},\frac{\sqrt{2}}{\sqrt{5}})$ $-25(2n^3-39n^2+208n-441)/12$
5 $(\frac{\sqrt{3}}{\sqrt{5}},\frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}})$ $125(2n^2-17n+111)/6$
  $(\frac{\sqrt{2}}{\sqrt{5}},\frac{\sqrt{2}}{\sqrt{5}},\frac{1}{\sqrt{5}})$ $125(n^2-16n+33)/4$
  $(\frac{\sqrt{2}}{\sqrt{5}},\frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}}, \frac{1}{\sqrt{5}})$ $625(7-n)/2$
  $(\frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}}, \frac{1}{\sqrt{5}},\frac{1}{\sqrt{5}})$ $3125$
  $(1)$ $(4-n)(10n^4-71n^3+1733n^2-9442n+42420)/10$
  $(\frac{\sqrt{5}}{\sqrt{6}},\frac{1}{\sqrt{6}})$ $18(2n^4-19n^3+343n^2-2186n+6900)/5$
  $(\frac{\sqrt{2}}{\sqrt{3}},\frac{1}{\sqrt{3}})$ $9(n^4-23n^3+194n^2-1444n+1200)/2$
  $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$ $4(n^4-26n^3+257n^2-658n+4620)$
  $(\frac{\sqrt{2}}{\sqrt{3}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}})$ $-54(n^3-9n^2+134n-540)$
6 $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{6}})$ $-36(n^3-21n^2+134n-420)$
  $(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})$ $-27(n^3-30n^2+188n+48)$
  $(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}}, \frac{1}{\sqrt{6}})$ $432(n^2-9n+80)$
  $(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{6}}, \frac{1}{\sqrt{6}})$ $324(n^2-18n+44)$
  $(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}}, \frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}})$ $3888(8-n)$
  $(\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}}, \frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}})$ $46656$



Table 3.2 shows the required number of integrand values for the rules $Q^{(m,n)}$ for selected values of $m$ and $n$. For comparison, integrand value numbers are also provided for some other rule families. In the ``Xu'' rows, the numbers are given for the rules described by Xu [9]. These rules, given for odd $m$ only, require $2^n { n + \lfloor m/2\rfloor \choose \lfloor m/2\rfloor }$ integrand values for a degree $2m+1$ rule. In spite of the rapidly increasing $2^n$ factor, these rules often require fewer integrand values than the $Q^{(m,n)}$ rules. For large $n$, the $Q^{(m,n)}$ rules require $O(\frac{(2n)^m}{m!})$ integrand values compared to $O(\frac{2^n n^{\lfloor m/2\rfloor}}{\lfloor m/2 \rfloor!})$ integrand values for the Xu rules. For a fixed $m$ and sufficiently large $n$, the $Q^{(m,n)}$ rules will require fewer points.



Table 3.2: Numbers of Integrand Values Needed for Spherical Surface Rules
Degree Rule $n$: 3 4 5 6 7 8 9 10
3 $Q^{(1,n)}$ 6 8 10 12 14 16 18 20
  Xu 8 16 32 64 128 256 512 1024
5 $Q^{(2,n)}$ 18 24 50 72 98 128 162 200
  Mys. 20 30 42 56 72 90 110 132
7 $Q^{(3,n)}$ 38 88 90 292 462 688 978 1340
  Mys. 52 90 142 210 296 402 530 682
  Mys. 26 64 130 232 378 576 834 1160
  Stroud 26 48 82 136 226 384 674 1224
  Xu 32 80 192 448 1024 2304 5120 11264
9 $Q^{(4,n)}$ 66 184 450 432 1666 2816 4482 6800
  Mys. 38 104 250 532 1022 1808 2994 4700
11 $Q^{(5,n)}$ 102 360 1002 2364 2702 9424 16722 28004
  Keast 70 168 362 740 1486 2992 6098 12604
  Xu 80 240 672 1792 4608 11520 28160 67584
13 $Q^{(6,n)}$ 146 600 1970 5336 12642 18048 53154 97880
15 $Q^{(7,n)}$ 198 952 3530 10836 28814 68464 116370 299660
  Xu 160 560 1792 5376 15360 42240 112640 292864
17 $Q^{(8,n)}$ 258 1208 5890 17376 59906 157184 374274 715040
19 $Q^{(9,n)}$ 326 1992 9290 35436 115598 332688 864146 2060980
  Xu 280 1120 4032 13440 42240 126720 366080 1025024
21 $Q^{(10,n)}$ 402 2712 14002 58728 209762 658048 1854882 4780008



The rows labelled with ``Mys.'' give the number of integrand values needed for some rules listed in the book by Mysovskih [5]. For degree 7, there are numbers for two general rules listed: the first rule uses $n(n+1) + (n+1)(n+2)(n+3)/3$ integrand values and the second uses $2n(2n^2-3n+4)/3$ integrand values. For degree 7, the row labelled ``Stroud'' gives numbers ($2^n + 2n^2$) for rules listed in the book by Stroud [7], p. 295. For degree 11, the row labelled ``Keast'' gives numbers ( $2n+2^n(n+1)+4n(n-1)(n+1)/3$) for a rule derived by Keast [4], p. 418. The Mysovskih and Stroud books also list a number of other rules for specific values of the rule degree and $n$ (mostly for low rule degree and small $n$) that are not included in Table 3.2.

A practical issue when using an integration rule is stability. A standard measure of the stability of an integration rule is the sum of the absolute values of the rule weights. This is a worst-case roundoff error magnification factor. Denote this stability factor for a fully symmetric interpolatory rule $Q^{(m,n)}$ by

\begin{displaymath} C^{(m,n)}= \sum_{\vert{\bf p}\vert=m}N_{\bf p}^{(m,n)}\vert w_{\bf p}\vert/V_n, \end{displaymath}

where $N_{\bf p}^{(m,n)}$ is the number of points needed for the sum $f\{{\bf z}_{{\bf p}}\}$. A completely stable rule has $C = 1$, but there is no general method known for constructing efficient rules for $I(f)$ with $C = 1$. In Table 3.3 the approximate stability factors for the rules $Q^{(m,n)}$ are shown. Although these stability factors increase slowly with $m$ and $n$, it can be seen that there will not be a significant loss of precision through roundoff error magnification when these rules are used.

Table 3.3: Approximate $Q^{(m,n)}$ Rule Stability Factors  
$m$ $n$: 2 3 4 5 6 7 8 9 10
1 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
2 1.0 1.0 1.0 1.3 1.5 1.7 1.8 1.9 2.0
3 1.0 1.0 1.0 1.0 1.6 2.1 2.6 3.0 3.4
4 1.0 1.2 1.4 1.6 1.7 2.4 3.3 4.1 5.0
5 1.0 1.1 1.5 2.1 2.8 3.3 4.4 5.7 7.1
6 1.4 1.9 2.3 3.0 4.3 5.5 6.7 8.4 10.4
7 1.1 1.8 3.0 4.5 6.5 8.8 11.1 13.4 16.2
8 2.7 3.7 4.8 7.1 10.2 13.9 18.0 22.3 26.7
9 1.5 4.1 7.6 11.9 17.2 23.1 29.9 37.3 45.3
10 6.3 8.6 12.9 20.4 29.5 39.7 51.0 63.6 77.6



2005-09-06