Polynomial division is dangerous!

[Jim Fox]

I suspect that everyone does polynomial division the same way, the way we learned in high school. However, this can lead to large exponentially increasing errors. Problems will occur if the denominator has a large magnitude root and the quotient is long. For example, if 1000 is a root of a long polynomial and it is deflated, expect large errors. If the polynomial has high enough degree, expect infinity at some point in the deflated polynomial.

 

For an explanation of why this occurs and what you can do about it see:

cnx.org/content/m43398/latest/, "Exponential errors in polynomial evaluation, deflation, & division"

P.S. Understanding this article is helped immensely if you know the program Matlab.

 

While you are there, you might check out my other article:

cnx.org/content/m15595/latest/, "Information in the Spectrum of the Polynomial Coefficients"

 

Both articles are posted on Connexions which is a project of Rice University. Connexions allows anyone to publish, on the web, anything about any subject. There are no referees to shoot down your paper. Your paper does not need to be new information. If you feel that you are knowledgeable about some well researched subject, then write a summary paper. Connections will publish it for you on the web. Connexions makes it easy for anyone to become a published author. Do you have a paper in you?

Edited March 18, 2012 by Jim Fox

[mathematic]

Are you discussing this in the context of doing it on a computer?

[DrRocket]

Connexions allows anyone to publish, on the web, anything about any subject. There are no referees to shoot down your paper. Your paper does not need to be new information. If you feel that you are knowledgeable about some well researched subject, then write a summary paper. Connections will publish it for you on the web. Connexions makes it easy for anyone to become a published author. Do you have a paper in you?

 

It you call that "published" then you are in need of much higher standards. If an organ publishes anything then nothing that it publishes can be assumed to be of value without a good deal more research into what the paper says.

 

There is a reason that high-value scientific papers are publilshed in peer-reviewed journals with high standards and a high rejection rate.

[Jim Fox]

Are you discussing this in the context of doing it on a computer?

 

Yes indeed. If all your coefficients are integers, you are safe. You will only have problems if the coefficients are 16 digit numbers that can experience round off error when they are manipulated on the computer.

 

It you call that "published" then you are in need of much higher standards. If an organ publishes anything then nothing that it publishes can be assumed to be of value without a good deal more research into what the paper says.

 

There is a reason that high-value scientific papers are publilshed in peer-reviewed journals with high standards and a high rejection rate.

Indeed, peer reviewed journals are the gold standard of publishing. However, if a university puts something out on the web, I do not know what you can call it except publishing. Some of the things they published are extremely un-interesting to me. However, some are quite good. I think my 2 articles are new and interesting, especially the first which is the subject of my post.

Edited March 19, 2012 by Jim Fox

[questionposter]

So...what other simple thing do you do if you want to find the quotient of two polynomials?

Calculators can have a few inconveniences, like if you say "what's negative 5 squared?" and just type it in, it will give you negative twenty five, you need to put parentheses around the -5. I'm sure if you worked out each step carefully there wouldn't errors.

In my experiences, matrices lead to even more errors anyway.

Edited March 19, 2012 by questionposter

[Bignose]

Yes indeed. If all your coefficients are integers, you are safe. You will only have problems if the coefficients are 16 digit numbers that can experience round off error when they are manipulated on the computer.

 

This is true for most any real number algebraic manipulations on a computer, however. Care has to be taken to know how many significant figures are needed for the calculations. It certainly isn't limited to polynomial division, however. And, unless you force the program to only use integer math (and accept the rounding that will entail), using only integers doesn't limit the problem, because you can easily make numbers with many significant figures when dividing two integers.

 

You do realize that programs do exist for arbitrary limit precision, though, right? Mathematica software can be set to as many digits as you want, and the programming language Python has modules that do the same thing. I suspect that most modern languages have modules/extensions that can do this, or one can write their own programming to accomplish this. Even Matlab has a toolbox to do this: http://www.mathworks.com/matlabcentral/fileexchange/6446

 

