most recent 30 from http://mathoverflow.net 2013-05-21T15:36:03Z http://mathoverflow.net/feeds/question/28459 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/28459/how-to-implement-horners-scheme-for-multivariate-polynomials gsreynolds 2010-06-17T04:27:48Z 2010-06-17T11:41:09Z

<h2>Background</h2> <p>I need to solve polynomials in multiple variables using <a href="http://en.wikipedia.org/wiki/Horner_scheme" rel="nofollow">Horner's scheme</a> 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.</p> <p>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.</p> <blockquote> <p>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 &amp; y.</p> </blockquote> <h2>Research</h2> <p>I've done my research and found a number of papers such as:<br> staff.ustc.edu.cn/~xinmao/ISSAC05/pages/bulletins/articles/147/hornercorrected.pdf<br> citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.8637&amp;rep=rep1&amp;type=pdf<br> www.is.titech.ac.jp/~kojima/articles/B-433.pdf </p> <h2>Problem</h2> <p>However, I'm not a mathematician or computer scientist, so I'm having trouble with the mathematics used to convey the algorithms and ideas.</p> <p>As far as I can tell the basic strategy is to turn a multivariate polynomial into separate univariate polynomials and compute it that way.</p> <p>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.</p>

http://mathoverflow.net/questions/28459/how-to-implement-horners-scheme-for-multivariate-polynomials/28490#28490 Joseph O'Rourke 2010-06-17T11:41:09Z 2010-06-17T11:41:09Z

<p>The paper you cite, "On the multivariate Horner scheme" (Pena, Sauer) has an explicit algorithm specified on p.3. The remaining challenge is to penetrate the notation and conventions in the paper laid out in the first three pages far enough to turn their algorithm presentation into code.</p> <p>It also seems that this paper (just reading the abstract) specifies an explicit algorithm: "Evaluation of Multivariate Polynomials and Their Derivatives," J. Carnicer and M. Gasca, <em>Mathematics of Computation</em>, Vol. 54, No. 189 (Jan., 1990), pp. 231-243.</p>