Recursive representation

 

• recursive representation is sparse representation with exponent ordering used to represent multivariate polynomials

• for recursive representation, an ordering of variables has to be chosen, e.g., alphabetically

• the variable which is chosen first in the ordering is called the main variable of the polynomial

• coefficients of the powers of the main variable will be polynomials in the other variables

• for simplicity, we will consider a polynomial in variables , with variable ordering so that the main variable is

  
  
  

• such a polynomial is represented by a list of pairs where each coefficient is a polynomial in and is represented by the list of pairs

• to distinquish a polynomial in from a polynomial in , we replace each pair of (exponent, coefficient) by the triple (variable, exponent, coefficient)

• the polynomial

  
  
  

  is then represented by the list ((x 3 ((y 2 1) (y 1 8))) (x 2 ((y 1 7) (y 0 3))) (x 1 ((y 1 5))) (x 0 4))