Evaluation of Gauss-Legendre curves
Pith reviewed 2026-05-10 06:15 UTC · model grok-4.3
The pith
Gauss-Legendre curves of degree n in d dimensions evaluate in O(n^{2} + d n) time via new representations in shifted power and Jacobi-related bases.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
New representations of Gauss-Legendre polynomials and their derivatives are given in the shifted power basis and in bases related to symmetric orthogonal Jacobi polynomials. These representations and certain recurrence relations are then used to construct evaluation algorithms for a Gauss-Legendre curve of degree n in E^d that require only O(n^{2} + d n) operations, together with multipoint evaluation algorithms of complexity O(M d n + d n^{2}).
What carries the argument
Representations of Gauss-Legendre polynomials and derivatives in the shifted power basis together with bases derived from symmetric orthogonal Jacobi polynomials, combined with recurrence relations that permit incremental evaluation.
If this is right
- A single Gauss-Legendre curve of degree n in d-space evaluates in quadratic time in n and linear time in d.
- Multipoint evaluation of M points on the same curve costs O(M d n + d n^{2}) operations.
- The same representations support derivative evaluation at the same asymptotic cost.
- The approach applies uniformly to the curve and its first derivative without separate machinery.
Where Pith is reading between the lines
- The basis changes may extend to other classical orthogonal polynomial families that admit similar recurrence structures, yielding comparable speed-ups for their associated curves.
- Applications such as high-order quadrature or piecewise polynomial approximation that repeatedly evaluate Legendre curves could see reduced overall run time once the representations are precomputed.
- Floating-point accuracy of the recurrences for large n remains an open verification point that would determine practical range of the methods.
Load-bearing premise
The new polynomial representations are algebraically exact and the recurrence relations incur no hidden costs or numerical instability that would invalidate the stated operation counts.
What would settle it
An implementation or operation count that requires more than O(n^{2} + d n) arithmetic operations for a single curve evaluation of large n and d, or that exhibits instability for moderate n, would falsify the efficiency claims.
Figures
read the original abstract
We present new representations of Gauss--Legendre polynomials and their derivatives in the shifted power basis and in bases related to symmetric orthogonal Jacobi polynomials. Using these representations and certain recurrence relations, we propose efficient $O(n^2+dn)$ methods for evaluating a Gauss--Legendre curve of degree $n$ in $\mathbb E^d$. We also propose algorithms for multipoint evaluation with computational complexity $O(Mdn+dn^2)$, where $M$ is the number of evaluation points.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents new representations of Gauss-Legendre polynomials and their derivatives in the shifted power basis and in bases related to symmetric orthogonal Jacobi polynomials. Using these representations together with recurrence relations, it proposes O(n² + d n) algorithms for evaluating a Gauss-Legendre curve of degree n in E^d and O(M d n + d n²) algorithms for multipoint evaluation, where M denotes the number of points.
Significance. If the algebraic identities hold and the resulting procedures remain stable, the work would supply concrete, asymptotically efficient evaluation schemes for a classical family of orthogonal polynomials in multiple dimensions. Such bounds are of interest in numerical quadrature, approximation theory, and geometric modeling; the explicit use of both monomial and Jacobi-related bases is a constructive strength.
major comments (3)
- [Abstract] Abstract: the central claim that 'representations plus recurrences yield the claimed complexities' is asserted without any derivation steps, operation-count breakdown, or pseudocode. Because the O(n² + d n) bound is the primary contribution, the absence of these details makes the complexity statement unverifiable from the given text.
- [Representations (shifted power basis)] Section on shifted-power representations (presumably §3): the monomial (shifted-power) basis is known to be exponentially ill-conditioned on [-1,1] for n ≳ 20. No forward-error analysis, compensated-summation strategy, or explicit rule for switching to the Jacobi-related bases is supplied; this omission directly affects whether the stated practical complexity can be realized in floating-point arithmetic.
- [Algorithms] Algorithm sections (presumably §4–5): the multipoint complexity O(M d n + d n²) presupposes that the per-point cost remains linear after the O(n²) precomputation. Without a stability or rounding-error discussion, it is unclear whether the claimed bound survives when the power-basis route is used for large n.
minor comments (2)
- [Abstract and §1] Define the ambient space E^d and the constant M explicitly at first use.
- [Introduction] Add a short comparison table or paragraph contrasting the new complexities with standard Horner, Clenshaw, or barycentric schemes for Gauss-Legendre polynomials.
Simulated Author's Rebuttal
We thank the referee for the thoughtful and detailed report. The comments highlight important issues of clarity in the abstract, numerical stability of the proposed bases, and the distinction between arithmetic complexity and practical floating-point behavior. We address each point below and indicate the revisions we will make.
read point-by-point responses
-
Referee: [Abstract] Abstract: the central claim that 'representations plus recurrences yield the claimed complexities' is asserted without any derivation steps, operation-count breakdown, or pseudocode. Because the O(n² + d n) bound is the primary contribution, the absence of these details makes the complexity statement unverifiable from the given text.
Authors: We agree that the abstract is too terse on this central claim. In the revised manuscript we will expand the abstract to include a concise outline of the derivation: the O(n²) term arises from precomputing the coefficients of the Gauss–Legendre polynomial (and its derivative) in the chosen basis via the new representations and recurrences, while the O(dn) term is the subsequent cost of evaluating the resulting degree-n polynomial in E^d at a single point. We will also add a short pseudocode sketch of the main evaluation procedure to Section 4 and ensure an explicit operation-count table appears in the text. revision: yes
-
Referee: [Representations (shifted power basis)] Section on shifted-power representations (presumably §3): the monomial (shifted-power) basis is known to be exponentially ill-conditioned on [-1,1] for n ≳ 20. No forward-error analysis, compensated-summation strategy, or explicit rule for switching to the Jacobi-related bases is supplied; this omission directly affects whether the stated practical complexity can be realized in floating-point arithmetic.
Authors: The referee correctly identifies the well-known ill-conditioning of the monomial basis. Our manuscript derives algebraic representations and asymptotic arithmetic costs; it does not contain a forward-error analysis. In the revision we will insert a short subsection (or paragraph) in §3 that (i) recalls the exponential growth of the condition number, (ii) states an explicit rule of thumb to switch to the symmetric Jacobi-related bases for n ≳ 20, and (iii) notes that compensated summation can be used with the power-basis route when n is moderate. A full rounding-error analysis lies outside the scope of the present work. revision: partial
-
Referee: [Algorithms] Algorithm sections (presumably §4–5): the multipoint complexity O(M d n + d n²) presupposes that the per-point cost remains linear after the O(n²) precomputation. Without a stability or rounding-error discussion, it is unclear whether the claimed bound survives when the power-basis route is used for large n.
Authors: The stated bound O(Mdn + dn²) is an arithmetic-complexity result that counts floating-point operations under the assumption that each operation is performed at unit cost; it does not incorporate stability considerations. After the O(n²) precomputation of basis coefficients or recurrence data, each of the M points is evaluated independently in O(dn) arithmetic operations via the recurrences or Horner-like schemes. In the revision we will clarify this distinction and cross-reference the new stability discussion added in response to the previous comment, emphasizing that the Jacobi-related bases should be used for large n to keep the per-point linear cost realizable in practice. revision: partial
Circularity Check
Algebraic derivations from polynomial identities; no circular reductions
full rationale
The paper derives new explicit representations of Gauss-Legendre polynomials and derivatives in the shifted power basis and Jacobi-related bases, then applies standard recurrence relations to obtain evaluation algorithms of complexity O(n² + d n) and multipoint variants O(M d n + d n²). These steps rest on direct algebraic identities and polynomial arithmetic, with no fitted parameters, no predictions that reduce to inputs by construction, and no load-bearing self-citations or imported uniqueness theorems. The derivation chain is self-contained against external polynomial theory and does not collapse to its own outputs.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard algebraic and recurrence properties of Gauss-Legendre and symmetric Jacobi polynomials hold.
Reference graph
Works this paper leans on
-
[1]
M. K. Agoston, Computer graphics and geometric modelling. Implementation & algo- rithms, 1st ed., Springer, London, 2005
work page 2005
-
[2]
Gautschi, Numerical analysis, 2nd ed., Birkh¨ auser, 2011
W. Gautschi, Numerical analysis, 2nd ed., Birkh¨ auser, 2011
work page 2011
-
[3]
I. S. Gradshteyn, I. M. Ryzhik, Table of integrals, series, and products, 7th ed., Else- vier/Academic Press, Amsterdam, 2007
work page 2007
-
[4]
N. Hale, A. Townsend, Fast and accurate computation of Gauss–Legendre and Gauss– Jacobi quadrature nodes and weights, SIAM Journal on Scientific Computing 35 (2013) A652–A674
work page 2013
-
[5]
F. Johansson, M. Mezzarobba, Fast and rigorous arbitrary-precision computation of Gauss–Legendre quadrature nodes and weights, SIAM Journal on Scientific Computing 40 (2018) C726–C747
work page 2018
-
[6]
R. Koekoek, P. A. Lesky, R. F. Swarttouw, Hypergeometric orthogonal polynomials and theirq-analogues, Springer Monographs in Mathematics, Springer Berlin Heidelberg, 2010
work page 2010
-
[7]
H. P. Moon, S. H. Kim, S.-H. Kwon, Gauss–Legendre polynomial basis for the shape control of polynomial curves, Applied Mathematics and Computation 451 (2023) 127995
work page 2023
-
[8]
H. P. Moon, S. H. Kim, S.-H. Kwon, A novel method for manipulating polynomial curves by the Gauss–Legendre control polygon with points interpolating property, Applied Math- ematics and Computation 512 (2026) 129760
work page 2026
-
[9]
J. Shen, T. Tang, L.-L. Wang, Orthogonal polynomials and related approximation results, in: Spectral methods: algorithms, analysis and applications, vol. 41 of Springer Series in Computational Mathematics, Springer Berlin Heidelberg, 2011. 15
work page 2011
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.