Remote Access Mathematics of Computation
Green Open Access

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?)

  • 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 ${R}^n$. Applications: construction of surfaces in ${R}^2$, 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.

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
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