Legendre functions and orthogonal polynomials
The Legendre polynomials , and more generally the classical orthogonal polynomials (Jacobi, Gegenbauer, Chebyshev, Laguerre, Hermite), are terminating hypergeometric series, for example
For integer degree they can be evaluated directly as polynomials, but for large this is slow and numerically unstable: the coefficients grow exponentially while on . FLINT has a dedicated algorithm for with real and word-size , which also gives the nodes and weights of Gauss–Legendre quadrature; the other functions use the general and 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 and together for real , and by only is needed. Four expansions are available.
Expansion at (
arb_hypgeom_legendre_p_ui_one):The terms decrease quickly when is small, and the series can be truncated after terms with a bound for the remainder.
Expansion at (
arb_hypgeom_legendre_p_ui_zero): for even ,and an analogous formula with for odd . The terms decrease when is small.
Asymptotic expansion (
arb_hypgeom_legendre_p_ui_asymp): with , , the Stieltjes seriessummed as the real part of a complex series in , with the explicit bound , , which follows from the analysis of Bogaert, Michiels and Fostier [Bog2012]. The number of terms needed decreases as grows; for much larger than the precision a handful of terms suffice, independently of .
- Recurrence (
arb_hypgeom_legendre_p_ui_rec): the three-term recurrence , scaled by its denominators: satisfies 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 productflint_mpn_mulhigh_nby and two operations by words, and the result is divided by at the end. The rounding errors are bounded a priori with the error-propagation estimate of [JM2018, Proposition 5], which uses only . It is stable on , costs short-product operations, and is the fastest method for moderate 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 ), and the size of the error term of the asymptotic expansion. The recurrence is used for below a few hundred at low precision, unless is very close to 0 or 1; for 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 the function evaluates at the midpoint and adds the error propagated from the radius , bounded by and on the ball (arb_hypgeom_legendre_p_ui_deriv_bound, which uses and for , with ).
Gauss–Legendre nodes and weights#
The roots of and the weights are computed by arb_hypgeom_legendre_p_ui_root. By the symmetry , only the positive roots, , are computed; the middle root of odd is . There are three methods, chosen by and the precision :
| condition | method |
|---|---|
| or | Newton iteration with evaluations of [JM2018] |
bit-burst Newton steps (_arb_hypgeom_legendre_p_ui_root_bitburst) | |
| otherwise | Newton–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 (that is, for the 1-based index ),
with an error of at most , , a bound that is squared by each Newton step.
The bit-burst and Newton–Taylor methods identify the root through this enclosure at about bits: it is checked to lie in and to be disjoint from the enclosures of and , so that it contains and no other root. Their final interval Newton step proves that a candidate interval contains exactly one root of , and containment of that interval in the Petras enclosure proves that it is .
Newton iteration with full evaluations#
- Starting from Petras' approximation, Newton steps at a precision about 20% above the target square the a priori error bound until it is below .
- When 40 bits plus a padding of bits is less than half of , step 1 is carried out only at a low starting precision, and the enclosure is refined by interval Newton steps at doubling precisions, where is the midpoint of the current enclosure and is bounded by plus a bound for from
arb_hypgeom_legendre_p_ui_deriv_boundtimes the radius. - The weight comes from at the enclosure of .
All evaluations of and 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 at a real point . For in the disk , the Laplace integral
gives with , since the integrand is a convex combination of the two endpoints; is bounded on a box enclosing the disk, which must lie in the half-plane . The Cauchy estimates give, for with ,
The radius is , about the distance over which changes by a bounded factor: about in the interior and near .
Bit-burst Newton steps#
For precision comparable to , 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.
- Starting point. , from Petras' approximation and three Newton steps in double precision. The first transfer needs well below the radius of the Taylor bounds. With for the word size , the multipliers of stage 0 fit in a word; this is used when and . Otherwise is the larger of and , and for , beyond the accuracy of double precision, is the midpoint of Petras' enclosure, whose error is a small fraction of .
Stage 0 computes and at to the working precision. With the three-term recurrence becomes
with no division. With the word-size choice of and below 130000 bits, the recurrence runs on two's complement limb windows of fixed size (one
mpn_mul_1and onempn_submul_1per 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.Transfer stages. The Newton correction is rounded to with about twice as many bits as the current accuracy, and are moved from to by the Taylor series. From the Legendre equation , the terms satisfy
with . The sums and , which give and , are computed in fixed point, with the terms as integers whose lengths decrease with , so that the precision tapers by itself; the powers of two are split off from the divisions. When exceeds , exact blocks of steps formed by binary splitting are applied in ball arithmetic instead. The number of terms 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.
- Final step. At the last point, within about of , an interval Newton step on the Taylor polynomial of degree 2 plus its tail bound encloses , and for the weight comes from the same expansion.
The products of 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 and the new lose less than one unit of the lowest kept limb each ( the limb exponent of the window); in terms of , these are errors in and, through the multiplier, in , of at most together. The computed sequence is the exact one plus, for each error in , the solution of the recurrence with , . With , and
the recurrence gives
so and : every error reaches and multiplied by at most . The bound is accumulated during the recurrence in mag_t arithmetic.
Error bound for the fixed-point transfers. The products in the recurrence for are exact and each division by truncates, adding less than one unit. With the error of in units,
a contracting recurrence since is small compared with the radius of convergence; it is also evaluated in mag_t arithmetic, starting from the radii of and .
Newton–Taylor steps#
For precision much larger or much smaller than :
- An enclosure of at a quarter of the precision, computed recursively by the method chosen for that precision.
One evaluation of and at the full precision with
arb_hypgeom_legendre_p_ui, and the Taylor coefficients from the recurrencewith the precision of tapered by . The degree is the smallest for which the Taylor bound at is below the working precision.
- The fixed-point iteration on midpoints, which gains about a quarter of the precision per step, and a final interval Newton step on the Taylor polynomial of degree plus its tail bound.
The single full-precision evaluation of dominates the cost when the precision is much larger than ; when it is much smaller, that evaluation uses the asymptotic expansion.
Legendre functions#
For complex degree , order and argument , the associated Legendre function of the first kind is
with the regularized (type 0 has cuts on and , type 1 on ), and the function of the second kind is
(and analogously for type 1). acb_hypgeom_legendre_p evaluates the representation with acb_hypgeom_2f1, which handles the transformations needed for large . For integers it uses instead the recurrence of acb_hypgeom_legendre_p_uiui_rec for , starting from and , when the precision is low compared to , is small, or is near 1 (where the transformations are singular); real with goes to arb_hypgeom_legendre_p_ui. If the recurrence would lose all accuracy and the result is indeterminate.
For integer , the defining formula for is a limit, so acb_hypgeom_legendre_q uses connection formulas without the removable singularity. For type 0 it evaluates two ordinary series in with gamma and trigonometric prefactors [WQ3a]. For type 1 it evaluates one regularized in [WQ3b] when the ball is away from the real half-line and from the square (the formula is invalid on ), and otherwise combines the type 0 function and [WQ3c]. (The formula [WQ3d] would also be convenient, but it is incorrect in the lower half-plane.)
The spherical harmonics
are polynomials in and , 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 or :
| Function | Definition | Direct method for integer |
|---|---|---|
| Chebyshev , | , | acb_chebyshev_t_ui, acb_chebyshev_u_ui (word-size ) |
| Jacobi | explicit double sum for and | |
| Gegenbauer | recurrence in for and | |
| Laguerre | recurrence in for and | |
| Hermite | — |
The direct methods cover the cases where the hypergeometric representation is singular although the polynomial is defined (the lower parameter , or is near a nonpositive integer). For non-integer degree, the Chebyshev functions use and (with for outside ) away from , and the series near it.
Use in FLINT#
arb_hypgeom_legendre_p_uiand its methodsarb_hypgeom_legendre_p_ui_zero,arb_hypgeom_legendre_p_ui_one,arb_hypgeom_legendre_p_ui_asymp,arb_hypgeom_legendre_p_ui_rec;arb_hypgeom_legendre_p_ui_rootand its methods_arb_hypgeom_legendre_p_ui_root_bitburstand_arb_hypgeom_legendre_p_ui_root_taylorfor quadrature, used byacb_calc_integrateandarb_fpwrap.acb_hypgeom_legendre_p,acb_hypgeom_legendre_q,acb_hypgeom_legendre_p_uiui_rec,acb_hypgeom_spherical_yand the real versions.acb_hypgeom_chebyshev_t,acb_hypgeom_chebyshev_u,acb_hypgeom_jacobi_p,acb_hypgeom_gegenbauer_c,acb_hypgeom_laguerre_l,acb_hypgeom_hermite_hand the real versions.
Referenced from#
- acb_hypgeom.h (module)
- The Gauss hypergeometric function (algorithm)
arb_hypgeom_legendre_p_ui_zero,arb_hypgeom_legendre_p_ui_one,arb_hypgeom_legendre_p_ui_asymp,arb_hypgeom_legendre_p_ui_rec,arb_hypgeom_legendre_p_uiarb_hypgeom_legendre_p_ui_root_arb_hypgeom_legendre_p_ui_root_bitburst,_arb_hypgeom_legendre_p_ui_root_taylor- Roots of Legendre polynomials and Gauss–Legendre nodes
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
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).
@misc{flint-doc-algorithms-special-functions-legendre,
author = {{The FLINT team}},
title = {{Legendre functions and orthogonal polynomials}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/special-functions/legendre.html},
note = {Generated 2026-11-20}
}