Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a stable and efficient Fortran implementation of polynomial interpolation at the Padua points on the square [ − 1,1]². These points are unisolvent and their Lebesgue constant has minimal order of growth (log square of the degree). The algorithm is based on the representation of the Lagrange interpolation formula in a suitable orthogonal basis, and takes advantage of a new matrix formulation together with the machine-specific optimized BLAS subroutine for the matrix-matrix product. Extension to interpolation on rectangles, triangles and ellipses is also described.

REFERENCES

• 1: AMD 2006. AMD Core Math Library (ACML). Version 3.6.0. Available at http://developer.amd.com/acml.aspx.
• 2: Bagby, T., Bos, L., and Levenberg, N. 2002. Multivariate simultaneous approximation. Constr. Approx. 18, 569--577.
• 3: An updated set of basic linear algebra subprograms (BLAS), ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.135-151, June 2002 [doi>10.1145/567806.567807]
• 4: Borislav Bojanov , Yuan Xu, On polynomial interpolation of two variables, Journal of Approximation Theory, v.120 n.2, p.267-282, 01 February 2003 [doi>10.1016/S0021-9045(02)00023-0]
• 5: Bos, L., Caliari, M., De Marchi, S., and Vianello, M. 2006a. Bivariate interpolation at Xu points: results, extensions and applications. Electron. Trans. Numer. Anal. 25, 1--16.
• 6: Len Bos , Marco Caliari , Stefano De Marchi , Marco Vianello , Yuan Xu, Bivariate Lagrange interpolation at the Padua points: The generating curve approach, Journal of Approximation Theory, v.143 n.1, p.15-25, November, 2006 [doi>10.1016/j.jat.2006.03.008]
• 7: Len Bos , Stefano De Marchi , Marco Vianello , Yuan Xu, Bivariate Lagrange interpolation at the Padua points: the ideal theory approach, Numerische Mathematik, v.108 n.1, p.43-57, October 2007 [doi>10.1007/s00211-007-0112-z]
• 8: Caliari, M., De Marchi, S., and Vianello, M. 2005. Bivariate polynomial interpolation on the square at new nodal sets. Appl. Math. Comput. 165, 2, 261--274.
• 9: Marco Caliari , Stefano De Marchi , Marco Vianello, Bivariate Lagrange interpolation at the Padua points: Computational aspects, Journal of Computational and Applied Mathematics, v.221 n.2, p.284-292, November, 2008 [doi>10.1016/j.cam.2007.10.027]
• 10: Caliari, M., Vianello, M., De Marchi, S., and Montagna, R. 2006. HYPER2D: a numerical code for hyperinterpolation at Xu points on rectangles. Appl. Math. Comput. 183, 1138--1147.
• 11: Carnicer, J. M., Gasca, M., and Sauer, T. 2006. Interpolation lattices in several variables. Numer. Math. 102, 559--581.
• 12: Carl de Boor , Nira Dyn , Amos Ron, Polynomial interpolation to data on flats in R^d , Journal of Approximation Theory, v.105 n.2, p.313-343, Aug. 2000 [doi>10.1006/jath.2000.3473]
• 13: Dunkl, C. F. and Xu, Y. 2001. Orthogonal Polynomials of Several Variables. Encyclopedia of Mathematics and its Applications, vol. 81. Cambridge University Press, Cambridge.
• 14: Franke, R. 1982. Scattered data interpolation: tests of some methods. Math. Comput. 38, 181--200.
• 15: Gasca, M. and Sauer, T. 2000. Polynomial interpolation in several variables. Adv. Comput. Math. 12, 377--410.
• 16: Reimer, M. 2003. Multivariate Polynomial Approximation. International Series of Numerical Mathematics, vol. 144. Birkhäuser, Basel.
• 17: Sauer, T. 1995. Computational aspects of multivariate polynomial interpolation. Adv. Comput. Math. 3, 219--238.
• 18: Yuan Xu, Lagrange interpolation on Chebyshev points of two variables, Journal of Approximation Theory, v.87 n.2, p.220-238, Nov. 1996 [doi>10.1006/jath.1996.0102]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
      G.1.2 Approximation
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms

Keywords:
Bivariate Lagrange interpolation, Fortran 77, Padua points, bivariate Chebyshev orthogonal basis