Where issues like this are much more common are in naively applying the mean and variance formulas for data sets, e.g. when the variance is small compared to the mean. Again, tools exist to handle this correctly, as well as cleverly-designed algorithms to avoid the errors even with atypical data sets.

 

I guess, really, the question is: do you have something to discuss about this topic? Or a new algorithm to avoid the errors? Because one could almost think of the first post as spam to go check our your articles...

[khaled]

I agree with BigNose, actually higher numeric variable precision than the standard are possible, and if you do arithmetic operations over them,

 

unlike standard ones that would work directly on on the ALU itself, they will be done on a virtual dynamic ALU that can work on any numeric precision

 

but based on that precision, there will a price to pay on the side of processing power needed

[John Cuthber]

"Indeed, peer reviewed journals are the gold standard of publishing. However, if a university puts something out on the web, I do not know what you can call it except publishing."

 

http://en.wikipedia.org/wiki/Self-publishing#Vanity_publishing

[DrRocket]

However, if a university puts something out on the web, I do not know what you can call it except publishing.

 

Trash

[Jim Fox]

So...what other simple thing do you do if you want to find the quotient of two polynomials?

Calculators can have a few inconveniences, like if you say "what's negative 5 squared?" and just type it in, it will give you negative twenty five, you need to put parentheses around the -5. I'm sure if you worked out each step carefully there wouldn't errors.

In my experiences, matrices lead to even more errors anyway.

 

Read cnx.org/content/m43398/latest/. I give Matlab code for 2 alternative ways to do polynomial division. They do not seem to have the problem.

 

By the way, one of them does polynomial division by solving the matrix equation Ax=b. b is the product polynomial and A is constructed from the denominator.

 

The other way is to do division in the Fourier domain.

 

This is true for most any real number algebraic manipulations on a computer, however. Care has to be taken to know how many significant figures are needed for the calculations. It certainly isn't limited to polynomial division, however. And, unless you force the program to only use integer math (and accept the rounding that will entail), using only integers doesn't limit the problem, because you can easily make numbers with many significant figures when dividing two integers.

 

You do realize that programs do exist for arbitrary limit precision, though, right? Mathematica software can be set to as many digits as you want, and the programming language Python has modules that do the same thing. I suspect that most modern languages have modules/extensions that can do this, or one can write their own programming to accomplish this. Even Matlab has a toolbox to do this: http://www.mathworks...leexchange/6446

 

Where issues like this are much more common are in naively applying the mean and variance formulas for data sets, e.g. when the variance is small compared to the mean. Again, tools exist to handle this correctly, as well as cleverly-designed algorithms to avoid the errors even with atypical data sets.

 

I guess, really, the question is: do you have something to discuss about this topic? Or a new algorithm to avoid the errors? Because one could almost think of the first post as spam to go check our your articles...

Indeed, I have written several programs using Michael Rings multi-precision math package. However, this problem could take an awful lot of significant digits. I just repeated the experiment of creating a 99 degree random coefficient polynomial. Then I multiplied it by z-1000. Then I divided it by z-1000. The answer should be the original array of random values between 0 and 1. Instead the final value was 1E280. So I believe you would need 296 digits of accuracy to do this correctly. The errors in the deflation increase by a factor of 1000 at each step of the division. If the root was 10,000 or if it was a 200 degree polynomial you would need vastly more significant digits.

 

Multi-precision math is not the solution. You asked, " do you have something to discuss about this topic? Or a new algorithm to avoid the errors?" Yes, the first article I mentioned, cnx.org/content/m43398/latest/, gives Matlab code for two alternative methods of doing polynomial division and they do not have this problem.

 

"Indeed, peer reviewed journals are the gold standard of publishing. However, if a university puts something out on the web, I do not know what you can call it except publishing."

 

http://en.wikipedia....nity_publishing

This article in wikepedia discusses "vanity publishers" who charge authors a fee. Rice does not charge a fee.