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

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. 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 ${R}^k$, 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 ${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, 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.

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

Ron Goldman
Affiliation: Department of Computer Science, Rice University, Houston, Texas 77251-1892

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

American Mathematical Society