How to implement Horner's scheme for multivariate polynomials?

Question

Background

I need to solve polynomials in multiple variables using Horner's scheme in Fortran90/95. The main reason for doing this is the increased efficiency and accuracy that occurs when using Horner's scheme to evaluate polynomials.

I currently have an implementation of Horner's scheme for univariate/single variable polynomials. However, developing a function to evaluate multivariate polynomials using Horner's scheme is proving to be beyond me.

An example bivariate polynomial would be: 12x^2y^2+8x^2y+6xy^2+4xy+2x+2y which would factorised to x(x(y(12y+8))+y(6y+4)+2)+2y and then evaluated for particular values of x & y.

Research

I've done my research and found a number of papers such as:
staff.ustc.edu.cn/~xinmao/ISSAC05/pages/bulletins/articles/147/hornercorrected.pdf
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.8637&rep=rep1&type=pdf
www.is.titech.ac.jp/~kojima/articles/B-433.pdf

Problem

However, I'm not a mathematician or computer scientist, so I'm having trouble with the mathematics used to convey the algorithms and ideas.

As far as I can tell the basic strategy is to turn a multivariate polynomial into separate univariate polynomials and compute it that way.

Can anyone help me? If anyone could help me turn the algorithms into pseudo-code that I can implement into Fortran myself, I would be very grateful.

Saloma

This sounds like MathOverflow material. Too bad we can't migrate there. – Landonlandor

Answer 1

For two variables one can store the polynomial coefficients in a rank=2 matrix K(n+1,n+1) where n is the order of the polynomial. Then observe the following pattern (in pseudo-code)

p(x,y) =     (K(1,1)+y*(K(1,2)+y*(K(1,3)+...y*K(1,n+1))) +
           x*(K(2,1)+y*(K(2,2)+y*(K(2,3)+...y*K(2,n+1))) +
         x^2*(K(3,1)+y*(K(3,2)+y*(K(3,3)+...y*K(3,n+1))) +
         ...
         x^n*(K(n+1,1)+y*(K(n+1,2)+y*(K(n+1,3)+...y*K(n+1,n+1)))

Each row is a separate homer's scheme in terms of y and all-together is a final homer's scheme in terms of x.

To code in FORTRAN or any language create an intermediate vector z(n+1) such that

z(i) = homers(y,K(i,1:n+1))

and

p = homers(x,z(1:n+1))

where homers(value,vector) is an implementation of the single variable evaluation with polynomial coefficients stored in vector.

Barbiturism