FLINT3.7.0-dev
Algorithm

Legendre functions and orthogonal polynomials

The Legendre polynomials Pn(x)P_n(x), and more generally the classical orthogonal polynomials (Jacobi, Gegenbauer, Chebyshev, Laguerre, Hermite), are terminating hypergeometric series, for example

Pn(x)=2F1(−n,n+1;1;1−x2),Pn(a,b)(z)=(a+1)nn! 2F1(−n,n+a+b+1;a+1;1−z2).P_n(x) = {}_2F_1\left(-n, n+1; 1; \frac{1-x}{2}\right), \qquad P_n^{(a,b)}(z) = \frac{(a+1)_n}{n!}\,{}_2F_1\left(-n,n+a+b+1;a+1;\frac{1-z}{2}\right).

For integer degree they can be evaluated directly as polynomials, but for large nn this is slow and numerically unstable: the coefficients grow exponentially while ∣Pn(x)∣≤1|P_n(x)| \le 1 on [−1,1][-1,1]. FLINT has a dedicated algorithm for Pn(x)P_n(x) with real xx and word-size nn, which also gives the nodes and weights of Gauss–Legendre quadrature; the other functions use the general 2F1{}_2F_1 and 1F1{}_1F_1 code with a few direct methods for integer degrees.

Legendre polynomials#

The algorithm of arb_hypgeom_legendre_p_ui is that of Johansson and Mezzarobba [JM2018]. It computes Pn(x)P_n(x) and Pn′(x)P_n'(x) together for real xx, and by Pn(−x)=(−1)nPn(x)P_n(-x) = (-1)^n P_n(x) only x≥0x \ge 0 is needed. Four expansions are available.

  • Expansion at x=1x = 1 (arb_hypgeom_legendre_p_ui_one):

    Pn(x)=∑k=0n(nk)(n+kk)(x−12)k.P_n(x) = \sum_{k=0}^{n} \binom{n}{k}\binom{n+k}{k} \left(\frac{x-1}{2}\right)^k.

    The terms decrease quickly when ∣1−x∣|1 - x| is small, and the series can be truncated after K<n+1K < n+1 terms with a bound for the remainder.

  • Expansion at x=0x = 0 (arb_hypgeom_legendre_p_ui_zero): for even n=2mn = 2m,

    P2m(x)=(−1)m(1/2)mm! 2F1(−m,m+12;12;x2),P_{2m}(x) = (-1)^m \frac{(1/2)_m}{m!}\, {}_2F_1\left(-m, m + \tfrac12; \tfrac12; x^2\right),

    and an analogous formula with x 2F1(−m,m+32;32;x2)x\,{}_2F_1(-m, m + \frac32; \frac32; x^2) for odd nn. The terms decrease when ∣x∣|x| is small.

  • Asymptotic expansion (arb_hypgeom_legendre_p_ui_asymp): with x=cos⁡θx = \cos\theta, 0<θ<π0 < \theta < \pi, the Stieltjes series

    Pn(cos⁡θ)=4πΓ(n+1)Γ(n+32)∑k=0K−1(12)k2k! (n+32)kcos⁡((n+k+12)θ−(k+12)π2)(2sin⁡θ)k+1/2+RK,P_n(\cos\theta) = \frac{4}{\pi} \frac{\Gamma(n+1)}{\Gamma(n+\frac32)} \sum_{k=0}^{K-1} \frac{(\frac12)_k^2}{k!\,(n+\frac32)_k} \frac{\cos\left((n + k + \tfrac12)\theta - (k+\tfrac12)\tfrac{\pi}{2}\right)}{(2\sin\theta)^{k+1/2}} + R_K,

    summed as the real part of a complex series in (1−icot⁡θ)(1 - i\cot\theta), with the explicit bound ∣RK∣≤0.50795 K! n!2K(n+K)! yKny|R_K| \le 0.50795\, \frac{K!\, n!}{2^K (n+K)!\, y^K \sqrt{ny}}, y=sin⁡θy = \sin\theta, which follows from the analysis of Bogaert, Michiels and Fostier [Bog2012]. The number of terms needed decreases as nn grows; for nn much larger than the precision a handful of terms suffice, independently of nn.

  • Recurrence (arb_hypgeom_legendre_p_ui_rec): the three-term recurrence (k+1)Pk+1=(2k+1)xPk−kPk−1(k+1)P_{k+1} = (2k+1)xP_k - kP_{k-1}, scaled by its denominators: uk=k! Pku_k = k!\,P_k satisfies uk+1=(2k+1)xuk−k2uk−1u_{k+1} = (2k+1)x u_k - k^2 u_{k-1} without division. The values are kept as limb vectors of fixed length with a common exponent (the low limb is dropped as they grow), each step is a high product flint_mpn_mulhigh_n by xx and two operations by words, and the result is divided by n!n! at the end. The rounding errors are bounded a priori with the error-propagation estimate of [JM2018, Proposition 5], which uses only ∣Pk(x)∣≤1|P_k(x)| \le 1. It is stable on (−1,1)(-1, 1), costs O(n)O(n) short-product operations, and is the fastest method for moderate nn and precision.

