# How to implement Horner’s scheme for multivariate polynomials?

## 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
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.

-
Maybe you'd get more help on StackOverflow than here. –  Gerry Myerson Jun 17 '10 at 7:08