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 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.**Phillip J. Barry, Ronald N. Goldman, and Tony D. DeRose,*𝐵-splines, Pólya curves, and duality*, J. Approx. Theory**65**(1991), no. 1, 3–21. MR**1098828**, 10.1016/0021-9045(91)90109-N**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*, Math. Comp.**54**(1990), no. 189, 231–243. MR**993925**, 10.1090/S0025-5718-1990-0993925-1**6.**Jésus M. Carnicer and Mariano Gasca,*On the evaluation of multivariate Lagrange formulae*, Multivariate approximation theory, IV (Oberwolfach, 1989) Internat. Ser. Numer. Math., vol. 90, Birkhäuser, Basel, 1989, pp. 65–72. MR**1034296**, 10.1002/nme.3312**7.**A. S. Cavaretta and C. A. Micchelli,*Pyramid patches provide potential polynomial paradigms*, Mathematical methods in computer aided geometric design, II (Biri, 1991), Academic Press, Boston, MA, 1992, pp. 69–100. MR**1172796****8.**K. C. Chung and T. H. Yao,*On lattices admitting unique Lagrange interpolations*, SIAM J. Numer. Anal.**14**(1977), no. 4, 735–743. MR**0445158****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.**Carl de Boor,*A practical guide to splines*, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York-Berlin, 1978. MR**507062****12.**Carl de Boor and Amos Ron,*Computational aspects of polynomial interpolation in several variables*, Math. Comp.**58**(1992), no. 198, 705–727. MR**1122061**, 10.1090/S0025-5718-1992-1122061-0**13.**P. de Casteljau,*Formes á pôles*, Hermes, Paris, 1985.**14.**Gerald Farin,*Triangular Bernstein-Bézier patches*, Comput. Aided Geom. Design**3**(1986), no. 2, 83–127. MR**867116**, 10.1016/0167-8396(86)90016-6**15.**Gerald Farin,*Curves and surfaces for computer aided geometric design*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. A practical guide; With contributions by P. Bézier and W. Boehm. MR**974109****16.**R. T. Farouki,*On the stability of transformations between power and Bernstein polynomial forms*, Comput. Aided Geom. Design**8**(1991), no. 1, 29–36. MR**1089729**, 10.1016/0167-8396(91)90047-F**17.**R. T. Farouki and V. T. Rajan,*On the numerical condition of polynomials in Bernstein form*, Comput. Aided Geom. Design**4**(1987), no. 3, 191–216. MR**917780**, 10.1016/0167-8396(87)90012-4**18.**R. T. Farouki and V. T. Rajan,*Algorithms for polynomials in Bernstein form*, Comput. Aided Geom. Design**5**(1988), no. 1, 1–26. MR**945302**, 10.1016/0167-8396(88)90016-7**19.**M. Gasca,*Multivariate polynomial interpolation*, Computation of curves and surfaces (Puerto de la Cruz, 1989) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 307, Kluwer Acad. Publ., Dordrecht, 1990, pp. 215–236. MR**1064962**, 10.1098/rspa.1968.0185**20.**M. Gasca and E. Lebrón,*On Aitken-Neville formulae for multivariate interpolation*, Numerical approximation of partial differential equations (Madrid, 1985), North-Holland Math. Stud., vol. 133, North-Holland, Amsterdam, 1987, pp. 133–140. MR**899785**, 10.1016/S0304-0208(08)71725-0**21.**M. Gasca and A. López-Carmona,*A general recurrence interpolation formula and its applications to multivariate interpolation*, J. Approx. Theory**34**(1982), no. 4, 361–374. MR**656636**, 10.1016/0021-9045(82)90078-8**22.**M. Gasca and J. I. Maeztu,*On Lagrange and Hermite interpolation in 𝑅^{𝑘}*, Numer. Math.**39**(1982), no. 1, 1–14. MR**664533**, 10.1007/BF01399308**23.**Ronald N. Goldman and Phillip J. Barry,*Wonderful triangle: a simple, unified, algorithmic approach to change of basis procedures in computer aided geometric design*, Mathematical methods in computer aided geometric design, II (Biri, 1991), Academic Press, Boston, MA, 1992, pp. 297–320. MR**1172811****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. Mørken,*Making the Oslo algorithm more efficient*, SIAM J. Numer. Anal.**23**(1986), no. 3, 663–675. MR**842650**, 10.1137/0723042**30.**Martin J. Marsden,*An identity for spline functions with applications to variation-diminishing spline approximation*, J. Approximation Theory**3**(1970), 7–49. MR**0254474****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*, J. Approximation Theory**9**(1973), 165–172. MR**0353623****33.**G. Mühlbach,*Newton- und Hermite-Interpolation mit Čebyšev-Systemen*, Z. Angew. Math. Mech.**54**(1974), 541–550 (German, with English and Russian summaries). MR**0356443****34.**G. Mühlbach,*The general Neville-Aitken-algorithm and some applications*, Numer. Math.**31**(1978/79), no. 1, 97–110. MR**508591**, 10.1007/BF01396017**35.**G. Mühlbach,*On multivariate interpolation by generalized polynomials on subsets of grids*, Computing**40**(1988), no. 3, 201–215 (English, with German summary). MR**961123**, 10.1007/BF02251249**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*, Numer. Funct. Anal. Optim.**13**(1992), no. 1-2, 75–96. MR**1163319**, 10.1080/01630569208816462**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.**Lyle Ramshaw,*Blossoms are polar forms*, Comput. Aided Geom. Design**6**(1989), no. 4, 323–358. MR**1030618**, 10.1016/0167-8396(89)90032-0**41.**Larry L. Schumaker,*Spline functions: basic theory*, John Wiley & Sons, Inc., New York, 1981. Pure and Applied Mathematics; A Wiley-Interscience Publication. MR**606200****42.**L. L. Schumaker and W. Volk,*Efficient evaluation of multivariate polynomials*, Computer Aided Geometric Design (1986), 1'49-154.**43.**Hans-Peter Seidel,*Symmetric recursive algorithms for surfaces: 𝐵-patches and the de Boor algorithm for polynomials over triangles*, Constr. Approx.**7**(1991), no. 2, 257–279. MR**1101066**, 10.1007/BF01888157**44.**Henry C. Thacher Jr. and W. E. Milne,*Interpolation in several variables*, J. Soc. Indust. Appl. Math.**8**(1960), 33–42. MR**0117871****45.**W. Volk,*An efficient raster evaluation method for univariate polynomials*, Computing**40**(1988), no. 2, 163–173 (English, with German summary). MR**948792**, 10.1007/BF02247944**46.**Wolfgang Volk,*Making the difference interpolation method for splines more stable*, J. Comput. Appl. Math.**33**(1990), no. 1, 53–59. MR**1081241**, 10.1016/0377-0427(90)90255-X**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:
http://dx.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