×

\(\mathcal{O}(1)\) computation of Legendre polynomials and Gauss-Legendre nodes and weights for parallel computing. (English) Zbl 1254.65038

Summary: A self-contained set of algorithms is proposed for the fast evaluation of Legendre polynomials of arbitrary degree and argument \(\in [-1,1]\). More specifically, the time required to evaluate any Legendre polynomial, regardless of argument and degree, is bounded by a constant; i.e., the complexity is \(\mathcal{O}(1)\). The proposed algorithm also immediately yields an \(\mathcal{O}(1)\) algorithm for computing an arbitrary Gauss-Legendre quadrature node. Such a capability is crucial for efficiently performing certain parallel computations with high order Legendre polynomials, such as computing an integral in parallel by means of Gauss-Legendre quadrature and the parallel evaluation of Legendre series. In order to achieve the \(\mathcal{O}(1)\) complexity, novel efficient asymptotic expansions are derived and used alongside known results. A C++ implementation is available from the authors that includes the evaluation routines of the Legendre polynomials and Gauss-Legendre quadrature rules.

MSC:

65D20 Computation of special functions and constants, construction of tables
33C45 Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)
65D32 Numerical quadrature and cubature formulas
41A55 Approximate quadratures
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI