POLYNOMIAL
Multivariate Polynomials

POLYNOMIAL, a C library which adds, multiplies, differentiates, evaluates and prints multivariate polynomials in a space of M dimensions.

Any polynomial in M variables can be written as a linear combination of monomials in M variables. The "total degree" of the polynomial is the maximum of the degrees of the monomials that it comprises. For instance, a polynomial in M = 2 variables of total degree 3 might have the form:

        p(x,y) = c(0,0) x^0 y^0
               + c(1,0) x^1 y^0 + c(0,1) x^0 y^1 
               + c(2,0) x^2 y^0 + c(1,1) x^1 y^1 + c(0,2) x^0 y^2
               + c(3,0) x^3 y^0 + c(2,1) x^2 y^1 + c(1,2) x^1 y^2 + c(0,3) x^0 y^3

The monomials in M variables can be regarded as a natural basis for the polynomials in M variables.

When listing the monomials that form a polynomial, it is useful to have an ordering that organizes them. One natural ordering can be illustrated for the 3-dimensional case:

        1
        x, y, z
        x^2, xy, xz, y^2, yz, z^2
        x^3, x^2y, x^2z, xy^2, xyz, xz^2, y^3, y^2z, yz^2, z^3
        x^4, x^3y, ...

Here, a monomial precedes another if it has a lower degree. If the monomials have the same degree, then a monomial precedes another if its exponent vector lexically precedes that of the other. In other words, we compare the two exponent vectors, reading from left to right, looking for the first location where the exponents differ. The monomial with the higher exponent at this point precedes the other.

Licensing:

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

Languages:

POLYNOMIAL is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

COMBO, a C library which includes routines for ranking, unranking, enumerating and randomly selecting balanced sequences, cycles, graphs, Gray codes, subsets, partitions, permutations, restricted growth functions, Pruefer codes and trees.

HERMITE_PRODUCT_POLYNOMIAL, a C library which defines Hermite product polynomials, creating a multivariate polynomial as the product of univariate Hermite polynomials.

LEGENDRE_PRODUCT_POLYNOMIAL, a C library which defines Legendre product polynomials, creating a multivariate polynomial as the product of univariate Legendre polynomials.

MONOMIAL, a C library which enumerates, lists, ranks, unranks and randomizes multivariate monomials in a space of M dimensions, with total degree less than N, equal to N, or lying within a given range.

SET_THEORY, a C library which demonstrates MATLAB commands that implement various set theoretic operations.

SUBSET, a C library which enumerates, generates, ranks and unranks combinatorial objects including combinations, compositions, Gray codes, index sets, partitions, permutations, subsets, and Young tables.

Source Code:

polynomial.c, the source code.
polynomial.h, the include file.

Examples and Tests:

polynomial_test.c, a sample calling program.
polynomial_test.txt, the output file.

List of Routines:

I4_CHOOSE computes the binomial coefficient C(N,K).
I4_FALL computes the falling factorial function [X]_N.
I4_MAX returns the maximum of two I4's.
I4_MIN returns the smaller of two I4's.
I4VEC_CONCATENATE concatenates two I4VEC's.
I4VEC_PERMUTE permutes an I4VEC in place.
I4VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an I4VEC.
I4VEC_SUM sums the entries of an I4VEC.
MONO_NEXT_GRLEX returns the next monomial in grlex order.
MONO_RANK_GRLEX computes the graded lexicographic rank of a monomial.
MONO_TOTAL_NEXT_GRLEX: grlex next monomial with total degree equal to N.
MONO_UNRANK_GRLEX computes the monomial 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_ADD adds two polynomials.
POLYNOMIAL_AXPY adds a multiple of one polynomial to another.
POLYNOMIAL_COMPRESS compresses a polynomial.
POLYNOMIAL_DIF differentiates a polynomial.
POLYNOMIAL_MUL multiplies two polynomials.
POLYNOMIAL_PRINT prints a polynomial.
POLYNOMIAL_SCALE scales a polynomial.
POLYNOMIAL_SORT sorts the information in a polynomial.
POLYNOMIAL_VALUE evaluates a polynomial.
R8VEC_CONCATENATE concatenates two R8VEC's.
R8VEC_PERMUTE permutes an R8VEC in place.
TIMESTAMP prints the current YMDHMS date as a time stamp.

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

Last modified on 01 January 2014.