Polynomial Types

Polynomials can be classified by the number of variables and their maximum exponents. They can also be classified by their sparsity.

Monomial / Term

• A polynomial that only has one term
• $deg(P)$ = exponent of the monomial
• e.g. for $P(x)=1+x+4x_2^5$
  • $1$, $x$ and $4x^5$ are all monomials
  • $deg(x)=1$

Univariate Polynomial

• standard monomial basis
• $P(X)=\sum _{i=0}^d{c}_i\cdot X^i$ where $deg(P)=d$
• $deg(P)$ = highest exponent
• e.g. $P(x)=1+x+4x^5$
  • $deg(P)=5$ because $5$ is the highest exponent

Multilinear Polynomial

• A multivariate polynomial that is linear (i.e. affine) in each of its variables separately but not necessarily simultaneously
• $deg(P)=$ maximum number of variables in any monomial
• $size(P)=2^k$
  • number of monomials/coefficients, including 0
  • where $k$ is the number of variables
• e.g. $P(x,y,z)=3+4x+5y+5xy+z$
  • $deg(P)=2$ because of $5xy$
  • $size(P)=2^3$

Multivariate Polynomial

• A multivariate polynomial that is non-linear in each of the variables
• $TotalDeg(P)=$ maximum degree of all terms
• $size(P)=(d+1{)}^k$
  • Size is the number of monomials/coefficients, including 0
  • where: $k$ is the number of variables, $d$ is the total degree
  • thus $k=log(N)$
• e.g. $P(x1,x2,x3)=x_1{x}_2^2+3x_1{x}_2+4x_2^5$
  • $TotalDeg(P)=5$ because of $4x_2^5$
  • $size(P)=(5+1{)}^2$

Sparsity

Sparse vs Dense

Mathematically

• Mathematically, the two types are not clearly defined
• Sparse: when most of the coefficients of its monomials are zero
• Dense: most of the coefficients of its monomials are non-zero

Computer Science

• In computer science, the two types are clearly defined
• Sparse:
  • zero coefficients: not stored
  • exponents: stored explicitly
• Dense:
  • zero coefficients: stored explicitly
  • exponents: not stored