Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A unified approach to evaluation algorithms for multivariate polynomials
HTML articles powered by AMS MathViewer

by Suresh K. Lodha and Ron Goldman PDF
Math. Comp. 66 (1997), 1521-1553 Request permission

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
  • A. G. Aitken, On interpolation by iteration of proportional parts without the use of differences, Proceedings of Edinburgh Mathematical Society (1932), 56–76.
  • 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.
  • Phillip J. Barry, Ronald N. Goldman, and Tony D. DeRose, $B$-splines, Pólya curves, and duality, J. Approx. Theory 65 (1991), no. 1, 3–21. MR 1098828, DOI 10.1016/0021-9045(91)90109-N
  • W. Boehm, Inserting new knots into B-spline curves, Computer-Aided Design 12 (1980), 199–201.
  • J. Carnicer and M. Gasca, Evaluation of multivariate polynomials and their derivatives, Math. Comp. 54 (1990), no. 189, 231–243. MR 993925, DOI 10.1090/S0025-5718-1990-0993925-1
  • 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, DOI 10.1002/nme.3312
  • 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
  • K. C. Chung and T. H. Yao, On lattices admitting unique Lagrange interpolations, SIAM J. Numer. Anal. 14 (1977), no. 4, 735–743. MR 445158, DOI 10.1137/0714050
  • 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.
  • S. D. Conte and C. de Boor, Elementary numerical analysis, McGraw-Hill, New York, 1980, Third Edition.
  • Carl de Boor, A practical guide to splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York-Berlin, 1978. MR 507062, DOI 10.1007/978-1-4612-6333-3
  • Carl de Boor and Amos Ron, Computational aspects of polynomial interpolation in several variables, Math. Comp. 58 (1992), no. 198, 705–727. MR 1122061, DOI 10.1090/S0025-5718-1992-1122061-0
  • P. de Casteljau, Formes á pôles, Hermes, Paris, 1985.
  • Gerald Farin, Triangular Bernstein-Bézier patches, Comput. Aided Geom. Design 3 (1986), no. 2, 83–127. MR 867116, DOI 10.1016/0167-8396(86)90016-6
  • 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
  • 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, DOI 10.1016/0167-8396(91)90047-F
  • 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, DOI 10.1016/0167-8396(87)90012-4
  • 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, DOI 10.1016/0167-8396(88)90016-7
  • 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, DOI 10.1098/rspa.1968.0185
  • 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, DOI 10.1016/S0304-0208(08)71725-0
  • 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, DOI 10.1016/0021-9045(82)90078-8
  • M. Gasca and J. I. Maeztu, On Lagrange and Hermite interpolation in $\textbf {R}^{k}$, Numer. Math. 39 (1982), no. 1, 1–14. MR 664533, DOI 10.1007/BF01399308
  • 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
  • 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.
  • S. L. Lien, M. Shantz, and V. Pratt, Adaptive forward differencing for rendering curves and surfaces, Computer Graphics 21 (1987), 111–118.
  • S. K. Lodha and R. Goldman, Change of basis algorithms for surfaces in CAGD, Computer Aided Geometric Design 12 (1995), 801–824.
  • —, 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.
  • 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.
  • T. Lyche and K. Mørken, Making the Oslo algorithm more efficient, SIAM J. Numer. Anal. 23 (1986), no. 3, 663–675. MR 842650, DOI 10.1137/0723042
  • Martin J. Marsden, An identity for spline functions with applications to variation-diminishing spline approximation, J. Approximation Theory 3 (1970), 7–49. MR 254474, DOI 10.1016/0021-9045(70)90058-4
  • 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.
  • G. Mühlbach, A recurrence formula for generalized divided differences and some applications, J. Approximation Theory 9 (1973), 165–172. MR 353623, DOI 10.1016/0021-9045(73)90104-4
  • 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 356443, DOI 10.1002/zamm.19740540804
  • G. Mühlbach, The general Neville-Aitken-algorithm and some applications, Numer. Math. 31 (1978/79), no. 1, 97–110. MR 508591, DOI 10.1007/BF01396017
  • 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, DOI 10.1007/BF02251249
  • E. H. Neville, Iterative interpolation, Journal of Indiana Mathematical Society (1934), 87–120.
  • 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, DOI 10.1080/01630569208816462
  • J. Peters, Evaluation of the multivariate bernstein-bézier form on a regular lattice, ACM Transactions on Mathematical Software 20 (1994).
  • L. Ramshaw, Blossoming: A connect-the-dots approach to splines, Digital Systems Research Center, Report 19, Palo Alto, California., 1987.
  • Lyle Ramshaw, Blossoms are polar forms, Comput. Aided Geom. Design 6 (1989), no. 4, 323–358. MR 1030618, DOI 10.1016/0167-8396(89)90032-0
  • Larry L. Schumaker, Spline functions: basic theory, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1981. MR 606200
  • L. L. Schumaker and W. Volk, Efficient evaluation of multivariate polynomials, Computer Aided Geometric Design (1986), 1’49–154.
  • Hans-Peter Seidel, Symmetric recursive algorithms for surfaces: $B$-patches and the de Boor algorithm for polynomials over triangles, Constr. Approx. 7 (1991), no. 2, 257–279. MR 1101066, DOI 10.1007/BF01888157
  • Henry C. Thacher Jr. and W. E. Milne, Interpolation in several variables, J. Soc. Indust. Appl. Math. 8 (1960), 33–42. MR 117871, DOI 10.1137/0108004
  • W. Volk, An efficient raster evaluation method for univariate polynomials, Computing 40 (1988), no. 2, 163–173 (English, with German summary). MR 948792, DOI 10.1007/BF02247944
  • Wolfgang Volk, Making the difference interpolation method for splines more stable, J. Comput. Appl. Math. 33 (1990), no. 1, 53–59. MR 1081241, DOI 10.1016/0377-0427(90)90255-X
  • J. Warren, Creating rational multi-sided Bernstein-Bézier surfaces using base points, ACM Transactions on Graphics 11 (1992), no. 2, 127–139.
  • —, An efficient evaluation algorithm for polynomials in the Pólya basis, Computing 24 (1995), 1–5.
Similar Articles
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
  • 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.
  • © Copyright 1997 American Mathematical Society
  • 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