Univariate polynomial evaluation

  • The evaluation of 1-D polynomials uses Horner’s algorithm.

  • The evaluation of 1-D Chebyshev and Legendre polynomials uses Clenshaw’s algorithm.

Multivariate polynomial evaluation

  • Multivariate Polynomials are evaluated following the algorithm in 1 . The algorithm uses the following notation:

    • multiindex is a tuple of non-negative integers for which the length is defined in the following way:

      \[\alpha = (\alpha1, \alpha2, \alpha3), |\alpha| = \alpha1+\alpha2+\alpha3\]
    • inverse lexical order is the ordering of monomials in such a way that \({x^a < x^b}\) if and only if there exists \({1 \le i \le n}\) such that \({a_n = b_n, \dots, a_{i+1} = b_{i+1}, a_i < b_i}\).

      In this ordering \(y^2 > x^2*y\) and \(x*y > y\)

    • Multivariate Horner scheme uses d+1 variables \(r_0, ...,r_d\) to store intermediate results, where d denotes the number of variables.


      1. Set di to the max number of variables (2 for a 2-D polynomials).

      2. Set \(r_0\) to \(c_{\alpha(0)}\), where c is a list of coefficients for each multiindex in inverse lexical order.

      3. For each monomial, n, in the polynomial:

        • determine \(k = max \{1 \leq j \leq di: \alpha(n)_j \neq \alpha(n-1)_j\}\)

        • Set \(r_k := l_k(x)* (r_0 + r_1 + \dots + r_k)\)

        • Set \(r_0 = c_{\alpha(n)}, r_1 = \dots r_{k-1} = 0.\)

      4. return \(r_0 + \dots + r_{di}\)

  • The evaluation of multivariate Chebyshev and Legendre polynomials uses a variation of the above Horner’s scheme, in which every Legendre or Chebyshev function is considered a separate variable. In this case the length of the \(\alpha\) indices tuple is equal to the number of functions in x plus the number of functions in y. In addition the Chebyshev and Legendre functions are cached for efficiency.

    1. Pena, Thomas Sauer, “On the Multivariate Horner Scheme”, SIAM Journal on Numerical Analysis, Vol 37, No. 4