LAGRANGE_ND
Multivariate Lagrange Interpolation

LAGRANGE_ND, a MATLAB 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 MATLAB library which defines and evaluates the Lagrange polynomial p(x) which interpolates a set of multivariate data, so that p(x(i)) = y(i).

lagrange_nd_test

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

SPINTERP, a MATLAB library which carries out piecewise multilinear hierarchical sparse grid interpolation; an earlier version of this software is ACM TOMS Algorithm 847, by Andreas Klimke;

TEST_INTERP_ND, a MATLAB 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:

• comp_unrank_grlex.m, computes the composition of given grlex rank.
• i4_choose.m, computes the binomial coefficient C(N,K) as an I4;
• i4mat_print.m, prints an I4MAT;
• i4mat_print_some.m, prints some of an I4MAT;
• i4vec_print.m, prints an I4VEC;
• interpolant_value.m, evaluates a Lagrange intepolant.
• lagrange_complete.m, Lagrange polynomial basis from data, spans complete polynomial space, uses very weak pivoting strategy.
• lagrange_complete2.m, Lagrange polynomial basis from data, spans complete polynomial space, uses improved pivoting strategy.
• lagrange_partial.m, Lagrange polynomial basis from data, spans partial polynomial space, uses very weak pivoting strategy.
• lagrange_partial2.m, Lagrange polynomial basis from data, spans partial polynomial space, uses improved pivoting strategy.
• lagrange_partial3.m, Lagrange polynomial basis from data, spans partial polynomial space, uses improved pivoting strategy, increases polynomial degree as necessary.
• lagrange_partial4.m, used by lagrange_partial3.
• lp_coefficients.m, returns the coefficients of a Legendre polynomial
• lpp_to_polynomial.m, converts a Legendre Product Polynomial to standard polynomial form.
• mono_between_enum.m, enumerates the monomials of D variables of total degree between N1 and N2, inclusive.
• mono_between_next_grlex.m, computes, one by one, the monomials of D variables of total degree between N1 and N2, inclusive, using graded lexicographic ordering.
• mono_next_grlex.m, returns the next monomial in the graded lexicographic ordering.
• mono_rank_grlex.m, returns the grlex rank of a monomial in the sequence of all monomials in D dimensions of degree N or less.
• mono_total_enum.m, enumerates the monomials of D variables of total degree N.
• mono_total_next_grlex.m, returns the next monomial of total degree N in the graded lexicographic ordering.
• mono_unrank_grlex.m, returns the monomial of the given rank in the graded lexicographic ordering.
• mono_upto_enum.m, enumerates the monomials of D variables of total degree 0 up to N.
• mono_value.m, evaluates a monomial.
• polynomial_axpy.m, adds a multiple of one polynomial to another.
• polynomial_compress.m, "compresses" a polynomial by merging coefficients associated with the same monomial.
• polynomial_print.m, prints a polynomial.
• polynomial_sort.m, sorts the terms in a polynomial.
• polynomial_value.m, evaluates a polynomial.
• r8col_separation.m, computes the separation between columns of an R8COL.
• r8mat_print.m, prints an R8MAT;
• r8mat_print_some.m, prints some of an R8MAT;
• r8mat_transpose_print.m, prints an R8MAT, transposed;
• r8mat_transpose_print_some.m, prints some of an R8MAT, transposed;
• r8vec_print.m, prints an R8VEC;
• timestamp.m, prints the YMDHMS date as a timestamp.