Abstract
We present a stable and efficient Fortran implementation of polynomial interpolation at the Padua points on the square [ − 1,1]2. 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.
Supplemental Material
Available for Download
Software for Padua2D---Lagrange Interpolation at Padua Points on Bivariate Domains
- AMD 2006. AMD Core Math Library (ACML). Version 3.6.0. Available at http://developer.amd.com/acml.aspx.Google Scholar
- Bagby, T., Bos, L., and Levenberg, N. 2002. Multivariate simultaneous approximation. Constr. Approx. 18, 569--577.Google ScholarCross Ref
- Blackford, L. S., Demmel, J., Dongarra, J., Duff, I., Hammarling, S., Henry, G., Heroux, M., Kaufman, L., Lumsdaine, A., Petitet, A., Pozo, R., Remington, K., and Whaley, R. C. 2002. An updated set of basic linear algebra subprograms (BLAS). ACM Trans. Math. Softw. 28, 2, 135--151. Available at http://www.netlib.org/blas/. Google ScholarDigital Library
- Bojanov, B. and Xu, Y. 2003. On polynomial interpolation of two variables. J. Approx. Theory 120, 267--282. Google ScholarDigital Library
- 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.Google Scholar
- Bos, L., Caliari, M., De Marchi, S., Vianello, M., and Xu, Y. 2006b Bivariate Lagrange interpolation at the Padua points: the generating curve approach. J. Approx. Theory 143, 15--25. Google ScholarDigital Library
- Bos, L., De Marchi, S., Vianello, M., and Xu, Y. 2007. Bivariate Lagrange interpolation at the Padua points: the ideal theory approach. Numer. Math. 108, 1, 43--57. Google ScholarDigital Library
- 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.Google Scholar
- Caliari, M., De Marchi, S., and Vianello, M. 2007. Bivariate Lagrange interpolation at the Padua points: computational aspects. J. Comput. Appl. Math., available online 23 October 2007. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Carnicer, J. M., Gasca, M., and Sauer, T. 2006. Interpolation lattices in several variables. Numer. Math. 102, 559--581.Google ScholarDigital Library
- de Boor, C., Dyn, N., and Ron, A. 2000. Polynomial interpolation to data on flats in R d. J. Approx. Theory 105, 2, 313--343. Google ScholarDigital Library
- Dunkl, C. F. and Xu, Y. 2001. Orthogonal Polynomials of Several Variables. Encyclopedia of Mathematics and its Applications, vol. 81. Cambridge University Press, Cambridge.Google Scholar
- Franke, R. 1982. Scattered data interpolation: tests of some methods. Math. Comput. 38, 181--200.Google Scholar
- Gasca, M. and Sauer, T. 2000. Polynomial interpolation in several variables. Adv. Comput. Math. 12, 377--410.Google ScholarCross Ref
- Reimer, M. 2003. Multivariate Polynomial Approximation. International Series of Numerical Mathematics, vol. 144. Birkhäuser, Basel.Google Scholar
- Sauer, T. 1995. Computational aspects of multivariate polynomial interpolation. Adv. Comput. Math. 3, 219--238.Google ScholarDigital Library
- Xu, Y. 1996. Lagrange interpolation on Chebyshev points of two variables. J. Approx. Theory 87, 220--238. Google ScholarDigital Library
Index Terms
- Algorithm 886: Padua2D---Lagrange Interpolation at Padua Points on Bivariate Domains
Recommendations
Bivariate Lagrange interpolation at the node points of Lissajous curves - the degenerate case
In this article, we study bivariate polynomial interpolation on the node points of degenerate Lissajous figures. These node points form Chebyshev lattices of rank 1 and are generalizations of the well-known Padua points. We show that these node points ...
Bivariate Lagrange interpolation at the Padua points: Computational aspects
The so-called ''Padua points'' give a simple, geometric and explicit construction of bivariate polynomial interpolation in the square. Moreover, the associated Lebesgue constant has minimal order of growth O(log^2(n)). Here we show four families of ...
The application of Cayley-Bacharach theorem to bivariate Lagrange interpolation
Special issue on proceedings of the international symposium on computational mathematics and applicationsIn this paper, we give a new proof of the famous Cayley-Bacharach theorem by means of interpolation, and deduce a general method of constructing properly posed set of nodes for bivariate Lagrange interpolation. As a result, we generalize the main ...
Comments