arb_hypgeom_legendre_p_ui selects the method from estimates of the cost of each expansion: the number of terms, the precision lost to cancellation in the series at 0 and at 1 (whose terms can be much larger than Pn(x)P_n(x)), and the size of the error term of the asymptotic expansion. The recurrence is used for nn below a few hundred at low precision, unless xx is very close to 0 or 1; for ∣x∣>1|x| > 1 only the expansion at 1 is used (with an early stop if it converges quickly). The working precision is raised by the estimated cancellation, and for inexact xx the function evaluates at the midpoint and adds the error propagated from the radius rr, bounded by r⋅max⁡∣Pn′∣r \cdot \max|P_n'| and r⋅max⁡∣Pn′′∣r \cdot \max|P_n''| on the ball (arb_hypgeom_legendre_p_ui_deriv_bound, which uses ∣Pn′(x)∣≤min⁡((n+1)2/2, cn (1−x2)−3/4)|P_n'(x)| \le \min((n+1)^2/2,\ c\sqrt{n}\,(1 - x^2)^{-3/4}) and ∣Pn′′(x)∣≤min⁡((n+1)4/8, 2c n3/2(1−x2)−5/4)|P_n''(x)| \le \min((n+1)^4/8,\ 2c\, n^{3/2}(1-x^2)^{-5/4}) for ∣x∣≤1|x| \le 1, with c≥23/2/πc \ge 2^{3/2}/\sqrt\pi).

Gauss–Legendre nodes and weights#

