LAGRANGE_ND
Multivariate Lagrange Interpolation

LAGRANGE_ND is a C++ library which is given a set of ND points X(*) in D-dimensional space, and constructs a family of ND Lagrange polynomials P(*)(X), associating polynomial P(i) with point X(i), such that, for 1 <= i <= ND,

        P(i)(X(i)) = 1
      

        P(i)(X(j)) = 0
      

The library currently includes the following primary routines:

• LAGRANGE_COMPLETE requires that the number of data points ND is exactly equal to R, the number of monomials in D dimensions of total degree N or less;
• LAGRANGE_COMPLETE2, a version of LAGRANGE_COMPLETE with improved "pivoting";
• LAGRANGE_PARTIAL allows the number of data points ND to be less than or equal to R, the number of monomials in D dimensions of total degree N or less;
• LAGRANGE_PARTIAL2, a version of LAGRANGE_PARTIAL with improved "pivoting".

The set of ND polynomials P(*)(X) are returned as a set of three arrays:

• PO(i) contains the order, the number of nonzero coefficients, for polynomial i;
• PC(i,j) contains the coefficient of the j-th term in polynomial i;
• PE(i,j) contains a code for the exponents of the monomial associated with the j-th term in polynomial i.

Each value of PE(i,j) is an exponent codes which can be converted to a vector of exponents that define a monomial. For example, if we are working in spatial dimension D=3, then if PE(i,j)=13, the corresponding exponent vector is (0,2,1), so this means that the j-th term in polynomial i is

        PC(i,j) * x^0 y^2 z^1
      

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

LAGRANGE_ND is available in a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

LAGRANGE_INTERP_ND, a C++ library which defines and evaluates the Lagrange polynomial p(x) which interpolates a set of multivariate data, so that p(x(i)) = y(i).

SPARSE_INTERP_ND a C++ library which can be used to define a sparse interpolant to a function f(x) of a multidimensional argument.

TEST_INTERP_ND, a C++ library which defines test problems for interpolation of data z(x), depending on an M-dimensional argument.

Reference:

1. Philip Davis,
   Interpolation and Approximation,
   Dover, 1975,
   ISBN: 0-486-62495-1,
   LC: QA221.D33
2. Tomas Sauer, Yuan Xu,
   On multivariate Lagrange interpolation,
   Mathematics of Computation,
   Volume 64, Number 211, July 1995, pages 1147-1170.

Source Code:

• lagrange_nd.cpp, the source code.
• lagrange_nd.hpp, the include file.

Examples and Tests:

• lagrange_nd_test.cpp, a sample calling program.
• lagrange_nd_test.txt, the output file.

List of Routines:

• I4_CHOOSE computes the binomial coefficient C(N,K).
• I4_MAX returns the maximum of two I4's.
• I4_MIN returns the minimum of two I4's.
• I4MAT_PRINT prints an I4MAT.
• I4MAT_PRINT_SOME prints some of an I4MAT.
• I4VEC_CONCATENATE concatenates two I4VEC's.
• I4VEC_PERMUTE permutes an I4VEC in place.
• I4VEC_PRINT prints an I4VEC.
• I4VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an I4VEC.
• I4VEC_SUM sums the entries of an I4VEC.
• LAGRANGE_COMPLETE: Complete Lagrange polynomial basis from data.
• LAGRANGE_COMPLETE2: Complete Lagrange polynomial basis from data.
• LAGRANGE_PARTIAL: Partial Lagrange polynomial basis from data.
• LAGRANGE_PARTIAL2: Partial Lagrange polynomial basis from data.
• MONO_BETWEEN_ENUM enumerates monomials in D dimensions of degrees in a range.
• MONO_BETWEEN_NEXT_GRLEX: grlex next monomial, degree between N1 and N2.
• MONO_NEXT_GRLEX returns the next monomial in grlex order.
• MONO_TOTAL_ENUM enumerates monomials in D dimensions of degree equal to N.
• MONO_TOTAL_NEXT_GRLEX: grlex next monomial with total degree equal to N.
• MONO_UNRANK_GRLEX computes the composition of given grlex rank.
• MONO_UPTO_ENUM enumerates monomials in D dimensions of degree up to N.
• MONO_VALUE evaluates a monomial.
• PERM_CHECK checks that a vector represents a permutation.
• POLYNOMIAL_AXPY adds a multiple of one polynomial to another.
• POLYNOMIAL_COMPRESS compresses a polynomial.
• POLYNOMIAL_PRINT prints a polynomial.
• POLYNOMIAL_SORT sorts the information in a polynomial.
• POLYNOMIAL_VALUE evaluates a polynomial.
• R8MAT_IS_IDENTITY determines if an R8MAT is the identity.
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• R8VEC_CONCATENATE concatenates two R8VEC's.
• R8VEC_PERMUTE permutes an R8VEC in place.
• R8VEC_PRINT prints an R8VEC.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.