Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

A unified approach to evaluation algorithms for multivariate polynomials


Authors: Suresh K. Lodha and Ron Goldman
Journal: Math. Comp. 66 (1997), 1521-1553
MSC (1991): Primary 65D17, 65Y20, 68Q25; Secondary 65Y25, 68U05, 68U07
MathSciNet review: 1422789
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a unified framework for most of the known and a few new evaluation algorithms for multivariate polynomials expressed in a wide variety of bases including the Bernstein-Bézier, multinomial (or Taylor), Lagrange and Newton bases. This unification is achieved by considering evaluation algorithms for multivariate polynomials expressed in terms of L-bases, a class of bases that include the Bernstein-Bézier, multinomial, and a rich subclass of Lagrange and Newton bases. All of the known evaluation algorithms can be generated either by considering up recursive evaluation algorithms for L-bases or by examining change of basis algorithms for L-bases. For polynomials of degree $n$ in $s$ variables, the class of up recursive evaluation algorithms includes a parallel up recurrence algorithm with computational complexity $O(n^{s+1})$, a nested multiplication algorithm with computational complexity $O(n^s \log n)$ and a ladder recurrence algorithm with computational complexity $O(n^s)$. These algorithms also generate a new generalization of the Aitken-Neville algorithm for evaluation of multivariate polynomials expressed in terms of Lagrange L-bases. The second class of algorithms, based on certain change of basis algorithms between L-bases, include a nested multiplication algorithm with computational complexity $O(n^s)$, a divided difference algorithm, a forward difference algorithm, and a Lagrange evaluation algorithm with computational complexities $O(n^s)$, $O(n^s)$ and $O(n)$ per point respectively for the evaluation of multivariate polynomials at several points.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65D17, 65Y20, 68Q25, 65Y25, 68U05, 68U07

Retrieve articles in all journals with MSC (1991): 65D17, 65Y20, 68Q25, 65Y25, 68U05, 68U07


Additional Information

Suresh K. Lodha
Affiliation: Department of Computer Science, University of California, Santa Cruz, California 95064
Email: lodha@cse.ucsc.edu

Ron Goldman
Affiliation: Department of Computer Science, Rice University, Houston, Texas 77251-1892
Email: rng@cs.rice.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-97-00862-4
PII: S 0025-5718(97)00862-4
Keywords: Algorithms, Bernstein, B\'{e}zier, change of basis, evaluation, Lagrange, multivariate, Newton, polynomials, recurrence, Taylor
Received by editor(s): July 26, 1995
Received by editor(s) in revised form: July 22, 1996
Additional Notes: The first author was supported in part by NSF Grants CCR-9309738, IRI-9423881 and by faculty research funds granted by the University of California, Santa Cruz.
The second author was supported in part by NSF Grant CCR-9113239.
Article copyright: © Copyright 1997 American Mathematical Society