How to implement Horner's scheme for multivariate polynomials?

Posted by gsreynolds on Stack Overflow See other posts from Stack Overflow or by gsreynolds
Published on 2010-06-16T22:59:55Z Indexed on 2010/06/17 4:33 UTC
Read the original article Hit count: 265

Filed under:

fortran

|

polynomial-math

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.

© Stack Overflow or respective owner

Related posts about fortran

passing a fortran int array to C++ by calling C++ function in fortran

as seen on Stack Overflow - Search for 'Stack Overflow'
hi, I am trying to call a C++ function in FORTRAN subroutine. This C+ function is supposed to update an integer array. Here is a non-working code I wrote. Can someone please let me know what the issue is: ! FORTRAN function that calls a C++ function subroutine my_function() integer(4) ar(*) … >>> More
MinGW/G++/g95 link problem - libf95 undefined reference to `MAIN_'

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi folks, Summing up, my problem consists on compiling g95 objects inside a C++ application. Actually, I'm constructing an interface for an old fortran program. For this task, I'm using the wxWidgets GUI library, and calling fortran subroutines when necessary. At the beginning, I was developing the… >>> More
Fortran arrays and subroutines

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm going through a Fortran code, and one bit has me a little puzzled. There is a subroutine, say SUBROUTINE SSUB(X,...) REAL*8 X(0:N1,1:N2,0:N3-1),... ... RETURN END Which is called in another subroutine by: CALL SSUB(W(0,1,0,1),...) where W is a 'working array'. It appears that a specific… >>> More
fortran 90 user defined type, passing by value ?

as seen on Stack Overflow - Search for 'Stack Overflow'
I have an issue in fortran 90. I have a user defined type and when I call one of the MPI subroutines the data looks to be passed by values (not address, as I thought it should). The output arguments aren't modified. It seems to be specific to the MPI calls I tried the same thing in a simple test… >>> More
Should External Routine Be Declared Always in Fortran?

as seen on Stack Overflow - Search for 'Stack Overflow'
In my fortran code I made the following call to dnrm2 routine d = dnrm2(n, ax, 1) Just a simple call that would return me a double precision result. The problem is whether I should declare the function at the start of my script. I found that if I don't declare it, and when I compile the code in… >>> More

Related posts about polynomial-math

Algorithm for computing the inverse of a polynomial

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm looking for an algorithm (or code) to help me compute the inverse a polynomial, I need it for implementing NTRUEncrypt. An algorithm that is easily understandable is what I prefer, there are pseudo-codes for doing this, but they are confusing and difficult to implement, furthermore I can not really… >>> More
polynomial surface fit numpy

as seen on Stack Overflow - Search for 'Stack Overflow'
I have had that problem before and I couldn't solve it how do I fit a 2d surface z=f(x,y) with a polynomial in numpy (full crossterms). Thanks in advance, Wolfgang >>> More
Modular Reduction of Polynomials in NTRUEncrypt

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello everyone. I'm implementing the NTRUEncrypt algorithm, according to an NTRU tutorial, a polynomial f has an inverse g such that f*g=1 mod x, basically the polynomial multiplied by its inverse reduced modulo x gives 1. I get the concept but in an example they provide, a polynomial f = -1 + X… >>> More
NTRU Pseudo-code for computing Polynomial Inverses

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello all. I was wondering if anyone could tell me how to implement line 45 of the following pseudo-code. Require: the polynomial to invert a(x), N, and q. 1: k = 0 2: b = 1 3: c = 0 4: f = a 5: g = 0 {Steps 5-7 set g(x) = x^N - 1.} 6: g[0] = -1 7: g[N] = 1 8: loop 9: while f[0] = 0 do 10: … >>> More
Polynomial operations using operator overloading

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to use operator overloading to define the basic operations (+,-,*,/) for my polynomial class but when i run the program it crashes and my computer frozes. Update3 Ok i successfully done the first two operations(+,-). Now at multiplication, after multiplying each term of the first polynomial… >>> More