The roots 1>x0>⋯>xn−1>−11 > x_0 > \cdots > x_{n-1} > -1 of PnP_n and the weights wk=2/((1−xk2)Pn′(xk)2)w_k = 2/((1-x_k^2)P_n'(x_k)^2) are computed by arb_hypgeom_legendre_p_ui_root. By the symmetry xn−1−k=−xkx_{n-1-k} = -x_k, wn−1−k=wkw_{n-1-k} = w_k only the positive roots, 0≤k<⌊n/2⌋0 \le k < \lfloor n/2 \rfloor, are computed; the middle root of odd nn is 00. There are three methods, chosen by nn and the precision pp:

conditionmethod
n<64n < 64 or p<128p < 128Newton iteration with evaluations of PnP_n [JM2018]
0.3n≤p≤15n0.3n \le p \le 15nbit-burst Newton steps (_arb_hypgeom_legendre_p_ui_root_bitburst)
otherwiseNewton–Taylor steps (_arb_hypgeom_legendre_p_ui_root_taylor)

The last two certify their result with an interval Newton step and an isolating enclosure; if a certification step fails, the first method is used.

Initial approximation and isolation#

All methods start from the approximation of Petras [Pet1999]: with ϕ=4k+34n+2π\phi = \frac{4k+3}{4n+2}\pi (that is, (4k′−1)π/(4n+2)(4k'-1)\pi/(4n+2) for the 1-based index k′=k+1k' = k + 1),

xk≈cos⁡ψ,ψ=ϕ+2cos⁡ϕ(4n+2)2sin⁡ϕ(1−11(4n+2)2sin⁡2ϕ),x_k \approx \cos\psi, \qquad \psi = \phi + \frac{2\cos\phi}{(4n+2)^2 \sin\phi}\left(1 - \frac{11}{(4n+2)^2 \sin^2\phi}\right),

with an error of at most ϕ2⋅22y4(1+2y2)\phi^2 \cdot 22 y^4 (1 + 2y^2), y=1/((4k′−1)π)y = 1/((4k'-1)\pi), a bound that is squared by each Newton step.

The bit-burst and Newton–Taylor methods identify the root through this enclosure at about 64+2log⁡2n64 + 2\log_2 n bits: it is checked to lie in (0,1)(0, 1) and to be disjoint from the enclosures of xk−1x_{k-1} and xk+1x_{k+1}, so that it contains xkx_k and no other root. Their final interval Newton step proves that a candidate interval contains exactly one root of PnP_n, and containment of that interval in the Petras enclosure proves that it is xkx_k.

Newton iteration with full evaluations#

  1. Starting from Petras' approximation, Newton steps at a precision about 20% above the target square the a priori error bound until it is below 2−p2^{-p}.
  2. When 40 bits plus a padding of 8+2log⁡2n8 + 2\log_2 n bits is less than half of pp, step 1 is carried out only at a low starting precision, and the enclosure is refined by interval Newton steps x↦m−Pn(m)/Pn′(X)x \mapsto m - P_n(m)/P_n'(X) at doubling precisions, where mm is the midpoint of the current enclosure XX and Pn′(X)P_n'(X) is bounded by Pn′(m)P_n'(m) plus a bound for Pn′′P_n'' from arb_hypgeom_legendre_p_ui_deriv_bound times the radius.
  3. The weight comes from Pn′P_n' at the enclosure of xkx_k.

All evaluations of PnP_n and Pn′P_n' use arb_hypgeom_legendre_p_ui; the last one, at full precision and with a full-precision argument, dominates the cost.

Taylor bounds#

The other two methods use the Taylor series Pn(m+t)=∑jcjtjP_n(m + t) = \sum_j c_j t^j at a real point mm. For zz in the disk ∣z−m∣≤r|z - m| \le r, the Laplace integral

Pn(z)=1π∫0π(z+z2−1cos⁡φ)ndφP_n(z) = \frac{1}{\pi} \int_0^\pi \left(z + \sqrt{z^2-1}\cos\varphi\right)^n d\varphi

gives ∣Pn(z)∣≤M=max⁡ρ(z)n|P_n(z)| \le M = \max \rho(z)^n with ρ(z)=max⁡∣z±i1−z2∣\rho(z) = \max|z \pm i\sqrt{1-z^2}|, since the integrand is a convex combination of the two endpoints; MM is bounded on a box enclosing the disk, which must lie in the half-plane Re⁡(1−z2)>0\operatorname{Re}(1 - z^2) > 0. The Cauchy estimates ∣cj∣≤M/rj|c_j| \le M/r^j give, for ∣t∣≤τ=qr|t| \le \tau = q r with q<1/2q < 1/2,

∑j>R∣cj∣τj≤MqR+11−q,∑j>Rj∣cj∣τj−1≤Mr (R+1)qR(1−q)2.\sum_{j > R} |c_j| \tau^j \le \frac{M q^{R+1}}{1-q}, \qquad \sum_{j > R} j |c_j| \tau^{j-1} \le \frac{M}{r}\,\frac{(R+1) q^R}{(1-q)^2}.

The radius is r=0.99min⁡(1−m2/n, (1−m)/4)r = 0.99\min(\sqrt{1-m^2}/n,\ (1-m)/4), about the distance over which PnP_n changes by a bounded factor: about 1/n1/n in the interior and (k+1)2/n2(k+1)^2/n^2 near ±1\pm 1.

Bit-burst Newton steps#

For precision comparable to nn, the root is computed by the bit-burst idea for holonomic functions [CC1990; vdH1999]: every evaluation point has only about twice as many bits as the accuracy of the approximation it represents, so that the full-precision work multiplies full-precision numbers only by short integers.

  1. Starting point. x(0)=A/2Bx^{(0)} = A/2^B, from Petras' approximation and three Newton steps in double precision. The first transfer needs ∣x(0)−xk∣|x^{(0)} - x_k| well below the radius rr of the Taylor bounds. With B=w−2−⌈log⁡22n⌉B = w - 2 - \lceil \log_2 2n \rceil for the word size ww, the multipliers of stage 0 fit in a word; this is used when 2B≥w2B \ge w and 2−B≤r/642^{-B} \le r/64. Otherwise BB is the larger of 62−⌈log⁡22n⌉62 - \lceil \log_2 2n \rceil and log⁡2(1/r)+8\log_2(1/r) + 8, and for r<2−44r < 2^{-44}, beyond the accuracy of double precision, x(0)x^{(0)} is the midpoint of Petras' enclosure, whose error is a small fraction of rr.
  2. Stage 0 computes PnP_n and Pn−1P_{n-1} at x(0)x^{(0)} to the working precision. With uj=j! 2BjPj(x(0))u_j = j!\,2^{Bj} P_j(x^{(0)}) the three-term recurrence becomes

    uj+1=(2j+1)A uj−j222Buj−1,u_{j+1} = (2j+1) A\, u_j - j^2 2^{2B} u_{j-1},

    with no division. With the word-size choice of BB and below 130000 bits, the recurrence runs on two's complement limb windows of fixed size (one mpn_mul_1 and one mpn_submul_1 per step), dropping the low limbs as the values grow; otherwise exact products of blocks of steps, each of about the working precision and formed by binary splitting, are applied in turn to a ball vector.

  3. Transfer stages. The Newton correction −Pn/Pn′-P_n/P_n' is rounded to δ=D/2E\delta = D/2^E with about twice as many bits as the current accuracy, and (Pn,Pn′)(P_n, P_n') are moved from x=A/2Bx = A/2^B to x+δx + \delta by the Taylor series. From the Legendre equation (1−x2)y′′−2xy′+n(n+1)y=0(1-x^2)y'' - 2xy' + n(n+1)y = 0, the terms aj=cjδja_j = c_j \delta^j satisfy

    γjaj+2=αjaj+1+βjaj,αj=2AD(j+1)22E−B,βj=D2(j(j+1)−n(n+1)),γj=σ(j+1)(j+2)22(E−B),\gamma_j a_{j+2} = \alpha_j a_{j+1} + \beta_j a_j, \quad \alpha_j = 2AD(j+1)^2 2^{E-B}, \quad \beta_j = D^2 (j(j+1) - n(n+1)), \quad \gamma_j = \sigma (j+1)(j+2) 2^{2(E-B)},

    with σ=22B−A2\sigma = 2^{2B} - A^2. The sums ∑aj\sum a_j and ∑jaj\sum j a_j, which give Pn(x+δ)P_n(x + \delta) and δPn′(x+δ)\delta P_n'(x+\delta), are computed in fixed point, with the terms as integers whose lengths decrease with jj, so that the precision tapers by itself; the powers of two are split off from the divisions. When K⋅pK \cdot p exceeds 101010^{10}, exact blocks of steps formed by binary splitting are applied in ball arithmetic instead. The number of terms KK is chosen so that the terms beyond it are below the working precision, and their sum is bounded by the Taylor bound above. Each stage doubles the size of the integers and halves the number of terms.

  4. Final step. At the last point, within about 2−p/22^{-p/2} of xkx_k, an interval Newton step on the Taylor polynomial of degree 2 plus its tail bound encloses xkx_k, and Pn′(xk)P_n'(x_k) for the weight comes from the same expansion.

The products of 2×22 \times 2 blocks use fmpz_mat_mul_fft_small for entries above 10000 bits.

Error bound for the limb recurrence. When a step drops limbs, the new uj+1u_{j+1} and the new uju_j lose less than one unit 2wS2^{wS} of the lowest kept limb each (SS the limb exponent of the window); in terms of Pi=ui/(i! 2Bi)P_i = u_i / (i!\,2^{Bi}), these are errors in Pj+1P_{j+1} and, through the multiplier, in Pj+2P_{j+2}, of at most (j+2) 2B+wS/((j+1)! 2B(j+1))(j+2)\, 2^{B + wS} / ((j+1)!\,2^{B(j+1)}) together. The computed sequence is the exact one plus, for each error ee in PiP_i, the solution yy of the recurrence with yi=ey_i = e, yi−1=0y_{i-1} = 0. With x=cos⁡θx = \cos\theta, s=sin⁡θs = \sin\theta and

Em=m (ym2−2xymym−1+ym−12)=m(ym−1−xym)2+ms2ym2,E_m = m\,(y_m^2 - 2x y_m y_{m-1} + y_{m-1}^2) = m (y_{m-1} - x y_m)^2 + m s^2 y_m^2,

the recurrence (m+1)ym+1=(2m+1)xym−mym−1(m+1) y_{m+1} = (2m+1) x y_m - m y_{m-1} gives

Em+1=m2m+1(ym−1−xym)2+(m+1)s2ym2≤m+1mEm,E_{m+1} = \frac{m^2}{m+1} (y_{m-1} - x y_m)^2 + (m+1) s^2 y_m^2 \le \frac{m+1}{m} E_m,

so Em≤(m/i)Ei=me2E_m \le (m/i) E_i = m e^2 and s2ym2≤Em/m≤e2s^2 y_m^2 \le E_m/m \le e^2: every error reaches PnP_n and Pn−1P_{n-1} multiplied by at most 1/s1/s. The bound is accumulated during the recurrence in mag_t arithmetic.

Error bound for the fixed-point transfers. The products in the recurrence for aja_j are exact and each division by γj\gamma_j truncates, adding less than one unit. With ϵj\epsilon_j the error of aja_j in units,

ϵj+2≤∣αj∣ϵj+1+∣βj∣ϵjγj+1,\epsilon_{j+2} \le \frac{|\alpha_j| \epsilon_{j+1} + |\beta_j| \epsilon_j}{\gamma_j} + 1,

a contracting recurrence since ∣δ∣|\delta| is small compared with the radius of convergence; it is also evaluated in mag_t arithmetic, starting from the radii of PnP_n and δPn′\delta P_n'.

Newton–Taylor steps#

For precision much larger or much smaller than nn:

  1. An enclosure m±τm \pm \tau of xkx_k at a quarter of the precision, computed recursively by the method chosen for that precision.
  2. One evaluation of Pn(m)P_n(m) and Pn′(m)P_n'(m) at the full precision with arb_hypgeom_legendre_p_ui, and the Taylor coefficients cjc_j from the recurrence

    (1−m2)(j+1)(j+2)cj+2=2m(j+1)2cj+1+(j(j+1)−n(n+1))cj,(1-m^2)(j+1)(j+2) c_{j+2} = 2m(j+1)^2 c_{j+1} + (j(j+1) - n(n+1)) c_j,

    with the precision of cjc_j tapered by τj\tau^j. The degree RR is the smallest for which the Taylor bound at ∣t∣≤τ|t| \le \tau is below the working precision.

  3. The fixed-point iteration d←−(c0+∑j≥2cjdj)/c1d \leftarrow -(c_0 + \sum_{j \ge 2} c_j d^j)/c_1 on midpoints, which gains about a quarter of the precision per step, and a final interval Newton step on the Taylor polynomial of degree RR plus its tail bound.

The single full-precision evaluation of PnP_n dominates the cost when the precision is much larger than nn; when it is much smaller, that evaluation uses the asymptotic expansion.

Legendre functions#

For complex degree nn, order mm and argument zz, the associated Legendre function of the first kind is

Pnm(z)=(1+z1−z)m/2F(−n,n+1;1−m;1−z2)(type 0),Pnm(z)=(z+1z−1)m/2F(−n,n+1;1−m;1−z2)(type 1),P_n^m(z) = \left(\frac{1+z}{1-z}\right)^{m/2} \mathbf{F}\left(-n, n+1; 1-m; \frac{1-z}{2}\right) \quad\text{(type 0)}, \qquad \mathcal{P}_n^m(z) = \left(\frac{z+1}{z-1}\right)^{m/2} \mathbf{F}\left(-n, n+1; 1-m; \frac{1-z}{2}\right) \quad\text{(type 1)},

with the regularized 2F1{}_2F_1 (type 0 has cuts on (−∞,−1](-\infty, -1] and [1,∞)[1, \infty), type 1 on (−∞,1](-\infty, 1]), and the function of the second kind is

Qnm(z)=π2sin⁡(πm)(cos⁡(πm)Pnm(z)−Γ(1+m+n)Γ(1−m+n)Pn−m(z))Q_n^m(z) = \frac{\pi}{2 \sin(\pi m)} \left( \cos(\pi m) P_n^m(z) - \frac{\Gamma(1+m+n)}{\Gamma(1-m+n)} P_n^{-m}(z)\right)

(and analogously for type 1). acb_hypgeom_legendre_p evaluates the 2F1{}_2F_1 representation with acb_hypgeom_2f1, which handles the transformations needed for large ∣z∣|z|. For integers 0≤m≤n0 \le m \le n it uses instead the recurrence of acb_hypgeom_legendre_p_uiui_rec for (1−z2)−m/2Pnm(z)(1-z^2)^{-m/2}P_n^m(z), starting from PmmP_m^m and Pm+1mP_{m+1}^m, when the precision is low compared to nn, n−mn - m is small, or zz is near 1 (where the transformations are singular); real zz with m=0m = 0 goes to arb_hypgeom_legendre_p_ui. If n−m>2pn - m > 2p the recurrence would lose all accuracy and the result is indeterminate.

For integer mm, the defining formula for QnmQ_n^m is a 0⋅∞0 \cdot \infty limit, so acb_hypgeom_legendre_q uses connection formulas without the removable singularity. For type 0 it evaluates two ordinary 2F1{}_2F_1 series in z2z^2 with gamma and trigonometric prefactors [WQ3a]. For type 1 it evaluates one regularized 2F1{}_2F_1 in 1/z21/z^2 [WQ3b] when the ball zz is away from the real half-line [−1,∞)[-1, \infty) and from the square ∣Re⁡z∣,∣Im⁡z∣<1/4|\operatorname{Re} z|, |\operatorname{Im} z| < 1/4 (the formula is invalid on (−1,0)(-1, 0)), and otherwise combines the type 0 function QnmQ_n^m and Pnm\mathcal{P}_n^m [WQ3c]. (The formula [WQ3d] would also be convenient, but it is incorrect in the lower half-plane.)

The spherical harmonics

Ynm(θ,ϕ)=2n+14π(n−m)!(n+m)!eimϕPnm(cos⁡θ)Y_n^m(\theta, \phi) = \sqrt{\frac{2n+1}{4\pi} \frac{(n-m)!}{(n+m)!}} e^{im\phi} P_n^m(\cos\theta)

are polynomials in cos⁡θ\cos\theta and sin⁡θ\sin\theta, which acb_hypgeom_spherical_y evaluates with acb_hypgeom_legendre_p_uiui_rec.

Other orthogonal polynomials#

The other classical families are defined for complex degree through 2F1{}_2F_1 or 1F1{}_1F_1:

FunctionDefinitionDirect method for integer n≥0n \ge 0
Chebyshev Tn(z)T_n(z), Un(z)U_n(z)2F1(−n,n;12;1−z2){}_2F_1(-n, n; \frac12; \frac{1-z}{2}), (n+1) 2F1(−n,n+2;32;1−z2)(n+1)\,{}_2F_1(-n, n+2; \frac32; \frac{1-z}{2})acb_chebyshev_t_ui, acb_chebyshev_u_ui (word-size nn)
Jacobi Pn(a,b)(z)P_n^{(a,b)}(z)(a+1)nn! 2F1(−n,n+a+b+1;a+1;1−z2)\frac{(a+1)_n}{n!}\,{}_2F_1(-n, n+a+b+1; a+1; \frac{1-z}{2})explicit double sum for n≤pn \le p and a<−0.9a < -0.9
Gegenbauer Cnm(z)C_n^m(z)(2m)nn! 2F1(−n,2m+n;m+12;1−z2)\frac{(2m)_n}{n!}\,{}_2F_1(-n, 2m+n; m+\frac12; \frac{1-z}{2})recurrence in nn for n≤pn \le p and m<0m < 0
Laguerre Lnm(z)L_n^m(z)(m+1)nn! 1F1(−n;m+1;z)\frac{(m+1)_n}{n!}\,{}_1F_1(-n; m+1; z)recurrence in nn for n≤pn \le p and ∣m∣>n\lvert m\rvert > n
Hermite Hn(z)H_n(z)2nπ(1F1(−n2;12;z2)Γ(1−n2)−2z 1F1(1−n2;32;z2)Γ(−n2))2^n\sqrt\pi\left(\frac{{}_1F_1(-\frac n2; \frac12; z^2)}{\Gamma(\frac{1-n}{2})} - \frac{2z\,{}_1F_1(\frac{1-n}{2}; \frac32; z^2)}{\Gamma(-\frac n2)}\right)—

The direct methods cover the cases where the hypergeometric representation is singular although the polynomial is defined (the lower parameter a+1a + 1, m+12m + \frac12 or m+1m + 1 is near a nonpositive integer). For non-integer degree, the Chebyshev functions use Tν(cos⁡θ)=cos⁡(νθ)T_\nu(\cos\theta) = \cos(\nu\theta) and Uν(cos⁡θ)=sin⁡((ν+1)θ)/sin⁡θU_\nu(\cos\theta) = \sin((\nu+1)\theta)/\sin\theta (with cosh⁡\cosh for zz outside [−1,1][-1,1]) away from z=1z = 1, and the 2F1{}_2F_1 series near it.

Use in FLINT#

Referenced from#

References#

  • [JM2018] F. Johansson and M. Mezzarobba, "Fast and rigorous arbitrary-precision computation of Gauss-Legendre quadrature nodes and weights", preprint (2018), https://arxiv.org/abs/1802.03948
  • [Bog2012] I. Bogaert, B. Michiels and J. Fostier, "O(1) computation of Legendre polynomials and Gauss-Legendre nodes and weights for parallel computing", SIAM Journal on Scientific Computing 34:3 (2012), C83-C101
  • [Pet1999] K. Petras, "On the computation of the Gauss-Legendre quadrature formula with a given precision", Journal of Computational and Applied Mathematics 112 (1999), 253-267
  • [CC1990] D. V. Chudnovsky and G. V. Chudnovsky. Computer algebra in the service of mathematical physics and number theory. In Computers in Mathematics (Stanford, 1986), Lecture Notes in Pure and Applied Mathematics 125, Dekker, 1990, 109–232.
  • [vdH1999] J. van der Hoeven. Fast evaluation of holonomic functions. Theoretical Computer Science 210:1 (1999), 199–215. https://doi.org/10.1016/S0304-3975(98)00102-9
  • [WQ3a] The Wolfram Functions Site, formula 07.11.26.0033.01. http://functions.wolfram.com/07.11.26.0033.01
  • [WQ3b] The Wolfram Functions Site, formula 07.12.27.0014.01. http://functions.wolfram.com/07.12.27.0014.01
  • [WQ3c] The Wolfram Functions Site, formula 07.12.26.0003.01. http://functions.wolfram.com/07.12.26.0003.01
  • [WQ3d] The Wolfram Functions Site, formula 07.12.26.0088.01. http://functions.wolfram.com/07.12.26.0088.01
Cite this page

The FLINT team, “Legendre functions and orthogonal polynomials,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/special-functions/legendre.html (generated 2026-11-20).