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

DOI:
https://doi.org/10.1090/S0025-5718-97-00862-4

MathSciNet review:
1422789

Full-text PDF

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 in variables, the class of up recursive evaluation algorithms includes a parallel up recurrence algorithm with computational complexity , a nested multiplication algorithm with computational complexity and a ladder recurrence algorithm with computational complexity . 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 , a divided difference algorithm, a forward difference algorithm, and a Lagrange evaluation algorithm with computational complexities , and per point respectively for the evaluation of multivariate polynomials at several points.

**1.**A. G. Aitken,*On interpolation by iteration of proportional parts without the use of differences*, Proceedings of Edinburgh Mathematical Society (1932), 56-76.**2.**P. Barry and R. Goldman,*Algorithms for progressive curves: Extending B-spline and blossoming techniques to the monomial, power, and Newton dual bases*, Knot Insertion and Deletion Algorithms for B-Spline Curves and Surfaces (R. Goldman and T. Lyche, eds.), SIAM, 1993, pp. 11-64. CMP**93:11****3.**P. Barry, R. Goldman, and T. DeRose,*B-splines, Pólya curves and duality*, Journal of Approximation Theory**65**(1991), no. 1, 3-21. MR**92f:41018****4.**W. Boehm,*Inserting new knots into B-spline curves*, Computer-Aided Design**12**(1980), 199-201.**5.**J. Carnicer and M. Gasca,*Evaluation of multivariate polynomials and their derivatives*, Mathematics of Computation**54**(1990), no. 189, 231-243. MR**90h:12001****6.**-,*On the evaluation of multivariate Lagrange formulae*, Proceedings of the Conference Mehrdimensionale Knostruktive Funktiontheorie, Oberwalch, Birkhauser Verlag, 1990, pp. 65-72. MR**91c:65014****7.**A. S. Cavaretta and C. A. Micchelli,*Pyramid patches provide potential polynomial paradigms*, Mathematical Methods in CAGD and Image Processing (T. Lyche and L. L. Schumaker, eds.), Academic Press, 1992, pp. 1-40. MR**93h:65023****8.**C. K. Chung and T. H. Yao,*On lattices admitting unique Lagrange interpolations*, Siam Journal on Numerical Analysis**14**(1977), 735-743. MR**56:3502****9.**E. Cohen, T. Lyche, and R. F. Riesenfeld,*Discrete B-splines and subdivision techniques in computer-aided geometric design and computer graphics*, Computer Graphics and Image Processing**14**(1980), 87-111.**10.**S. D. Conte and C. de Boor,*Elementary numerical analysis*, McGraw-Hill, New York, 1980, Third Edition.**11.**C. de Boor,*A practical guide to splines*, Springer Verlag, New York, 1978, Applied Mathematical Sciences, Volume 27. MR**80a:65027****12.**C. de Boor and Amos Ron,*Computational aspects of polynomial interpolation in several variables*, Mathematics of Computation (1992), 705-727. MR**92i:65022****13.**P. de Casteljau,*Formes á pôles*, Hermes, Paris, 1985.**14.**G. Farin,*Triangular Bernstein-Bézier patches*, Computer Aided Geometric Design**3**(1986), no. 2, 83-128. MR**87k:65014****15.**-,*Curves and surfaces for computer aided geometric design: A practical guide*, Academic Press Inc., New York, 1988. MR**90c:65014****16.**R. Farouki,*On the stability of transformations between power and Bernstein form*, Computer Aided Geometric Design (1991), no. 1, 29-36. MR**91m:65042****17.**R. Farouki and V. Rajan,*On the numerical condition of polynomials in Bernstein form*, Computer Aided Geometric Design**4**(1987), 191-216. MR**89a:65028****18.**-,*Algorithms for polynomials in Bernstein form*, Computer Aided Geometric Design**5**(1988), no. 1, 1-26. MR**89c:65033****19.**M. Gasca,*Multivariate polynomial interpolation*, Computation of Curves and Surfaces (W. Dahmen, M. Gasca, and C. A. Micchelli, eds.), Kluwer Academic Publishers, 1990, pp. 215-236. MR**91k:65028****20.**M. Gasca and E. Lebrón,*On Aitken-Neville formulae for multivariate interpolation*, Numerical Approximation of Partial Differential Equations, Elsevier Science Publication, North Holland, 1987, pp. 133-140. MR**89b:41005****21.**M. Gasca and A. López-Carmona,*A general recurrence interpolation formula and its applications to multivariate interpolation*, Journal of Approximation Theory (1982), 361-374. MR**83f:41003****22.**M. Gasca and J. I. Maeztu,*On Lagrange and Hermite interpolation in*, Numer. Math.**39**(1989), 1-14. MR**83g:65012****23.**R. N. Goldman and P. J. Barry,*Wonderful triangle: A simple, unified, algorithmic approach to change of basis procedures in computer aided geometric design*, Mathematical Methods in CAGD II (T. Lyche and L. Schumaker, eds.), Academic Press, 1992, pp. 297-320. MR**93e:65027****24.**A. Habib, R. Goldman, and T. Lyche,*A recursive algorithm for Hermite interpolation over a triangular grid*, Journal of Computational and Applied Mathematics**73**(1996), 95-118.**25.**S. L. Lien, M. Shantz, and V. Pratt,*Adaptive forward differencing for rendering curves and surfaces*, Computer Graphics**21**(1987), 111-118.**26.**S. K. Lodha and R. Goldman,*Change of basis algorithms for surfaces in CAGD*, Computer Aided Geometric Design**12**(1995), 801-824. CMP**96:04****27.**-,*Lattices and algorithms for bivariate Bernstein, Lagrange, Newton and other related polynomial bases based on duality between L-bases and B-bases*, University of California, Santa Cruz, CA, UCSC-CRL-95-14, Submitted for publication, 1995.**28.**S. K. Lodha, R. Goldman, and J. Warren,*A ladder recurrence algorithm for the evaluation of L-patches*, Annals of Numerical Mathematics**3**(1996), 209-220. CMP**96:14****29.**T. Lyche and K. Morken,*Making the Oslo algorithm more efficient*, SIAM Journal of Numerical Analysis (1986), 663-675. MR**87m:65031****30.**M. J. Marsden,*An identity for spline functions with applications to variation-diminishing spline approximation*, Journal of Approximation Theory**3**(1970), 7-49. MR**40:7682****31.**A. Le Méhauté,*Approximation of derivatives in . Applications: construction of surfaces in*, Multivariate Approximation (S. P. Singh, J. H. W. Burry, and B. Watson, eds.), Reidel, 1984, pp. 361-378. CMP**17:12****32.**G. Mühlbach,*A recurrence formula for generalized divided differences and some applications*, Journal of Approximation Theory**9**(1973), 165-172. MR**50:6106****33.**-,*Newton and Hermite interpolation mit Cebysev-systemen*, Z. Angew. Math. Mech.**50**(1974), 97-110. MR**50:8913****34.**-,*The general Neville-Aitken algorithm and some applications*, Numerische Mathematik**31**(1978), 97-110. MR**80a:65025****35.**-,*On multivariate interpolation by generalized polynomials in subsets of grids*, Computing**40**(1988). MR**90c:65020****36.**E. H. Neville,*Iterative interpolation*, Journal of Indiana Mathematical Society (1934), 87-120.**37.**G. Nürnberger and Th. Riessinger,*Lagrange and Hermite interpolation by bivariate splines*, Numerical Functional Analysis and Optimization**13**(1992), no. 1, 75-96. MR**93f:41048****38.**J. Peters,*Evaluation of the multivariate bernstein-bézier form on a regular lattice*, ACM Transactions on Mathematical Software**20**(1994). CMP**96:06****39.**L. Ramshaw,*Blossoming: A connect-the-dots approach to splines*, Digital Systems Research Center, Report 19, Palo Alto, California., 1987.**40.**-,*Blossoms are polar forms*, Computer Aided Geometric Design**6**(1989), 323-358. MR**91d:65026****41.**L. L. Schumaker,*Spline functions: Basic theory*, John Wiley, New York, 1981. MR**82j:41001****42.**L. L. Schumaker and W. Volk,*Efficient evaluation of multivariate polynomials*, Computer Aided Geometric Design (1986), 1'49-154.**43.**H. P. Seidel,*Symmetric recursive algorithms for surfaces: B-patches and the de Boor algorithm for polynomials over triangles*, Constructive Approximation**7**(1991), 259-279. MR**92c:41010****44.**H. C. Jr. Thacher and W. E. Milne,*Interpolation in several variables*, J. SIAM (1960), 33-42. MR**22:8645****45.**W. Volk,*An efficient raster evaluation method for univariate polynomials*, Computing**40**(1988), 163-173. MR**89f:65029****46.**-,*Making the difference interpolation method for splines more stable*, J. of Computing and Applied Mathematics**33**(1990), 53-59. MR**92a:65047****47.**J. Warren,*Creating rational multi-sided Bernstein-Bézier surfaces using base points*, ACM Transactions on Graphics**11**(1992), no. 2, 127-139.**48.**-,*An efficient evaluation algorithm for polynomials in the Pólya basis*, Computing**24**(1995), 1-5.

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:
https://doi.org/10.1090/S0025-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